Die Primfaktorzerlegung
Die Primzahlen können wir als multiplikative Bausteine der natürlichen Zahlen n ≥ 2 auffassen. Wir werden nun zeigen, dass die „multiplikative Konstruktion“ einer Zahl im Wesentlichen, d. h. bis auf die Anordnung der Bausteine, eindeutig bestimmt ist. Hierzu definieren wir:
Definition (Primfaktorzerlegung)
Eine Primfaktorzerlegung (PFZ) einer natürlichen Zahl n ≥ 2 ist eine Darstellung von n als Produkt von Primzahlen. Durch Anordnung der Faktoren kann jede PFZ in die kanonische Form
n = p1e1 · … · pkek mit p1 < … < pk und e1, …, ek ≥ 1
gebracht werden.
Beispiel
Die Zahl n = 40 besitzt beispielsweise die Primfaktorzerlegungen
2 · 2 · 2 · 5, 2 · 2 · 5 · 2, 5 · 2 · 2 · 2.
Die kanonische Form dieser Zerlegungen ist 23 · 5.
Es ist richtig, aber keineswegs klar, dass eine Primfaktorzerlegung einer Zahl bis auf die Reihenfolge der Faktoren eindeutig bestimmt ist. Bevor wir dies zeigen, halten wir explizit fest:
Satz (Existenz einer Primfaktorzerlegung)
Sei n ≥ 2. Dann existiert eine PFZ von n. Genauer gilt: Ist p ein Primteiler von n, so existiert eine PFZ von n, in der p als Faktor vorkommt.
Beweis
Wir zeigen die Aussage durch starke Induktion.
Induktionsschritt n ≥ 2:
Ist n prim, so ist n eine PFZ von n. Andernfalls gibt es einen Primteiler p < n von n. Sei q = n/p. Dann gilt 2 ≤ q < n, sodass nach I. V. eine PFZ von q existiert. Anfügen des Faktors p an eine PFZ von q liefert eine PFZ von n.
Allgemeiner gilt: Ist d ≥ 2 ein Teiler von n, so kann eine PFZ von d zu einer PFZ von n erweitert werden, indem eine PFZ von n/d an die betrachtete PFZ von d angefügt wird.
Nach diesen Vorbereitungen können wir nun zeigen:
Satz (Eindeutigkeit der Primfaktorzerlegung, Fundamentalsatz der Zahlentheorie)
Sei n ≥ 2. Dann ist eine PFZ von n bis auf die Reihenfolge der Faktoren eindeutig.
Mit anderen Worten:
Jede Zahl n ≥ 2 hat genau eine PFZ in kanonischer Form.
Ein Beweis des Satzes findet sich bereits bei Euklid. Wir geben einen kompakten zu Beginn des 20. Jahrhunderts gefundenen Beweis mit Hilfe von starker Induktion. Die Argumentation geht zurück auf Ernst Zermelo, Ferdinand von Lindemann und Helmut Hasse.
Beweis
Wir führen den Beweis durch starke Induktion.
Induktionsschritt n ≥ 2:
Ist n prim, so ist die Eindeutigkeit klar. Andernfalls sei, in kanonischen Formen,
(+) n = p1e1 … pkek = q1d1 … qk′dk′, mit p1 ≤ q1.
Es genügt zu zeigen, dass p1 = q1. Denn dann können wir in beiden PFZ durch p1 dividieren und die I. V. auf n/p1 = n/q1 anwenden. Dies zeigt, dass die beiden Darstellungen
p1e1 − 1 … pkek und q1d1 − 1 … qk′dk′
von n/p1 übereinstimmen. Hieraus folgt, dass die beiden Darstellungen von n in (+) übereinstimmen.
Annahme, p1 < q1. Dann ist p1 q1 < q12 ≤ n (da n nicht prim), sodass
m = n − p1 q1 > 0.
Wegen p1| n ist p1 ein Teiler von m und analog ist q1 ein Teiler von m. Nach I. V. und dem Existenzsatz kommen damit sowohl p1 als auch q1 in der eindeutigen kanonischen PFZ von m vor, sodass p1 q1 | m. Dann ist aber p1 q1 ein Teiler von n = m + p1 q1 und damit p1 ein Teiler von n/q1. Damit kommt p1 nach I. V. und dem Existenzsatz in der Darstellung
n/q1 = q1d1 − 1 … qk′dk′
vor, die wir aus (+) ablesen. Dies steht im Widerspruch zu p1 < q1.
Wir wollen das Ergebnis noch etwas anders formulieren. Hierzu definieren wir:
Definition (p-Exponent einer Zahl)
Sei p eine Primzahl. Dann definieren wir eine Funktion exp : ℕ* → ℕ durch
exp(n) = maxk ≥ 0 pk | n.
Die Zahl exp(n) heißt der p-Exponent der Zahl n.
Beispiel
Für n = 4400 = 24 · 52 · 11 gilt
ex2(n) = 4, ex5(n) = 2, ex11(n) = 1
und exp(n) = 0 für alle anderen Primzahlen p. Für alle p gilt zudem exp(1) = 0.
Der Leser beachte, dass in diesem Beispiel stillschweigend die Eindeutigkeit der Primfaktorzerlegung verwendet wird. Durch die Definition als Maximum ist klar, dass der p-Exponent für jede Zahl n definiert ist. Aber erst die Eindeutigkeit der PFZ erlaubt es, die p-Exponenten aus jeder PFZ einfach ablesen zu können.
Mit Hilfe der p-Exponenten können wir die Eindeutigkeit der Primfaktorzerlegung nun so formulieren:
n = ∏p prim pexp(n) für alle n ≥ 1.
Dabei ist das unendliche Produkt unproblematisch, da höchstens endlich viele Faktoren ungleich 1 sind; das unendliche Produkt ist damit lediglich eine einfache Notation für ein endliches Produkt.
Beispiel
4400 = 24 · 30 · 52 · 70 · 111 · 130 · 170 · 190 · …