4. Das Lemma von Euklid, II
Das Lemma von Euklid lässt sich auch ohne Verwendung des Euklidischen Algorithmus beweisen. Wir geben ein Argument, das nur elementare Eigenschaften des größten gemeinsamen Teilers (ggT) und des kleinsten gemeinsamen Vielfachen (kgV) verwendet. Diese Eigenschaften können mit einiger Sorgfalt und Mühe direkt aus der Definition der Teilbarkeit abgeleitet werden.
Zur Vereinfachung der Notation schreiben wir im Folgenden kurz (a, b) statt ggT(a, b) und [ a, b ] statt kgV(a, b). Weiter verwenden wir auch wieder die Notation a|b für „a ist ein Teiler von b“.
Satz (Eigenschaften des ggT und kgV)
Seien a, b, c, d positive natürliche Zahlen. Dann gilt:
(1) | Sind a und b Teiler von c, so ist [ a, b ] ein Teiler von c. |
(2) | Ist d ein Teiler von a und von b, so ist d ein Teiler von (a, b). |
(3) | (ca, cb) = c (a, b). |
Beweis
zu (1): Seien a, b Teiler von c. Wir setzen n = [ a, b ] und zeigen, dass n|c. Durch Division von c durch n mit Rest erhalten wir eindeutige natürliche Zahlen q, r mit
c = q n + r, 0 ≤ r < n.
Dann gilt r = c − q n. Da a die Zahlen c und n teilt, teilt a jede Linearkombination von c und n. Folglich gilt a|r. Analog ergibt sich, dass b|r. Da 0 ≤ r < n gilt und n nach Definition die kleinste positive Zahl ist, die sowohl von a als auch b geteilt wird, ergibt sich aus a|r und b|r, dass r = 0. Also ist c = q n, sodass n ein Teiler von c ist.
zu (2): Sei d ein Teiler von a und von b. Wir zeigen, dass d|(a, b). Wegen d|a und (a, b)|a folgt aus (1), dass [ d, (a, b) ]|a. Analog gilt [ d, (a, b)]|b. Also ist [ d, (a, b) ] ein gemeinsamer Teiler von a und b, sodass [ d, (a, b) ] ≤ (a, b). Da [ d, (a, b) ] ein Vielfaches von (a, b) ist, gilt (a, b) ≤ [ d, (a, b) ]. Insgesamt ist also (a, b) = [ d, (a, b) ]. Dies zeigt, dass d|(a, b).
zu (3): Wir zeigen, dass c(a, b) ≤ (ca, cb) und dass (ca, cb) ≤ c(a, b).
Für die erste Ungleichung beobachten wir, dass (a, b)|a. Folglich gilt c(a, b)|ca. Analog gilt c(a, b)|cb. Also ist c(a, b) ein gemeinsamer Teiler von ca und cb, sodass c(a, b) ≤ (ca, cb).
Für die zweite Ungleichung beobachten wir, dass c|ca und c|cb. Folglich gilt c|(ca, cb) nach Teil (2). Also gibt es ein m mit cm = (ca, cb). Dann gilt cm|ca und cm|cb. Folglich existieren k1, k2 mit cmk1 = ca und cmk2 = cb. Kürzen von c ≠ 0 zeigt, dass m|a und m|b. Folglich ist m ≤ (a, b). Dies liefert (ca, cb) = cm ≤ c(a, b).
Aus den Eigenschaften (2) und (3) des Satzes ergibt sich das Lemma von Euklid in wenigen Zeilen:
Beweis des Lemmas von Euklid
Seien a, b ≥ 1 natürliche Zahlen, und sei p eine Primzahl, die das Produkt a b teilt. Wir nehmen an, dass p kein Teiler von b ist und zeigen, dass p ein Teiler von a ist. Nach Annahme ist (p, b) = 1. Da aber p ein Teiler von ap und von ab ist, ist p nach Teil (2) des Satzes ein Teiler von (ap, ab). Nach Teil (3) des Satzes gilt aber
(ap, ab) = a · (p, b) = a · 1 = a.
Dies zeigt, dass p ein Teiler von a ist.
Damit haben wir einen weiteren Pfad zum Beweis der Eindeutigkeit der Primfaktorzerlegung gefunden. Die elementaren Eigenschaften des ggT und kgV aus der Definition der Teilbarkeit unter dem Motto „verwende so wenig wie möglich“ abzuleiten ist vielleicht etwas mühsam und unanschaulich. Aber auch diese Form der mathematischen Tätigkeit kann sehr gewinnbringend sein. Es ist eine Art Survival-Training mit einer kleinen Werkzeugkiste mit Definitionen. Wir brauchen viele Ideen und kleine Tricks, um zu überleben.