5. Weitere Eindeutigkeitsbeweise
Anfang des 20. Jahrhunderts wurden durch Ernst Zermelo, Ferdinand von Lindemann und Helmut Hasse kompakte Beweise des Fundamentalsatzes der Zahlentheorie gefunden, die das Lemma von Euklid nicht verwenden. Sie erreichen ihr Ziel direkt. Eine Möglichkeit, das Argument zu führen, zeigt der folgende Beweis.
Satz (Fundamentalsatz der Zahlentheorie, Eindeutigkeit)
Sei n ≥ 2. Dann ist eine Primfaktorzerlegung von n bis auf die Reihenfolge der Faktoren eindeutig bestimmt.
Beweis ohne Verwendung des Lemmas von Euklid
Wir führen den Beweis durch starke Induktion nach n ≥ 2.
Induktionsschritt n ≥ 2:
Ist n prim, so ist die Aussage klar. Andernfalls sei
(+) n = p1e1 … pkek = q1d1 … qk′dk′
mit Primzahlen p1 < … < pk, q1 < … < qk′ und positiven Exponenten. Wir dürfen wieder p1 ≤ q1 annehmen. Es genügt zu zeigen:
(#) p1 = q1.
Denn dann gilt
n/p1 = p1e1 − 1 … pkek = q1d1 − 1 … qk′dk′ (mit e1 − 1, d1 − 1 ≥ 0),
und aus der Induktionsvoraussetzung für n/p1 folgt, dass diese beiden Darstellungen von n/p1 übereinstimmen. Dann stimmen aber auch die beiden Darstellungen von n in (+) überein, da sie aus den Darstellungen von n/p1 durch Hinzufügen des Faktors p1 entstehen.
Beweis von p1 = q1
Annahme nicht. Wegen p1 ≤ q1 gilt also p1 < q1. Sei m = n − p1q1. Da n keine Primzahl ist, gilt p1 q1 < q12 ≤ n und damit
m = n − p1 q1 > 0.
Da p1 ein Teiler von n ist, ist p1 ein Teiler von m. Analog ist q1 ein Teiler von m. Nach Induktionsvoraussetzung kommen damit sowohl p1 als auch q1 in der eindeutigen Primfaktorzerlegung von m vor, sodass p1q1 ein Teiler von m ist. Dann ist aber p1q1 ein Teiler von n = m + p1q1. Damit ist p1 ein Teiler von n/q1. Aus (+) ergibt sich die Darstellung
n/q1 = q1d1 − 1 q2d2 … qk′dk′.
Erneut nach Induktionsvoraussetzung kommt der Teiler p1 von n/q1 in dieser Darstellung vor, im Widerspruch zu p1 < q1.
Trotz der Kürze dieser Argumentation bleibt der Weg über das Lemma von Euklid in Kombination mit dem Lemma von Bezout wertvoll, und er darf sogar nach wie vor als Standard gelten. Der Euklidische Algorithmus ist der vielleicht wichtigste Algorithmus der gesamten Mathematik, und das Lemma von Bezout ist ein Korollar des Ergebnisses, dass der Euklidische Algorithmus den größten gemeinsamen Teiler zweier Zahlen berechnet. All diese Dinge werden in jeder systematischen Darstellung der elementaren Zahlentheorie irgendwann bewiesen, und damit schadet es nicht, sie vor der Eindeutigkeit der Primfaktorzerlegung zu behandeln. Mit Hilfe des Lemmas von Bezout ist, wie wir gesehen haben, das Lemma von Euklid und weiter die Eindeutigkeit der Primfaktorzerlegung leicht zu beweisen. Das Lemma von Euklid führt zudem in sehr klarer Weise vor Augen, welche Eigenschaft gebraucht wird, um die Eindeutigkeit der Primfaktorzerlegung beweisen zu können. Es lädt zum Experimentieren, Nachdenken und Fragen ein: „Ist das nicht klar?“ Eben nicht. „Das muss doch einfach zu zeigen sein!“ Offenbar nicht.
Auf der anderen Seite ist das moderne Argument bestechend kurz und es ist sehr erfreulich, die Eindeutigkeit ohne Umwege beweisen zu können: „Das muss sich doch durch Induktion beweisen lassen!“ Ja, aber es ist relativ trickreich. Wie immer in der Mathematik ist Vielfalt und Methodenreichtum wertvoll, nicht zuletzt auch didaktisch.
Hat man die Eindeutigkeit der Primfaktorzerlegung einmal bewiesen, so lassen sich viele Eigenschaften des größten gemeinsamen Teilers und des kleinsten gemeinsamen Vielfachen mehr oder weniger direkt aus der Primfaktorzerlegung ablesen, sodass diese Eigenschaften an Anschaulichkeit gewinnen. Ein besonders schönes Beispiel ist die für alle natürlichen Zahlen a, b gültige Produktformel
ggT(a, b) · kgV(a, b) = a · b.
Wir diskutieren sie im folgenden Essay genauer. Auch das Lemma von Euklid ergibt sich aus der Existenz und Eindeutigkeit der Primfaktorzerlegung:
Beweis des Lemmas von Euklid mit Hilfe des Fundamentalsatzes
Sei p prim und Teiler eines Produkts ab. Dann gibt es eine Primfaktorzerlegung von ab, in der p vorkommt (wir beginnen mit der Abspaltung von p und fahren dann beliebig fort). Aufgrund der Eindeutigkeit der Primfaktorzerlegung entsteht die betrachtete Zerlegung von ab durch Zusammenfügen der eindeutigen Primfaktorzerlegungen von a und b, sodass p in einer der beiden Zerlegungen vorkommen muss. Damit ist p ein Teiler von a oder ein Teiler von b.
Noch ein Beweis
Wir zeigen noch einmal:
Satz (Fundamentalsatz der Zahlentheorie, Eindeutigkeit)
Sei n ≥ 2. Dann ist eine Primfaktorzerlegung von n bis auf die Reihenfolge der Faktoren eindeutig bestimmt.
Beweis
Annahme nicht. Sei n das kleinste Gegenbeispiel. Dann gibt es einen Primteiler p von n und eine Primfaktorzerlegung
n = p1 … pk
von n mit p < p1, …, pk (denn nach Minimalität von n haben zwei verschiedene Primfaktorzerlegungen von n keine gemeinsamen Faktoren, da wir diese Abdividieren könnten; der kleinste Primfaktor der beiden Zerlegungen und die Zerlegung ohne diesen Faktor sind also wie gewünscht).
Für i = 1, …, k sei
pi = qip + ri, 0 < ri < p,
die Division mit Rest von pi durch p (wegen pi prim und p ≠ pi ist ri ≠ 0). Wir setzen r = r1 … rk. Dann gilt 0 < r < n, da ri < pi für alle i. Weiter gilt:
(+) r ist durch p teilbar.
Beweis von (+)
Ausmultiplizieren liefert ein q mit
n = p1 … pk = (q1p + r1) … (qkp + rk) = qp + r.
Da n und qp durch p teilbar sind, ist r = n − qp durch p teilbar.
Damit gibt es eine Primfaktorzerlegung von r, in der p vorkommt. Ersetzen wir im Produkt r1 … rk jeden Faktor ri < p durch eine Primfaktorzerlegung seiner selbst, so erhalten wir eine Primfaktorzerlegung von r, in der p nicht vorkommt. Wegen r < n ist dies ein Widerspruch zur Minimalität von n.
Dieses Argument hat der Autor beim Nachdenken über das Problem entdeckt; es ist aber gut möglich, dass es auch anderswo zu finden ist. Der Beweis verwendet das Prinzip vom kleinsten Element. Er lässt sich aber, wie immer in solchen Fällen, auch induktiv führen.
Bemerkung: Verwendung der Kongruenzrelation
Setzen wir die Kongruenzrelation „modulo p“ als bekannt voraus, so können wir den Beweis von (+) auch so notieren: Es gilt r1 ≡ pi mod(p) für alle i = 1, …, k, sodass nach den Kongruenzregeln
r ≡ r1 … rk ≡ p1 … pk ≡ n ≡ 0 mod(p).
Der Beweis von (+) ist aber auch nicht viel länger und wir wollten das Argument so elementar wie möglich präsentieren. Es lässt sich als Verallgemeinerung des Beweises des Satzes ansehen, dass das Produkt ungerader Zahlen ungerade ist. Die 2 kann sich in ein derartiges Produkt nicht hineinschummeln. Analog kann für Primzahlen p < p1, …, pk die Zahl p kein Teiler von p1 … pk sein.
Für Leser, denen die Beweisführung zunächst vielleicht etwas zu kompakt erscheint, fügen wir noch an:
Erklärungen zum Beweis
Wir nehmen an, dass sich eine natürliche Zahl n in der Form
(+) n = p1 p2 = q1 q2
darstellen lässt, mit Primzahlen p1 ≤ p2 und q1 ≤ q2. (Dass je zwei Faktoren beteiligt sind, dient für diese Erläuterungen lediglich der Vereinfachung.) Wir nehmen weiter an, dass pi ≠ qj für alle i, j gilt, da wir sonst gemeinsame Faktoren kürzen können. Schließlich können wir auch p1 < q1 voraussetzen (ansonsten tauschen wir die p’s und q’s einfach aus). Nun messen wir die Primzahlen q1 und q2 mit Hilfe von p1 durch Divisionen mit Rest. Wir erhalten
q1 = d1p1 + r1, q2 = d1p1 + r2
mit Quotienten d1, d2 ≥ 1 und Resten r1, r2 ≤ p. Der Rest r1 kann nicht 0 sein, da ansonsten q1 durch p1 teilbar wäre, was wegen q1 prim und p1 < q1 nicht sein kann. Analog ist r2 ungleich 0. Wir erhalten
| p1p2 = n | = q1q2 = (d1p1 + r1)(d2p1 + r2) |
| = d1d2p12 + r1d2p1 + d1p1r2 + r1r2 | |
| = p1(d1d2p1 + r1d2 + d1r2) + r1r2. |
Damit gilt für r = r1r2 > 0, dass
r = r1r2 = p1p2 − p1(d1d2p1 + r1d2 + d1r2) = p1(p2 − d1d2p1 − r1d2 − d1r2).
Also ist r durch p1 teilbar. Aber die beiden Reste r1 und r2 sind nach Konstruktion kleiner als p1, sodass es keine Primfaktorzerlegung von r1 oder r2 gibt, die p enthält. Fügen wir also zwei Primfaktorzerlegungen von r1 und r2 zusammen, so erhalten wir eine Zerlegung von r ohne p. Starten wir eine Zerlegung von r durch Abspalten des Primteilers p von r, so erhalten wir eine Zerlegung von r, die p enthält. Dies zeigt insgesamt:
Gibt es zwei verschiedene Primfaktorzerlegungen von n, so gibt es zwei verschiedene Primfaktorzerlegungen von r < n.
Durch ein übliches Beweisschema (starke Induktion, Prinzip vom kleinsten Element, Prinzip vom unendlichen Abstieg) ergibt sich aus dieser Implikation die Eindeutigkeit der Primfaktorzerlegung.