Der Unendlichkeitssatz
Wir zeigen nun, dass es unendlich viele Primzahlen gibt. Zur Vorbereitung noch eine fast selbstverständliche Definition:
Definition (Primteiler oder Primfaktor)
Eine Primzahl p heißt Primteiler oder Primfaktor einer Zahl n, falls p | n.
Jede Zahl n ≥ 2 besitzt mindestens einen Primteiler. Denn das kleinste d ≥ 2 mit d | n ist notwendig eine Primzahl. Jede Primzahl hat nur einen Primteiler (sich selbst), aber auch die Zahlen p2, p3, …, pn, … mit einer Primzahl p haben nur einen Primteiler (dies folgt aus der Eindeutigkeit der Primfaktorzerlegung, die wir unten beweisen).
Nach diesen Vorbereitungen zeigen wir nun:
Satz (Satz von Euklid über die Unendlichkeit der Primzahlen)
Es gibt unendlich viele Primzahlen.
Beweis
Sei n ≥ 1 beliebig, und seien p1, …, pn Primzahlen. Wir zeigen, dass es eine Primzahl p gibt, die von allen Zahlen p1, …, pn verschieden ist. Hierzu setzen wir
a = p1 … pn + 1.
Die Zahl a besitzt für jedes k den Rest 1 bei Division durch pk, d. h.
a ≡ 1 (pk) für alle 1 ≤ k ≤ n.
Folglich gilt:
(+) Für alle 1 ≤ k ≤ n ist pk kein Teiler von a.
Sei nun p ein Primteiler von a. Nach (+) ist p von allen pk verschieden. Damit ist p eine Primzahl wie gewünscht.
Es ist verführerisch, die Zahl a selbst als eine „neue Primzahl“ anzusehen. Dies wird bestätigt durch
2 + 1 = 3
2 · 3 + 1 = 7
2 · 3 · 5 + 1 = 31
2 · 3 · 5 · 7 + 1 = 211
2 · 3 · 5 · 7 · 11 + 1 = 2311
Diese fünf Zahlen sind prim. Unser scheinbarer Primzahlgenerator wird aber überführt durch
2 · 3 · 5 · 7 · 11 · 13 + 1 = 30031 = 59 · 509
2 · 3 · 5 · 7 · 11 · 13 · 17 + 1 = 510511 = 19 · 97 · 277
2 · 3 · 5 · 7 · 11 · 13 · 17 · 19 + 1 = 9699691 = 347 · 27953
2 · 3 · 5 · 7 · 11 · 13 · 17 · 19 · 23 + 1 = 223092871 = 317 · 703763
Eine Primzahl p der Form p = 2 · 3 · 5 · … · pn + 1 heißt eine Euklidische Primzahl. Es ist ein offenes Problem, ob es unendlich viele Euklidische Primzahlen gibt. Ein sehr alter und klassischer Beweis wirft damit eine schwierige Frage auf. Wir stoßen auf sie fast zwangsläufig beim Durchdenken des Arguments und Experimentieren mit der Konstruktion.
Als Nächstes zeigen wir − mit der gleichen Beweisidee − als Kontrast, dass es beliebig große Sprünge in der Folge der Primzahlen gibt:
Satz (Intervalle zusammengesetzter Zahlen)
Es gibt beliebig lange Intervalle zusammengesetzter Zahlen.
Beweis
Sei n ≥ 2 beliebig, und seien p1, …, pn die ersten n Primzahlen. Wir setzen
q = p1 · … · pn.
Dann sind die pn − 1 Zahlen
q + 2, q + 3, q + 4, …, q + pn
zusammengesetzt. Denn sei a beliebig mit 2 ≤ a ≤ pn. Dann ist a durch ein pk teilbar, da jeder Primfaktor von a wegen a ≤ pn eine der Primzahlen p1, …, pn ist. Da q nach Konstruktion durch pk teilbar ist, ist auch q + a durch pk teilbar. Damit haben wir ein Intervall zusammengesetzter Zahlen der Länge pn − 1 gefunden. Da pn aufgrund der Unendlichkeit der Primzahlen beliebig groß gewählt werden kann, ist der Satz bewiesen.
Die beiden Beweise lassen sich so zusammenfassen: Multiplizieren wir die ersten Primzahlen auf, so besitzt die auf dieses Produkt folgende Zahl andere Primfaktoren und danach folgt ein langes Intervall zusammengesetzter Zahlen.
Beispiel
Für n = 8 erhalten wir
p1 … p8 = 2 · 3 · 5 · 7 · 11 · 13 · 17 · 19 = 9699690.
Damit sind 18 aufeinanderfolgenden Zahlen
9699690 + 2, …, 9699690 + 19
zusammengesetzt. Die Primfaktorzerlegungen sind:
9699690 + 2 = 22 · 109 · 22247 | 9699690 + 11 = 11 · 593 · 1487 |
9699690 + 3 = 3 · 3233231 | 9699690 + 12 = 2 · 3 · 1616617 |
9699690 + 4 = 2 · 113 · 167 · 257 | 9699690 + 13 = 13 · 263 · 2837 |
9699690 + 5 = 5 · 1939939 | 9699690 + 14 = 23 · 7 · 173209 |
9699690 + 6 = 24 · 33 · 22453 | 9699690 + 15 = 32 · 5 · 439 · 491 |
9699690 + 7 = 73 · 28279 | 9699690 + 16 = 2 · 761 · 6373 |
9699690 + 8 = 2 · 23 · 37 · 41 · 139 | 9699690 + 17 = 172 · 33563 |
9699690 + 9 = 3 · 79 · 40927 | 9699690 + 18 = 22 · 3 · 808309 |
9699690 + 10 = 22 · 52 · 96997 | 9699690 + 19 = 192 · 97 · 277 |
Die Konstruktion ist nicht optimal: In unserer Primzahltabelle folgt auf 1327 die 1361, sodass die 33 Zahlen 1328, …, 1360 zusammengesetzt sind.