Satz von Euklid

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 schrieb er: „Es gibt mehr Primzahlen als jede vorgelegte Anzahl von Primzahlen“ (Buch IX, Proposition 20).

Beweis von Euklid

Euklid verwendete einen Widerspruchsbeweis, um die Aussage des Satzes zu beweisen.

Angenommen, es gäbe nur endlich viele Primzahlen $p_1, \ldots, p_n$ . Es sei die kleinste Zahl, die von allen diesen Zahlen geteilt wird (also das Produkt aller dieser Zahlen). Betrachten wir nun den Nachfolger von , den wir als m+1 bezeichnen. Nun gibt es zwei Möglichkeiten:

ist eine Primzahl: Sie ist dann nach Konstruktion größer als $p_1, \ldots, p_n$ und somit eine weitere Primzahl im Widerspruch zur Annahme.
ist keine Primzahl: Sie muss daher einen Primteiler besitzen. Nach Annahme muss dann eine der Primzahlen $p_1, \ldots, p_n$ sein. Also muss sowohl von als auch von ein Teiler sein. Die einzige Möglichkeit für solch ein wäre , was jedoch keine Primzahl ist. Daraus ergibt sich der Widerspruch.

Die Annahme, es gäbe nur endlich viele Primzahlen, ist also falsch. Euklid führte den Beweis im Übrigen mit nur drei Primzahlen, so wie auch an anderen Stellen des Werkes „Die Elemente“ drei Objekte im heutigen Sinne von „beliebig viele Objekte“ verwendet wird.

Anwendung

Der Beweis des Satzes von Euklid zeigt eine Möglichkeit auf, wie aus einer oder mehreren vorgegebenen Primzahlen $p_{1},p_{2},\dotsc ,p_{r}$ (oder auch nur natürlichen Zahlen ) mindestens eine weitere Primzahl berechnet werden kann. Dazu bildet man das Produkt dieser Zahlen und addiert 1 zu dem Produkt, also

$n:=p_{1}p_{2}\dotsm p_{r}+1=\prod _{i=1}^{r}p_{i}+1$ .

Wegen $n>1$ gibt es einen kleinsten Teiler $d>1$ von . Dieser ist notwendigerweise eine Primzahl. Ferner ist teilerfremd ^[1] zu und damit verschieden von jeder der vorgegebenen Zahlen $p_{i}$ .

Zieht man nur Mengen von aufeinander folgenden Primzahlen in Betracht, also $p_{1}=2,p_{2}=3,p_{3}=5,\dotsc$ , und bildet daraus die Zahlen

$P_{r}:=2\cdot 3\dotsm p_{r}+1=\prod _{i=1}^{r}p_{i}+1$ ,

dann stellen sich die ersten fünf dieser Zahlen als prim heraus, die nächsten fünf als zusammengesetzt. Beispielsweise ist

$P_{6}=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13+1=30031=59\cdot 509$ .

Es ist eine offene Frage, ob es unter diesen Zahlen unendlich viele Primzahlen, unendlich viele zusammengesetzte Zahlen oder beides gibt.

Beispiele

Die Zahlen 2, 5 und 11 bilden eine endliche Menge von Primzahlen. Gemäß obiger Formel berechnet sich zu

$n = 1 + 2 \cdot 5 \cdot 11 = 111 = 3 \cdot 37$ .

Sowohl 3 als auch 37 sind weitere Primzahlen. Anhand der 3 ist zu sehen, dass auch Primzahlen gefunden werden können, die nicht größer als die vorgegebenen Primzahlen sind.

Die Zahlen 2, 3, 5, 7 und 11 bilden eine endliche Menge von Primzahlen. Gemäß obiger Formel berechnet sich zu

$n=P_{5}=1+2\cdot 3\cdot 5\cdot 7\cdot 11=2311$ ,

welches eine weitere Primzahl ist. Hier zeigt sich, dass schon das Ergebnis selbst eine Primzahl sein kann.

Die Zahlen 23 und 89 bilden eine endliche Menge von Zahlen. Gemäß obiger Formel ergibt sich

$n = 1 + 23 \cdot 89 = 2048 = 2^{11}$ ,

eine Zahl, deren kleinster Teiler $>1$ die Primzahl 2 ist, kleiner ist als die beiden vorgegebenen Zahlen.

Die Menge der Zahlen sei $\{2^{16}\}=\{65536\}$ . Die Formel ergibt die Zahl

$n=65536+1=65537$ ,

deren kleinster Teiler $>1$ eine Primzahl ist, und zwar die Fermatsche Primzahl $F_{4}=65537$ .

Siehe auch

Größte bekannte Primzahl

Anmerkung

↑ Mit $s:=n/d$ und $t:=-(n-1)/p_{i}$ ist $sd+tp_{i}=1$ . Ist nun $c\in \mathbb {Z}$ ein gemeinsamer Teiler von und $p_{i}$ , also $d=d^{\prime }c$ und $p_{i}=p^{\prime }c$ , dann ist $1=sd^{\prime }c+tp^{\prime }c=(sd^{\prime }+tp^{\prime })\,c=1$ , also ein Teiler von 1. Damit ist $\operatorname {ggT} (d,p_{i})=1$ für $i=1,\dotsc ,r$ .

Basierend auf einem Artikel in:

Wikipedia.de