Satz von Euklid - LinkFang.de





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 [math]p_1, \ldots, p_n[/math]. Es sei [math]m[/math] die kleinste Zahl, die von allen diesen Zahlen geteilt wird (also das Produkt aller dieser Zahlen). Betrachten wir nun den Nachfolger von [math]m[/math], den wir als [math]m+1[/math] bezeichnen. Nun gibt es zwei Möglichkeiten:

  • [math]m+1[/math] ist eine Primzahl: Sie ist dann nach Konstruktion größer als [math]p_1, \ldots, p_n[/math] und somit eine weitere Primzahl im Widerspruch zur Annahme.
  • [math]m+1[/math] ist keine Primzahl: Sie muss daher einen Primteiler [math]q[/math] besitzen. Nach Annahme muss [math]q[/math] dann eine der Primzahlen [math]p_1, \ldots, p_n[/math] sein. Also muss [math]q[/math] sowohl von [math]m[/math] als auch von [math]m+1[/math] ein Teiler sein. Die einzige Möglichkeit für solch ein [math]q[/math] wäre [math]1[/math], 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

Der Beweis des Satzes von Euklid zeigt eine Möglichkeit auf, wie aus einer oder mehreren vorgegebenen Primzahlen mindestens eine weitere Primzahl berechnet werden kann. Dazu berechnet man das Produkt dieser Primzahlen und addiert 1 zu dem Produkt:

[math]n = 1 + p_1 \cdot p_2 \cdots p_r = 1 + \prod_{i=1}^r p_i[/math]

Anschließend berechnet man die Primfaktorzerlegung der so gewonnenen Zahl [math]n[/math]. Alle Primfaktoren sind dann Primzahlen, die in der ursprünglichen Primzahlmenge nicht enthalten waren.

Es ist eine offene Frage, ob es unter den Zahlen der Form [math]2 \cdot 3 \cdot 5 \cdot 7 \cdots p + 1[/math] mit [math]p[/math] prim, 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 [math]n[/math] zu

[math]n = 1 + 2 \cdot 5 \cdot 11 = 111 = 3 \cdot 37[/math].

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 [math]n[/math] zu

[math]n = 1 + 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 = 2311[/math]

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

Die Zahlen 23 und 89 bilden eine endliche Menge von Primzahlen. Gemäß obiger Formel berechnet sich [math]n[/math] zu

[math]n = 1 + 23 \cdot 89 = 2048 = 2^{11}[/math].

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

Weblinks

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

Einzelnachweise

  1. Die Elemente, Buch IX, Proposition 20

Kategorien: Euklid | Primzahl | Satz (Mathematik)

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Satz von Euklid (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.