2. Die Eindeutigkeit der Primfaktorzerlegung

Es ist schwer vorstellbar, wie eine natürliche Zahl n ≥ 2 zwei Primfaktorzerlegungen mit nicht übereinstimmenden Bausteinen haben könnte. Um ein Problembewusstsein zu erzeugen, betrachten wir unsere Beweise der Existenz einer Primfaktorzerlegung. Wir hatten wiederholt kleinste Primteiler abgespalten und so eine Primfaktorzerlegung

n = p₁ … p_k mit p₁ ≤ p₂ ≤ … ≤ p_k

erhalten. Wir könnten aber genauso gut wiederholt größte Primteiler abspalten, um eine Primfaktorzerlegung

n = q₁ … q_m mit q₁ ≥ q₂ ≥ … ≥ q_m

zu erhalten. Es ist nicht klar, dass m = k gilt, und dass die Primzahlen q_j nichts anderes sind als die Primzahlen p_i in umgekehrter Reihenfolge. Diese Aussagen sind richtig, aber sie benötigen einen Beweis. Am Ende des Essays betrachten wir ein Gegenbeispiel zur Eindeutigkeit der Primfaktorzerlegung in einer anderen Zahlenwelt. Aber auch ohne ein derartiges Gegenbeispiel muss die Eindeutigkeit bewiesen werden, damit sie von einer Hypothese zu einem Satz wird.

Wir formulieren zunächst das Ergebnis in einer geeigneten Form:

Satz (Fundamentalsatz der Zahlentheorie, Eindeutigkeit)

Sei n ≥ 2. Dann ist eine Primfaktorzerlegung von n bis auf die Reihenfolge der Faktoren eindeutig bestimmt. Genauer gilt:

Seien p₁ < …< p_k und q₁ < … < q_k′ Primzahlen und e₁, …, e_k, d₁, …, d_k′ natürliche Zahlen größergleich 1 mit

(+) n = p₁^e₁ … p_k^e_k = q₁^d₁ … q_k′^d_k′.

Dann gilt k = k′ und p₁ = q₁, …, p_k = q_k, e₁ = d₁, …, e_k = d_k.

Wir geben in diesem und in den folgenden Essays verschiedene Beweise dieses grundlegenden Satzes. Wir beginnen mit dem klassischen Argument.

Euklid hat die Eindeutigkeit der Primfaktorzerlegung mit Hilfe des folgenden Hilfssatzes gezeigt:

Satz (Lemma von Euklid, Teilbarkeitssatz von Euklid)

Seien a, b ≥ 1 natürliche Zahlen, und sei p eine Primzahl, die das Produkt ab teilt. Dann ist p ein Teiler von a oder ein Teiler von b.

Kurz: Teilt eine Primzahl ein Produkt, so teilt sie einen Faktor. Mit Hilfe dieser Aussage lässt sich die Eindeutigkeit vergleichsweise leicht beweisen. Um dies einzusehen, nehmen wir das Lemma von Euklid vorerst als bewiesen an. Wir können es leicht auf mehr als zwei Faktoren verallgemeinern:

Satz (Lemma von Euklid, allgemeine Version)

Seien a₁, …, a_k ≥ 1 natürliche Zahlen, und sei p eine Primzahl, die das Produkt a₁ … a_k teilt. Dann gibt es ein i derart, dass p die Zahl a_i teilt.

Die allgemeine Version erhalten wir durch mehrfache Anwendung der Version für zwei Faktoren. Ordentlich wird der Beweis durch Induktion nach der Anzahl k ≥ 2 der Faktoren geführt.

Die allgemeine Version ermöglicht nun:

Beweis der Eindeutigkeit mit Hilfe des Lemmas von Euklid

Wir zeigen die Aussage des Fundamentalsatzes durch starke Induktion nach n ≥ 2.

Induktionsschritt n

Ist n prim, so ist die Aussage klar. Andernfalls sei wie im Fundamentalsatz

(+) n = p₁^e₁ … p_k^e_k = q₁^d₁ … q_k′^d_k′

