Satz von Euklid

Der Satz von Euklid besagt, dass es keine größte Primzahl gibt. Dies ist identisch mit der Aussage, 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" schreibt er im Buch IX: "Es gibt mehr Primzahlen als jede vorgelegte Anzahl von Primzahlen.".

Beweis

Der Beweis, der oft als schön oder elegant bezeichnet wird, beruht auf einem einfachen Widerspruch:

Annahme: Es gibt nur endlich viele paarweise verschiedene Primzahlen p₁, p₂, ..., p_r.

Dann existiert eine Zahl $n\in\mathbb{N}$ , die sich wie folgt berechnen lässt:

$n = 1 + p_1 \cdot p_2 \cdot ... \cdot p_r = 1 + \prod_{i=1}^r p_i$

Diese Zahl $n$ ist dann durch keine der Primzahlen p₁, p₂, ..., p_r teilbar, da jede Division einen Rest von 1 liefert. Die Zahl $n$ ist also selbst eine Primzahl oder enthält zumindest bisher nicht aufgeführte Primfaktoren. Diese Primzahl n bzw. deren neue Primfaktoren sind aber verschieden von den Primzahlen p₁, p₂, ..., p_r. Da angenommen wurde, dies seien alle Primzahlen, ergibt sich ein Widerspruch. Die Annahme, es gäbe nur endlich viele Primzahlen, ist also falsch.

Beispiele

Angenommen, 2, 3, 5, 7 und 11 sind die einzigen Primzahlen. Dann berechnet man n = 2*3*5*7*11 + 1 = 2311.

2311 ist eine weitere Primzahl.

Angenommen, 2, 3, 5, 7, 11 und 13 sind die einzigen Primzahlen. Dann berechnet man n = 2*3*5*7*11*13 + 1 = 30031 = 59*509.

59 ist eine weitere Primzahl. Hier sieht man auch, dass n nicht immer selbst eine Primzahl ist.

Angenommen, 2, 5 und 11 sind die einzigen Primzahlen. Dann berechnet man n = 2*5*11 + 1 = 111 = 3*37.

3 ist eine weitere Primzahl, die nicht größer als die angenommenen Primzahlen ist.

Angenommen, 23 und 89 sind die einzigen Primzahlen. Dann berechnet man n = 23*89 + 1 = 2048 = 2^11.

2 ist eine weitere Primzahl, die sogar kleiner ist als beide angenommenen Primzahlen.

Es ist eine offene Frage, ob das Produkt der ersten r Primzahlen mit dem Bildungsgesetz für n unendlich viele Primzahlen oder unendlich viele zusammengesetzte Zahlen ergibt.

Euklid Kategorie:Zahlentheorie

Satz von Euklid

Beweis

Beispiele

See also: Satz von Euklid, 300 v. Chr., Alexandria, Division mit Rest, Euklid, Euklids Elemente, Primzahl, Teilbarkeit, Unendlichkeit