Hauptmenü öffnen

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).

Inhaltsverzeichnis

Beweis von EuklidBearbeiten

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

Angenommen, es gäbe nur endlich viele Primzahlen  . 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   bezeichnen. Nun gibt es zwei Möglichkeiten:

  •   ist eine Primzahl: Sie ist dann nach Konstruktion größer als   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   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,[1] so wie auch an anderen Stellen des Werkes „Die Elemente“ drei Objekte im heutigen Sinne von „beliebig viele Objekte“ verwendet wird.

AnwendungBearbeiten

Der Beweis des Satzes von Euklid zeigt eine Möglichkeit auf, wie aus einer oder mehreren vorgegebenen Primzahlen   (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

 .

Wegen   gibt es einen kleinsten Teiler   von  . Dieser ist notwendigerweise eine Primzahl. Ferner ist   teilerfremd[2] zu und damit verschieden von jeder der vorgegebenen Zahlen  .

Zieht man nur Mengen von aufeinander folgenden Primzahlen in Betracht, also  , und bildet daraus die Zahlen

 ,

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

 .

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

BeispieleBearbeiten

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

 .

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

 ,

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

 ,

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

Die Menge der Zahlen sei  . Die Formel ergibt die Zahl

 ,

deren kleinster Teiler   eine Primzahl ist, und zwar die Fermatsche Primzahl  .

Siehe auchBearbeiten

WeblinksBearbeiten

 Wikibooks: Beweis zum Satz von Euklid – Im Beweisarchiv auf Wikibooks finden sich weitere Beweise für die Existenz von unendlich vielen Primzahlen.

EinzelnachweiseBearbeiten

  1. Die Elemente, Buch IX, Proposition 20
  2. Mit   und   ist  . Ist nun   ein gemeinsamer Teiler von   und  , also   und  , dann ist  , also   ein Teiler von 1. Damit ist  für  .