Beweisarchiv: Zahlentheorie: Elementare Zahlentheorie: Satz von Euklid

Aus Wikibooks

Beweisarchiv: Zahlentheorie

Elementare Zahlentheorie: Kleiner Satz von Fermat · Satz von Euklid · Satz von Wilson · Vollständige Multiplikativität der p-adischen Exponentenbewertung
Algebraische Zahlentheorie: Pythagoraszahl nicht-reeller Körper · Korrespondenzsatz der algebraischen Zahlentheorie · Zerlegungsgesetz
Analytische Zahlentheorie: Irrationalität von · Primzahlsatz


Satz von Euklid[Bearbeiten]

Aussage[Bearbeiten]

Es gibt unendlich viele Primzahlen.

Konstruktive Beweise[Bearbeiten]

Die folgenden Beweise sind konstruktiv in dem Sinne, dass sie ein Verfahren angeben, mit dem sich beliebig viele Primzahlen finden lassen.

Beweis von Euklid (300 v. Chr.)[Bearbeiten]

Euklid geht von einer endlichen Menge von Primzahlen aus und bildet die Zahl

Diese Zahl ist durch keine der Primzahlen teilbar, da immer ein Rest 1 verbleibt. Damit sind die Primfaktoren von nicht in der Ausgangsmenge enthalten, man kann also zu jeder endlichen Menge von Primzahlen eine weitere hinzufügen. Mit dieser Formulierung umging Euklid geschickt den Begriff des Unendlichen, wenngleich seine damalige Formulierung "zu jeder endlichen Liste von Primzahlen lässt sich eine weitere hinzufügen" äquivalent zu der Aussage ist, dass es unendlich viele Primzahlen gibt.

Hinweis: Die Zahl ist nicht notwendigerweise selber eine Primzahl, siehe etwa

Beweise, die die Existenz unendlich vieler paarweise teilerfremder Zahlen zeigen[Bearbeiten]

Es gibt verschiedene Beweise, die alle auf demselben Prinzip aufbauen: Ist eine Menge natürlicher Zahlen, die größer als 1 sind und von denen je zwei teilerfremd sind, d. h. deren größter gemeinsamer Teiler 1 ist, so erhält man durch die Faktorisierung dieser Zahlen eine Menge von Primzahlen, die mindestens so viele Elemente wie besitzt. Denn natürliche Zahlen größer als 1 haben mindestens einen Primfaktor, und die Teilerfremdheit stellt sicher, dass verschiedene Zahlen auch verschiedene Primzahlen liefern.

Um zu beweisen, dass es unendlich viele Primzahlen gibt, genügt es also, eine unendliche Menge paarweise teilerfremder natürlicher Zahlen anzugeben, oder verschiedene endliche Mengen paarweiser teilerfremder natürlicher Zahlen, deren Größe jedoch unbeschränkt ist.

Goldbachs Beweis (1730)[Bearbeiten]

Es sei für die Folge der Fermat-Zahlen. Es gilt

Diese Aussage lässt sich beispielsweise mit vollständiger Induktion zeigen. Daraus folgt für , dass die Zahl teilt. Damit folgt

Da aber die Fermat-Zahlen alle ungerade sind, ist dieser ggT gleich 1, d. h. je zwei Fermat-Zahlen sind teilerfremd. Die Folge ist offenbar streng monoton steigend, also enthält sie unendlich viele verschiedene Glieder, und mit dem obigen Argument folgt die Existenz unendlich vieler Primzahlen.

Schorns Beweis[Bearbeiten]

Wähle eine natürliche Zahl . Die natürlichen Zahlen für sind paarweise teilerfremd, denn wenn eine Primzahl die beiden Zahlen und teilt, dann teilt auch die Differenz , die nur Primfaktoren besitzt. Also ist . Andererseits ist durch alle Zahlen und somit durch teilbar, also wären zwei aufeinanderfolgende Zahlen durch teilbar: Widerspruch. Somit sind die Zahlen für paarweise teilerfremd, und nach der obigen Überlegung gibt es folglich mindestens Primzahlen. Da beliebig gewählt war, gibt es unendlich viele Primzahlen.

Stieltjes’ Beweis (1890)[Bearbeiten]

Angenommen, seien die einzigen Primzahlen, die existieren. Dann kann man die Zahl

auf verschiedene Arten in der Form zerlegen. Jede Primzahl teilt entweder oder , aber nicht beide zugleich. Aus diesem Grund ist durch keine der existierenden Primzahlen teilbar (einer der Summanden und ist jeweils teilerfremd zu der Primzahl und somit ein Rest). Da aber ist, ist eine weitere, größere Primzahl oder durch eine weitere noch unbekannte Primzahl teilbar.

Anmerkung: Im Spezialfall ist dies genau Euklids Beweis.

Nichtkonstruktive Beweise[Bearbeiten]

Eulerprodukt für die harmonische Reihe[Bearbeiten]

Als Motivation betrachten wir das Produkt

Die Nenner der auftretenden Brüche sind gerade diejenigen Zahlen, in denen der Primfaktor 2 höchstens dreimal und der Primfaktor 3 höchstens zweimal enthalten ist und die sonst durch keine anderen Primzahlen teilbar sind. Jeder solche Bruch tritt genau einmal auf. Würde man im ersten Faktor noch hinzufügen, kämen diejenigen Zahlen hinzu, die den Primfaktor 2 viermal enthalten.

Geht man zum entsprechenden Grenzwert über, erhält man die Aussage:

ist gleich der Summe der Kehrwerte aller natürlichen Zahlen, die keine anderen Primfaktoren als 2 und 3 enthalten.

Die Reihen in den Klammern sind geometrische Reihen und haben jeweils einfach angebbare Werte:

Die obige Rechnung funktioniert auch für mehr als zwei Primzahlen: Ist eine beliebige endliche Menge von Primzahlen, so ist das Produkt

gleich der Summe der Kehrwerte aller natürlichen Zahlen, die durch keine anderen Primzahlen als teilbar sind.

Wären nun bereits alle Primzahlen, so wäre die Zahl also gleich der Summe der Kehrwerte aller natürlichen Zahlen, also gleich der harmonischen Reihe

Diese Reihe ist aber bekanntlich divergent und somit nicht gleich der endlichen Zahl : Widerspruch.

Anmerkung: Die Überlegung liefert allgemein eine Produktdarstellung

Die linke Seite wird für als riemannsche Zetafunktion bezeichnet, die rechte Seite als Eulerprodukt.

Wikipedia-Verweise[Bearbeiten]