Kurs:Grundkurs Mathematik (Osnabrück 2016-2017)/Teil I/Vorlesung 20/kontrolle

Wir kehren zur Thematik der Primzahlen und der Primfaktorzerlegung einer natürlichen Zahl zurück. Bisher kennen wir nur die Existenz einer Primfaktorzerlegung (siehe Satz 12.9), aber noch nicht die Eindeutigkeit. Obwohl wir diese Fragestellung für natürliche Zahlen formuliert haben, ergibt sich im Kontext der ganzen Zahlen ein neuer Zusammenhang, der für diese Thematik hilfreich ist.

Teilerfremdheit und das Lemma von Bézout

Aufgabe Referenznummer erstellen

Die Wasserspedition „Alles im Eimer“ verfügt über einen $7$ - und einen $10$ -Liter-Eimer, die allerdings keine Markierungen haben. Sie erhält den Auftrag, insgesamt genau einen Liter Wasser von der Nordsee in die Ostsee zu transportieren. Kann sie diesen Auftrag erfüllen?

Die Aufgabe ist lösbar: Man macht dreimal den $7$ -Liter-Eimer in der Nordsee voll und transportiert dies in die Ostsee. Danach (oder gleichzeitig) macht man zweimal den $10$ -Liter-Eimer in der Ostsee voll und transportiert dies in die Nordsee. Unterm Strich hat man dann

3 \cdot 7 - 2 \cdot 10 = 1

Liter transportiert (eine andere Möglichkeit ist $5 \cdot 10 - 7 \cdot 7 = 1$ ). Die dieser Überlegung zugrunde liegende Aussage heißt Lemma von Bézout.

Satz Referenznummer erstellen

Es seien $a, b \in ℕ$ zwei teilerfremde natürliche Zahlen.

Dann gibt es ganze Zahlen $r, s \in ℤ$ mit $r a + s b = 1$ .

Beweis

Wir beweisen die Aussage durch Induktion über das Maximum von $a$ und $b$ , wobei wir ohne Einschränkung $a \leq b$ wählen können. Wenn das Maximum $0$ ist, so sind beide Zahlen $0$ und somit nicht teilerfremd. Wenn das Maximum $1$ ist, so ist $b = 1$ und somit ergeben $r = 0$ und $s = 1$ eine Darstellung der $1$ . Es seien nun $a \leq b$ teilerfremd, $b \geq 2$ und die Aussage sei für alle Zahlenpaare, deren Maxima kleiner als $b$ sind, schon bewiesen. Dann ist $a < b$ , da bei $a = b$ die beiden Zahlen nicht teilerfremd sind. Ebenso können wir $a = 0$ ausschließen. Wir betrachten das Zahlenpaar $(a, b - a)$ und wollen darauf die Induktionsvoraussetzung anwenden. Das Maximum dieses neuen Paares ist jedenfalls kleiner als $b$ . Allerdings müssen wir, damit die Induktionsvoraussetzung wirklich angewendet werden kann, wissen, dass auch $a$ und $b - a$ teilerfremd sind. Dazu führen wir einen Widerspruchsbeweis. Nehmen wir also an, dass $a$ und $b - a$ nicht teilerfremd sind. Dann gibt es eine natürliche Zahl $t \geq 2$ , die sowohl $a$ als auch $b - a$ teilt. Dies bedeutet wiederum, dass es natürliche Zahlen $m, n$ mit $a = m t$ und $b - a = n t$ gibt. Doch dann ist

b = (b - a) + a = n t + m t = (n + m) t

ebenfalls ein Vielfaches von $t$ , im Widerspruch zur Teilerfremdheit von $a$ und $b$ . Die Induktionsvoraussetzung ist also auf $a$ und $b - a$ anwendbar und somit gibt es ganze Zahlen $r, s$ mit

r a + s (b - a) = 1 .

Dann ist aber auch

(r - s) a + s b = r a + s (b - a) = 1

und wir haben eine Darstellung der $1$ mit $a$ und $b$ gefunden.

◻

Die Division mit Rest, die wir bisher nur für natürliche Zahlen formuliert haben, überträgt sich unmittelbar auf ganze Zahlen (der Divisor bleibt eine natürliche Zahl).

Satz Referenznummer erstellen

Es sei $d$ eine fixierte positive natürliche Zahl.

Dann gibt es zu jeder ganzen Zahl $n$ eine eindeutig bestimmte ganze Zahl $q$ und eine eindeutig bestimmte natürliche Zahl $r$ , $0 \leq r \leq d - 1$ , mit