mit Primzahlen p₁ < … < p_k, q₁ < … < q_k′ und positiven Exponenten. Wir dürfen annehmen, dass p₁ ≤ q₁, sonst tauschen wir die p’s und q’s aus. Schreiben wir die q-Darstellung als Produkt von d₁ + … + d_k′ Primzahlen (mit Exponenten 1) aus, so liefert das allgemeine Lemma von Euklid, dass der Teiler p₁ von n eine der Primzahlen q₁, …, q_k′ ist (denn eine Primzahl p ist nur dann Teiler einer Primzahl q, wenn p = q). Wegen p₁ ≤ q₁ < … < q_k′ ist also p₁ = q₁. Division durch p₁ liefert

p₁^{e₁ − 1} … p_k^e_k = q₁^{d₁ − 1} … q_k′^d_k′ (mit p₁ = q₁)

mit e₁ − 1, d₁ − 1 ≥ 0. Nach Induktionsvoraussetzung stimmen diese beiden Darstellungen überein. Aus e₁ − 1 = d₁ − 1 folgt e₁ = d₁, womit die Übereinstimmung der Darstellungen in (+) gezeigt ist.

Damit ist der Beweis des Fundamentalsatzes auf den Beweis des Lemmas von Euklid reduziert. Wir besprechen Beweise des Lemmas von Euklid im folgenden Essay. Hier betrachten wir noch:

Ein Gegenbeispiel zur Eindeutigkeit der Primfaktorzerlegung

Wir reduzieren die natürlichen Zahlen ℕ auf die positiven geraden Zahlen

G = { 2, 4, 6, 8, 10, … }.

In der Menge G können wir wie in den natürlichen Zahlen addieren und multiplizieren, denn die Summe und das Produkt zweier gerader Zahlen ist ebenfalls gerade. Die Menge G ist, wie man sagt, abgeschlossen unter der Addition und Multiplikation. Die Menge G enthält kein ausgezeichnetes Eins-Element für die Multiplikation mehr. Das ist für einen multiplikativen Zahlbereich ungewöhnlich, soll unser aber hier nicht weiter stören. In G können wir die Begriffe der Teilbarkeit, der zusammengesetzten Zahl und der Primzahl in Analogie zu den natürlichen Zahlen einführen. Es gilt zum Beispiel

8 = 2 · 4, 12 = 2 · 6,

sodass die Zahlen 8 und 12 zusammengesetzt sind. Dagegen ist die Zahl 6 eine Primzahl in G. Die Menge G „sieht“ keine Möglichkeit, die Zahl 6 multiplikativ zu zerlegen. In den geraden Zahlen ist die Darstellung 6 = 2 · 3 nicht möglich, es gibt keine 3. Die ersten Primzahlen in G lauten

2, 6, 10, 14, 18, 22, 26, 30, …

Bemerkenswerterweise ist nun in G die Eindeutigkeit der Primfaktorzerlegung verletzt. Denn es gilt zum Beispiel

36 = 6 · 6 = 2 · 18, 60 = 2 · 30 = 6 · 10,

mit G-Primzahlen 2, 6, 10, 30. Die Zahlen 36 und 60 haben also in G jeweils zwei verschiedene Primfaktorzerlegungen. Das Lemma von Euklid ist (wie es sein muss!) verletzt:

Beispiel

Seien p = 6, a = 2 und b = 18. Dann teilt die G-Primzahl p das Produkt a · b, da 2 · 18 = 36 = 6 · 6. Aber sie teilt in G keinen der beiden Faktoren a und b. Teilen wir die 36 durch 2, so geht der G-Primfaktor 6 verloren. Teilen wir die 36 durch 6, so geht der G-Primfaktor 2 verloren. In G kann also das Quadrat p² einer Primzahl p einen von p verschiedenen Primteiler q besitzen.

Die Eindeutigkeit der Primfaktorzerlegung in den natürlichen Zahlen können wir als Stabilitätsaussage lesen: Ein Primfaktor einer Zahl bleibt erhalten, wenn wir einen anderen Primfaktor abspalten. Und wenn wir einen mehrfach vorhandenen Primfaktor abspalten, so wird dabei seine Vielfachheit um genau eins reduziert.