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]

In heutiger Sprechweise stellt Euklid die folgende Behauptung auf:

Gegeben sei eine endliche Menge von Primzahlen Dann gibt es mindestens eine weitere Primzahl die nicht in enthalten ist.

Dazu bildet Euklid das kleinste Vielfache aller Primzahlen aus (Es ist für den Beweis nicht wichtig, dass das kleinste Vielfache ist; wichtig ist jedoch, dass alle bisherigen Primzahlen Teiler von sind.)
Dann bildet er und unterscheidet zwei Fälle:

  1. ist Primzahl, dann ist eine weitere Primzahl.
  2. ist keine Primzahl, dann hat einen Primteiler Angenommen, es wäre dann wäre ein Teiler von Es ist aber auch Teiler von und müsste folglich auch Teiler sein von der Differenz Ein Widerspruch!

Der Beweis kommt auch ohne die Fallunterscheidung aus:

Keiner der gegebenen Primteiler von ist Teiler von denn sonst müsste auch Teiler der Differenz sein, was für Primzahlen nicht geht, da sie definitionsgemäß sind.
Wenn man aber alle Zahlen also auch in Primfaktoren zerlegen kann, dann muss es über die hinaus weitere Primzahlen geben.

In allen Fällen führt das beschriebene Verfahren zur Entdeckung mindestens einer neuen Primzahl, unabhängig von der Menge der Primzahlen, mit der man den Beweis beginnt, solange diese Menge nur endlich ist. Euklid führte den Beweis mit nur drei Primzahlen,[1] so wie auch an anderen Stellen des Werkes „Die Elemente“ drei Objekte im heutigen Sinne von „beliebig, aber endlich viele Objekte“ verwendet wird.

Dass der Satz von Euklid (nicht unbedingt Euklids Beweis des Satzes von Euklid) als geradezu klassisches Beispiel eines Widerspruchsbeweises angesehen wird, kommt wohl von der Formulierung:

Behauptung: Es gibt unendlich viele Primzahlen.
Beweis: Angenommen, die Menge der Primzahlen wäre endlich (abgesehen vom Konjunktiv entspricht diese Annahme genau dem Ausgangspunkt von Euklids Beweis). Man kann immer mindestens eine Primzahl konstruieren, die nicht in der endlichen Menge ist. Das Angenommene muss also falsch sein.

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 .