Satz von Euklid

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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[Bearbeiten | Quelltext bearbeiten]

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.

Anwendung[Bearbeiten | Quelltext bearbeiten]

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.

Beispiele[Bearbeiten | Quelltext bearbeiten]

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 auch[Bearbeiten | Quelltext bearbeiten]

Weblinks[Bearbeiten | Quelltext bearbeiten]

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

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  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 .