Der Satz von Euklid besagt, 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."
Sein Beweis, der oft als "schön" oder "elegant" bezeichnet wird, beruht auf einer einfachen Widerspruchsüberlegung:
Angenommen, es gäbe nur endlich viele (insgesamt N) unterschiedliche Primzahlen P1, P2, ... PN.
Das Produkt dieser Primzahlen sei Z.
- Z = P1 × P2 × ... × PN
Die Zahl (Z + 1) ist dann durch keine der Primzahlen teilbar, da jede Division einen Rest von 1 liefert.
Jede nicht-Primzahl > 1 lässt sich aber durch eine Primzahl teilen: also ist (Z + 1) selbst eine Primzahl oder enthält zumindest bisher nicht aufgeführte Primfaktoren.
Diese Primzahl Z + 1 bzw. die neuen Primfaktoren sind aber verschieden von den Primzahlen P1, P2, ... PN. Da angenommen wurde, dies seien alle Primzahlen, ergibt sich ein Widerspruch. Die Annahme, es gäbe nur endlich viele Primzahlen, ist also unhaltbar.
Beispiele
- Angenommen, 2, 3, 5, 7 und 11 sind die einzigen Primzahlen. Dann berechnet man Z+1 = 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 Z+1 = 2*3*5*7*11*13 + 1 = 30031 = 59*509. 59 ist eine weitere Primzahl. Hier sieht man auch, dass Z+1 nicht immer selbst eine Primzahl sein muss.
- Angenommen, 2, 5 und 11 sind die einzigen Primzahlen. Dann berechnet man Z+1 = 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 Z+1 = 23+89 + 1 = 2048 = 2^12. 2 ist eine weitere Primzahl, die sogar kleiner ist, als beide angenommenen Primzahlen.
Es ist eine offene Frage, ob das Produkt der ersten n Primzahlen mit dem Bildungsgesetz für Z+1 unendlich viele Primzahlen oder unendlich viele zusammengesetzte Zahlen ergibt.