$n = q d + r .$

Beweis

Siehe Aufgabe 20.7.

◻

Definition Referenznummer erstellen

Es sei $(G, e, \circ)$ eine Gruppe. Eine Teilmenge $H \subseteq G$ heißt Untergruppe von $G$ , wenn Folgendes gilt.

$e \in H$ .
Mit $g, h \in H$ ist auch $g \circ h \in H$ .
Mit $g \in H$ ist auch $g^{- 1} \in H$ .

In einer Untergruppe kann man also die Verknüpfung der Gruppe ausführen, man kann das Inverse nehmen und das neutrale Element gehört dazu. In additiver Schreibweise, die für uns im Mittelpunkt steht, bedeuten die Bedingungen einfach

$0 \in H$ .
Mit $g, h \in H$ ist auch $g + h \in H$ .
Mit $g \in H$ ist auch das Negative $- g \in H$ .

Beispielsweise bilden alle Vielfachen der $5$ innerhalb der ganzen Zahlen eine Untergruppe, die wir mit $ℤ 5$ bezeichnen. Es ist ja

0 = 0 \cdot 5,

wenn $g = 5 \cdot a$ und $h = 5 \cdot b$ sind, so ist

h + g = 5 \cdot (a + b)

nach dem Distributivgesetz und mit $g = 5 \cdot a$ ist $- g = 5 \cdot (- a)$ . Wie im eingangs gegebenen Beispiel kann man sich eine Menge $a_{1}, \dots, a_{k}$ von ganzen Zahlen (Eimergrößen) vorgeben und sich fragen, welche Zahlen man daraus mit Hilfe von ganzzahligen Koeffizienten bilden kann (welche Wassermengen man transportieren kann). Es geht also um die Menge aller Zahlen der Form

n_{1} a_{1} + \dots + n_{k} a_{n} mit n_{j} \in ℤ .

Diese Gesamtmenge bildet eine Untergruppe von $ℤ$ , man spricht von der von den $a_{1}, \dots, a_{k}$ erzeugten Untergruppe von $ℤ$ . Statt Eimern kann man sich eine Menge von ganzzahligen Pfeilen vorstellen.

Satz Satz 20.5 ändern

Die Untergruppen von $ℤ$ sind genau

die Teilmengen der Form

$ℤ d = {k d ∣ k \in ℤ}$

mit einer eindeutig bestimmten nichtnegativen Zahl $d$ .

Beweis

Eine Teilmenge der Form $ℤ d$ ist aufgrund des Distributivgesetzes eine Untergruppe. Es sei umgekehrt $H \subseteq ℤ$ eine Untergruppe. Bei $H = 0$ kann man $d = 0$ nehmen, sodass wir voraussetzen dürfen, dass $H$ neben $0$ noch mindestens ein weiteres Element $x$ enthält. Wenn $x$ negativ ist, so muss die Untergruppe $H$ auch das Negative davon, also $- x$ enthalten, welches positiv ist. D.h. $H$ enthält auch positive Zahlen. Es sei nun $d$ die kleinste positive Zahl aus $H$ . Wir behaupten $H = ℤ d$ . Dabei ist die Inklusion $ℤ d \subseteq H$ klar, da mit $d$ alle (positiven und negativen) Vielfachen von $d$ dazugehören müssen. Für die umgekehrte Inklusion sei $h \in H$ beliebig. Nach der Division mit Rest gilt

h = q d + r mit 0 \leq r < d .

Wegen $h \in H$ und $q d \in H$ ist auch $r = h - q d \in H$ . Nach der Wahl von $d$ muss wegen $r < d$ gelten: $r = 0$ . Dies bedeutet $h = q d$ und damit $h \in ℤ d$ , also $H \subseteq ℤ d$ .

◻

Lemma Referenznummer erstellen

Es seien $a_{1}, \dots, a_{k}$ ganze Zahlen und $H = (a_{1}, \dots, a_{k}) = {n_{1} a_{1} + n_{2} a_{2} + \dots + n_{k} a_{k} ∣ n_{j} \in ℤ}$ die davon erzeugte Untergruppe.

Eine ganze Zahl $t$ ist ein gemeinsamer Teiler der $a_{1}, \dots, a_{k}$ genau dann, wenn $H \subseteq ℤ t$ ist, und $t$ ist ein größter gemeinsamer Teiler genau dann, wenn $H = ℤ t$ ist.

