Der Mathematiker Euklid von Alexandria gilt als erster, der den Beweis aufstellte, dass es unendlich viele Primzahlen gibt. Im Folgenden sei dieser Beweis durch Widerspruch erklärt:
Vorwissen:
- Es gibt unendlich viele natürliche Zahlen.
- Jede natürliche Zahl ist entweder eine Primzahl oder eine zusammengesetzte Zahl.
- Jede natürliche Zahl lässt sich mit Primfaktoren darstellen (z. B. 10 = 2 · 5 oder 7 = 7).
Annahme:
„Es gibt endlich viele Primzahlen.“
Folglich müsste eine größte Primzahl existieren.
Bezeichnen wir diese angenommene größte Primzahl mit n.
Listen wir unter dieser Annahme alle Primzahlen bis zur größten Primzahl n auf:
2, 3, 5, 7, 11, 13, …, n
Die Zahl n wäre also die letzte und damit größte Primzahl. Eine weitere, größere Primzahl würde es also nicht geben.
Widerspruchsbeweis
Würden wir eine weitere Primzahl finden, die größer als die Primzahl n ist, dann wäre die Aussage falsch, und es würde weitere Primzahlen geben (ein Widerspruch).
Prüfen wir das und multiplizieren wir im ersten Schritt alle Primzahlen miteinander:
2 · 3 · 5 · 7 · 11 · 13 · … · n
Das ergibt eien Zahl, die viel größer ist als die „größte“ Primzahl n.
Im zweiten Schritt addieren wir eine +1 hinzu, die sich ergebende Zahl nennen wir z:
z = (2 · 3 · 5 · 7 · 11 · 13 · … · n) + 1
Diese neue Zahl z ist ungleich aller Primfaktoren (Primzahlen) der Zahl n.
Weiterhin ist festzustellen, dass diese neue Zahl z laut der Annahme keine Primzahl sein darf, sondern eine zusammengesetzte Zahl sein muss. Andernfalls hätten wir ja eine noch größere Primzahl als die Primzahl n und die Annahme wäre falsch.
Damit z jedoch eine zusammengesetzte Zahl ist, muss die Zahl z durch mindestens einen der Primfaktoren von Zahl n teilbar sein (sonst wäre sie nicht zusammengesetzt). Oder anders gesagt: Jede zusammengesetzte Zahl lässt sich in Primfaktoren zerlegen.
Nennen wir einen dieser Primfaktoren von Zahl z allgemein p.
Wenn wir die Zahl z durch p teilen, so bleibt jedoch stets der Rest 1. (Diesen hatten wir mit +1 erzeugt.)
z:p = \( \frac{ (2\,·\,3\,·\,5\,·\,7\,·\,11\,·\,13\,·\,…\,·\,p\,·\,…\,·\,n) + 1 }{ p } \)
z:p = \( \frac{ (2\,·\,3\,·\,5\,·\,7\,·\,11\,·\,13\,·\,…\,·\,p\,·\,…\,·\,n) }{ p } \) + \( \frac{1}{p} \)
z:p = (2 · 3 · 5 · 7 · 11 · 13 · … · n) + Rest 1
Da sich ein Rest ergibt, teilt also keiner der Primfaktoren aus der Auflistung die Zahl z restlos.
Die Zahl z muss also einen „neuen“ Teiler bzw. Primfaktor in sich haben, der noch nicht bei der Zahl z vorgekommen ist. Denn jede natürliche Zahl lässt sich mit Primfaktoren darstellen.
Es gibt also eine Primzahl, die noch nicht in der Auflistung der Primzahlen enthalten war!
Das widerspricht jedoch der Annahme, dass wir alle Primzahlen bis zur größten Primzahl n aufgelistet haben.
Es gibt folglich noch weitere - und zwar unendlich viele - Primzahlen. ✓
Im Folgenden ist der Widerspruchsbeweis noch mal zusammengefasst:
- Die gebildete Zahl z ist entweder eine Primzahl oder eine zusammengesetzte Zahl.
- Primzahl darf sie laut Annahme nicht sein, also müsste sie eine zusammengesetzte Zahl sein.
- Wäre sie eine zusammengesetzte Zahl, dann würden wir für ihre Primfaktordarstellung jedoch eine neue Primzahl benötigen, da keine der Primzahlen der Zahl n enthalten ist (da immer Rest 1).
- Dies widerspricht jedoch der Annahme, dass wir alle Primzahlen aufgezählt haben und es eine größtmögliche Primzahl gibt.
- Daher kann es keine größte Primzahl geben. Stattdessen gibt es unendlich viele Primzahlen.
Beispiele
Es seien hier noch die zwei Möglichkeiten mit Beispielen dargestellt, dass sich entweder eine Primzahl oder eine zusammengesetzte Zahl ergibt.
Beispiel A:
(2 · 3 · 5 · 7 · 11) + 1 = 2 310 + 1 = 2 311
Die Zahl 2 311 hat keine Teiler, es ist eine Primzahl.
Beispiel B:
(2 · 3 · 5 · 7 · 11 · 13) + 1 = 30 030 + 1 = 30 031
Die Zahl 30 031 hat die Teiler 59 · 509. Sie ist eine zusammengesetzte Zahl.