Beweisarchiv: Zahlentheorie: Elementare Zahlentheorie: Satz von Euklid

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 EuklidBearbeiten

AussageBearbeiten

Es gibt unendlich viele Primzahlen.

Konstruktive BeweiseBearbeiten

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 zeigenBearbeiten

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 BeweisBearbeiten

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 BeweiseBearbeiten

Eulerprodukt für die harmonische ReiheBearbeiten

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-VerweiseBearbeiten