Beweis

Aus $H = (a_{1}, \dots, a_{k}) \subseteq (t)$ folgt sofort $ℤ a_{i} \subseteq ℤ t$ für jedes $i = 1, \dots, k$ , was gerade bedeutet, dass $t$ diese Zahlen teilt, also ein gemeinsamer Teiler ist. Es sei umgekehrt $t$ ein gemeinsamer Teiler. Dann ist $a_{i} \in ℤ t$ und da $H = (a_{1}, \dots, a_{k})$ die kleinste Untergruppe ist, die alle $a_{i}$ enthält, muss $H \subseteq ℤ t$ gelten.

Aufgrund von Satz 20.5 wissen wir, dass es eine ganze Zahl $d$ mit $H = ℤ d$ gibt. Für einen anderen gemeinsamen Teiler $t$ der $a_{i}$ gilt $ℤ d = H \subseteq ℤ t$ , sodass $d$ von allen anderen gemeinsamen Teilern geteilt wird, also ein größter gemeinsamer Teiler ist.

◻

Der Euklidische Algorithmus

Es seien $a, b$ ganze Zahlen, $b \neq 0$ . Dann kann man die Division mit Rest durchführen und erhält $a = q b + r$ mit $0 \leq r < | b |$ . Danach kann man (bei $r \neq 0$ ) die Division mit Rest von $b$ durch $r$ durchführen, d.h. $b$ nimmt die Rolle von $a$ und $r$ die Rolle von $b$ ein und man erhält einen neuen Rest. Dies kann man fortsetzen, und da dabei die Reste immer kleiner werden bricht das Verfahren irgendwann ab.

Definition Referenznummer erstellen

Es seien zwei ganze Zahlen $a, b$ (mit $b \neq 0$ ) gegeben. Dann nennt man die durch die Anfangsbedingungen $r_{0} = a$ und $r_{1} = b$ und die mittels der Division mit Rest

r_{i} = q_{i} r_{i + 1} + r_{i + 2}

rekursiv bestimmte Folge $r_{i}$ die Folge der euklidischen Reste.

Satz Satz 20.8 ändern

Es seien ganze Zahlen $r_{0} = a$ und $r_{1} = b \neq 0$ gegeben.

Dann besitzt die Folge $r_{i}$ , $i = 0, 1, 2, \dots$ der euklidischen Reste folgende Eigenschaften.

Es ist $r_{i + 2} = 0$ oder $r_{i + 2} < r_{i + 1}$ .^[1]

Es gibt ein (minimales) $k \geq 2$ mit $r_{k} = 0$ .

Es ist
$ggT (r_{i - 1}, r_{i}) = ggT (r_{i}, r_{i + 1})$

für alle $i = 1, \dots, k$ .

Es sei $k \geq 2$ der erste Index derart, dass $r_{k} = 0$ ist. Dann ist
$ggT (a, b) = r_{k - 1} .$

Beweis

Dies folgt unmittelbar aus der Definition der Division mit Rest.
Solange $r_{i} \neq 0$ ist, wird die Folge der natürlichen Zahlen $r_{i}$ immer kleiner, sodass irgendwann der Fall $r_{i} = 0$ eintreten muss.
Wenn $t$ ein gemeinsamer Teiler von $r_{i}$ und von $r_{i + 1}$ ist, so zeigt die Beziehung
$r_{i - 1} = q_{i - 1} r_{i} + r_{i + 1},$

dass $t$ auch ein Teiler von $r_{i - 1}$ und damit ein gemeinsamer Teiler von $r_{i - 1}$ und von $r_{i}$ ist. Die Umkehrung folgt genauso.
Dies folgt aus (3) mit der Gleichungskette
$ggT (a, b) = ggT (b, r_{2}) = ggT (r_{2}, r_{3}) = \dots = ggT (r_{k - 2}, r_{k - 1}) = ggT (r_{k - 1}, r_{k}) = ggT (r_{k - 1}, 0) = r_{k - 1} .$

◻

Beispiel

Aufgabe

Bestimme in $ℤ$ mit Hilfe des euklidischen Algorithmus den größten gemeinsamen Teiler von $71894$ und $45327$ .

Lösung

Der Euklidische Algorithmus liefert:

71894 = 1 \cdot 45327 + 26567

45327 = 1 \cdot 26567 + 18760

26567 = 1 \cdot 18760 + 7807

