Es gibt unendlich viele Primzahlen.
Hier finden Sie die Beweise und erläuternde Beispiele:
Euklids Beweis der Unendlichkeit der Primzahlen
Der Beweis von Euklid ist ein klassischer Widerspruchsbeweis oder ein Reductio ad absurdum.
Dabei wird angenommen, es gäbe nur endlich viele Primzahlen. Also gibt es auch eine größte Primzahl . Nun bildet man das Produkt aller Primzahlen, das aufgrund der Definition durch alle Primzahlen von
bis
teilbar ist:
Die Zahl ist durch keine der Zahlen von
bis
teilbar.
Daraus folgt, daß die Zahl selbst eine neue Primzahl oder ein Produkt von mehreren unbekannten Primzahlen ist.
Dies ist ein Widerspruch zu der Annahme, daß es endlich viele Primzahlen gibt.
Beispiel zu Euklids Beweis der Unendlichkeit der Primzahlen
Angenommen, ist die größte Primzahl. Dann ist das aber
das Produkt von den Primzahlen 59 und 509, die beide größer als 13 sind.
Stieltjes Beweis der Unendlichkeit der Primzahlen
Der Beweis von Stieltje ist eine Verallgemeinerung des Euklidschen Beweises ().
Aus den einzig existierenden Primzahlen läßt sich die Zahl
konstruieren, die sich in der Form
zerlegen läßt. Für
und
gilt, daß sie echt größer als 1 sind und jede Primzahl
oder
teilt, aber keinesfalls beide gleichzeitig. Daher ist auch die Summe
nicht durch eine der existierenden Primzahlen teilbar. Weil
echt größer als 1 ist, ist
eine weitere größere Primzahl oder durch eine weitere unbekannte Primzahl teilbar.
Beispiel zu Stieltjes Beweis der Unendlichkeit der Primzahlen
Angenommen wird nun, daß es nur die ersten vier Primzahlen 2,3,5 und 7 gibt. Dann ist und läßt sich in die Faktoren 15 (=3*5) und 14 (=2*7) zerlegen. Die Summe
läßt sich durch keine der Zahlen 2,3,4 und 7 teilen. Daher ist 29 eine Primzahl (ja!) oder durch zwei Primzahlen teilbar.