Es gibt unendlich viele Primzahlen! Hier sind verständliche Beweise!

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.