18760 = 2 \cdot 7807 + 3146

7807 = 2 \cdot 3146 + 1515

3146 = 2 \cdot 1515 + 116

1515 = 13 \cdot 116 + 7

116 = 16 \cdot 7 + 4

7 = 1 \cdot 4 + 3

4 = 1 \cdot 3 + 1.

Die Zahlen $71894$ und $45327$ sind also teilerfremd.

Bei kleinen Zahlen sieht man häufig relativ schnell direkt, was ihr größter gemeinsamer Teiler ist, da man die Primfaktorzerlegung kennt bzw. mögliche gemeinsame Teiler schnell übersehen kann. Bei zwei größeren Zahlen müssten aber viel zu viele Probedivisionen durchgeführt werden! Der euklidische Algorithmus ist also zur Bestimmung des größten gemeinsamen Teilers ein sehr effektives Verfahren!

Wenn man mit dem euklidischen Algorithmus den größten gemeinsamen Teiler $d$ von zwei Zahlen $a$ und $b$ gefunden hat, so kann man aus diesen Rechnungen häufig direkt ablesen, wie die Quotienten $\frac{a}{d}$ und $\frac{b}{d}$ aussehen.

Es seien zwei Strecken $s$ und $t$ gegeben. Man sagt, dass $t$ ein (ganzzahliges) Vielfaches von $s$ ist, wenn es eine natürliche Zahl $n$ mit der Eigenschaft gibt, dass sich die Strecke $t$ ergibt, wenn man die Strecke $s$ $n$ -fach gerade hintereinanderlegt (die Strecke wird also $n$ -mal genommen). Für zwei Strecken $s$ und $t$ gibt es das folgende Konzept, das ihre ganzzahlige Vergleichbarkeit ausdrückt. Man beachte, dass dieses Konzept unabhängig von solchen Messungen ist, die die Längen in Zahlen mit Hilfe von Einheiten ausdrücken. Es werden nur die beiden Längen gegeneinander gemessen, man verwendet keine normierten Standardlängen.

Definition Referenznummer erstellen

Zwei Strecken $s$ und $t$ heißen kommensurabel, wenn es eine Strecke $g$ mit der Eigenschaft gibt, dass beide Strecken ganzzahlige Vielfache von $g$ sind.

Auch vom euklidischen Algorithmus gibt es in diesem Kontext eine sinnvolle Version. Die Strecke $t$ sei mindestens so lang wie $s$ . Dann ist

t = n s + r

mit $n \in ℕ$ und einer „Reststrecke“ $r$ , die kürzer als $s$ ist und eventuell $0$ ist. Die Gleichung ist dabei als eine Gleichung von hintereinander hingelegten Strecken zu verstehen. Wie in Satz 20.8 ergibt sich, dass mit $s$ und $t$ auch $s$ und $r$ kommensurabel sind. Wenn man dieses Verfahren rekursiv fortsetzt, so tritt im Falle der Kommensurabilität irgendwann die Situation auf, wo die kleine Strecke in die größere Strecke voll aufgeht. Somit hat man dann auch die größte gemeinsame Teilerstrecke gefunden.

Darstellung des größten gemeinsamen Teilers

Mit dem euklidischen Algorithmus kann man auch durch Zurückrechnen eine Darstellung des größten gemeinsamen Teilers als Linearkombination der beiden vorgegebenen Zahlen erhalten. Dazu seien

r_{i} = q_{i} r_{i + 1} + r_{i + 2}

die Gleichungen im euklidischen Algorithmus und $r_{k - 1} = ggT (r_{0}, r_{1})$ . Aus der letzten Gleichung

r_{k - 3} = q_{k - 3} r_{k - 2} + r_{k - 1}

erhält man die Darstellung

r_{k - 1} = r_{k - 3} - q_{k - 3} r_{k - 2}

von $r_{k - 1}$ als Linearkombination mit $r_{k - 3}$ und $r_{k - 2}$ . Mit der vorhergehenden Zeile

r_{k - 4} = q_{k - 4} r_{k - 3} + r_{k - 2}

bzw.

r_{k - 2} = r_{k - 4} - q_{k - 4} r_{k - 3}

kann man in dieser Darstellung $r_{k - 2}$ ersetzen und erhält eine Darstellung von $r_{k - 1}$ als Linearkombination von $r_{k - 3}$ und $r_{k - 4}$ . So fortfahrend erhält man schließlich eine Darstellung von