Unendlichkeit der Primzahlen

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 p_n. Nun bildet man das Produkt aller Primzahlen, das aufgrund der Definition durch alle Primzahlen von p_1 bis p_n teilbar ist:

    \[p=\prod_{i=0}^np_i = p_1\cdot p_2\cdot \ldots \cdot p_n\]

Die Zahl p+1 ist durch keine der Zahlen von p_1 bis p_n teilbar.
Daraus folgt, daß die Zahl p 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, p_n=13 ist die größte Primzahl. Dann ist das aber 2*3*5*7*11*13 +1 = 30031 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 (n=1).
Aus den einzig existierenden Primzahlen p_1,\ldots,p_n läßt sich die Zahl N=p_1\cdotp_2\cdot \ldots \cdot p_n konstruieren, die sich in der Form N= m\cdot n zerlegen läßt. Für m und n gilt, daß sie echt größer als 1 sind und jede Primzahl p_i m oder n teilt, aber keinesfalls beide gleichzeitig. Daher ist auch die Summe m+n nicht durch eine der existierenden Primzahlen teilbar. Weil m+n echt größer als 1 ist, ist m+n 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 N=2*3*5*7=210 und läßt sich in die Faktoren 15 (=3*5) und 14 (=2*7) zerlegen. Die Summe 15+14=29 läßt sich durch keine der Zahlen 2,3,4 und 7 teilen. Daher ist 29 eine Primzahl (ja!) oder durch zwei Primzahlen teilbar.