Der Satz von Euklid besagt, dass es keine größte Primzahl gibt. Dies ist identisch mit der Aussage, dass es unendlich viele Primzahlen gibt.
Dieser Satz geht auf den griechischen Mathematiker Euklid zurück, der um 300 v. Chr. in Alexandria lebte. In seinem Werk die "Elemente" schreibt er im Buch IX: "Es gibt mehr Primzahlen als jede vorgelegte Anzahl von Primzahlen."
Beweis
Der Beweis, der oft als "schön" oder "elegant" bezeichnet wird, beruht auf einem einfachen Widerspruch:
Annahme: Es gibt nur endlich viele paarweise verschiedene Primzahlen p0, p1, ..., pr.
Dann existiert eine Zahl n∈N, die sich wie folgt berechnen lässt:
Diese Zahl n ist dann durch keine der Primzahlen p0, p1, ..., pr teilbar, da jede Division einen Rest von 1 liefert. Die Zahl n ist also selbst eine Primzahl oder enthält zumindest bisher nicht aufgeführte Primfaktoren. Diese Primzahl n bzw. deren neuen Primfaktoren sind aber verschieden von den Primzahlen p0, p1, ..., pr. Da angenommen wurde, dies seien alle Primzahlen, ergibt sich ein Widerspruch. Die Annahme, es gäbe nur endlich viele Primzahlen, ist also falsch.
Beispiele
- Angenommen, 2, 3, 5, 7 und 11 sind die einzigen Primzahlen. Dann berechnet man n = 2*3*5*7*11 + 1 = 2311. 2311 ist eine weitere Primzahl.
- Angenommen, 2, 3, 5, 7, 11 und 13 sind die einzigen Primzahlen. Dann berechnet man n = 2*3*5*7*11*13 + 1 = 30031 = 59*509. 59 ist eine weitere Primzahl. Hier sieht man auch, dass n nicht immer selbst eine Primzahl sein muss.
- Angenommen, 2, 5 und 11 sind die einzigen Primzahlen. Dann berechnet man n = 2*5*11 + 1 = 111 = 3*37. 3 ist eine weitere Primzahl, die nicht größer als die angenommenen Primzahlen ist.
- Angenommen, 23 und 89 sind die einzigen Primzahlen. Dann berechnet man n = 23*89 + 1 = 2048 = 2^11. 2 ist eine weitere Primzahl, die sogar kleiner ist, als beide angenommenen Primzahlen.
Es ist eine offene Frage, ob das Produkt der ersten r Primzahlen mit dem Bildungsgesetz für n unendlich viele Primzahlen oder unendlich viele zusammengesetzte Zahlen ergibt.