Satz des Euklid
Der Satz des Euklid, manchmal auch Satz von Euklid, ist ein Lehrsatz aus der elementaren Zahlentheorie und besagt, dass es unendlich viele Primzahlen gibt. Benannt ist er nach Euklid von Alexandria, der ihn als Erster im dritten Jahrhundert v. Chr. in seinen Elementen bewies. Jedoch kannten die Mathematiker der Antike das Konzept der Unendlichkeit noch nicht. Euklid selbst formulierte den Satz daher wie folgt: „Es gibt mehr Primzahlen als jede vorgelegte Anzahl von Primzahlen.“

Eine Primzahl ist eine ganze Zahl größer als 1, die nur durch 1 und sich selbst ohne Rest teilbar ist. Die ersten Primzahlen sind 2, 3, 5 und 7. Der Satz des Euklid besagt, dass die Liste 2, 3, 5, 7, 11, 13, 17… aller Primzahlen nicht endet, genauso wie die Liste 1, 2, 3, 4, 5, 6 … aller natürlichen Zahlen nicht endet.

Der ursprüngliche von Euklid geführte Beweis ist direkt und konstruktiv. Zu einer gegebenen endlichen Liste von Primzahlen wird stets eine weitere noch nicht vorhandene Primzahl erzeugt, ohne diese jedoch explizit anzugeben. Vielmehr wird argumentiert, dass jede endliche Liste von Primzahlen unvollständig ist. Daraus wird gefolgert, dass es unendlich viele Primzahlen gibt. In der späteren Literatur wird oft fälschlicherweise behauptet, dass Euklids Argument anhand eines Widerspruchsbeweises aufgeführt sei. Jedoch lässt sich der Beweis leicht zu einem Widerspruchsbeweis umformulieren.

Nach dem Fundamentalsatz der Arithmetik können alle natürlichen Zahlen größer als 1 eindeutig in Primfaktoren zerlegt werden. Der Satz des Euklid ist daher eines der grundlegendsten Resultate der Zahlentheorie, da er zeigt, dass es unendlich viele unzerlegbare Grundbausteine der Zahlen gibt. Im Laufe der Zeit wurden neben Euklids Originalbeweis zahlreiche andere Beweise gefunden, die teilweise mathematische Techniken aus der Analysis, Kombinatorik oder auch der Topologie nutzen. Ab dem 19. Jahrhundert konnten zudem mit den Beweisen des Dirichletschen Primzahlsatzes und des Primzahlsatzes weitreichende Verallgemeinerungen erzielt werden. Während der Satz des Euklid lediglich aussagt, dass die Anzahl der Primzahlen unendlich groß ist, formulieren die modernen Primzahlsätze Regeln, wie häufig Primzahlen in gewissen Bereichen ungefähr anzutreffen sind.

Analoge Fragestellungen hinsichtlich der Häufigkeit von Primzahlzwillingen, Mersenne-Primzahlen oder Fermat-Primzahlen verbleiben bis heute unbeantwortet.

Beweis von Euklid 
Der Satz wurde erstmals in Euklids Elementen im neunten Buch, Proposition 20, niedergeschrieben.

Originalformulierung 
Euklids Ausführung kann wie folgt ins Deutsche übersetzt werden:

Erläuterungen: Zu jeder endlichen Menge von Primzahlen (gegebenes Objekt) gibt es danach eine Primzahl (gesuchtes Objekt), die dieser Menge nicht angehört. Euklid beweist dies konstruktiv, indem er ein Verfahren beschreibt, aus gegebenen endlich vielen Primzahlen  (Euklid behandelt hier den Fall ) eine neue Primzahl zu gewinnen, indem man die Zahl  bildet und einen ihrer Primfaktoren bestimmt. Im Beweis wird geometrisch-anschaulich argumentiert, indem gesagt wird, dass eine Strecke (Zahl) eine andere „misst“, wenn letztere durch erstere teilbar ist. In Euklids Ausführungen geht ferner sein bereits in Buch VII, Proposition 31 (die lautet: Jede zusammengesetzte Zahl wird von irgendeiner Primzahl gemessen) beschriebenes Verfahren zur effektiven Gewinnung eines Primfaktors einer vorgegebenen Zahl als „Unterprogramm“ ein. Da Euklid im Originalwerk keine Möglichkeit hatte, eine willkürliche Liste von Primzahlen zu schreiben, verwendete er eine Methode, die er häufig anwandte, nämlich die Methode des verallgemeinerbaren Beispiels. Dabei wählt er nur drei Primzahlen aus und beweist mit der oben skizzierten allgemeinen Methode, dass er immer eine zusätzliche Primzahl finden kann. Euklid ging vermutlich davon aus, dass seine Leser davon überzeugt wären, dass ein ähnlicher Beweis funktionieren wird, egal wie viele Primzahlen ursprünglich ausgewählt werden.

Veranschaulichung des Beweises an einem Beispiel 
Die Beweisidee von Euklid lässt sich über folgendes Beispiel veranschaulichen. Dieses verwendet die ersten drei Primzahlen 2, 3 und 5. Aus diesen kann mit Euklids Methode eine neue Primzahl konstruiert werden, die in der Liste noch nicht vorkommt. Dafür wird die Zahl

betrachtet, die aus dem Produkt der Listenzahlen mit anschließender Addition von 1 gebildet wird. Diese Zahl 31 ist nun weder durch 2 noch durch 3 noch durch 5 teilbar. Das folgt daraus, dass die Differenz zweier Zahlen mit gemeinsamem Teiler wieder diesen Teiler hat: Es ist  nach Konstruktion durch 2, 3 und 5 teilbar – hätte auch ihr Nachfolger 31 diese Eigenschaft, so auch  Doch die 1 wird nur von 1 selbst geteilt. In der Tat ist 31 zum Beispiel wieder eine (neue) Primzahl und ungleich 2, 3 und 5.

In heutiger Fachsprache 
Trotz Euklids direkter Argumentation wird der Satz des Euklid von vielen Autoren in Standardwerken der Zahlentheorie als ein Widerspruchsbeweis wiedergegeben, zum Beispiel bei Jörg Brüdern oder Tom M. Apostol.

In der Sprechweise der heutigen Mengenlehre stellt Euklid die folgende Behauptung auf:
Gegeben sei eine endliche Menge  von paarweise verschiedenen Primzahlen  Dann gibt es mindestens eine weitere Primzahl  die nicht in  enthalten ist.
Dazu bildet Euklid das kleinste Vielfache  aller Primzahlen aus  Dabei ist wichtig, dass alle bisherigen Primzahlen Teiler von  sind.
Dann bildet er  und unterscheidet zwei Fälle:
 ist Primzahl, dann ist  eine weitere Primzahl.
 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 der Differenz  sein. Ein Widerspruch!

Der Beweis kommt auch ohne die Fallunterscheidung aus:
Angenommen, es gäbe nur endlich viele Primzahlen, etwa  Dann wäre die Zahl  wegen des Fundamentalsatzes der Arithmetik durch ein  teilbar, also auch  ein Widerspruch.

Beurteilung des Beweises 
Von Euklid wird oft fälschlicherweise berichtet, er habe sein Ergebnis durch Widerspruch bewiesen, beginnend mit der Annahme, dass die ursprünglich betrachtete endliche Menge alle Primzahlen enthält, obwohl es sich eigentlich um einen Beweis durch Fallunterscheidung, also eine direkte Beweismethode handelt. Der Philosoph Torkel Franzén stellte fest: „Euklids Beweis, dass es unendlich viele Primzahlen gibt, ist kein indirekter Beweis […]. Das Argument wird manchmal als indirekter Beweis formuliert, indem man es durch die Annahme ersetzt: ‚Angenommen  sind alle Primzahlen.‘ Da diese Annahme jedoch nicht einmal im Beweis verwendet wird, ist die Neuformulierung sinnlos.“

Benno Artmann sieht im Beweis von Euklid ein Beispiel der Verwendung „endlicher Mittel zur Beherrschung des Unendlichen“. In dieser Hinsicht habe Euklid „Bahnbrechendes“ geleistet. Jedoch bildeten die Primzahlen nur ein Beispiel dieses Prinzips in Euklids Schaffen. Im selben Kontext wird seine Theorie der Parallelen und Kreistangenten sowie „Unvereinbarkeit“ (im Sinne des Euklidischen Algorithmus) von Artmann genannt.

Die Zahlentheoretiker Gérald Tenenbaum und Michel Mendès France nennen Euklids Argument „wundervoll in seiner Schönheit und Einfachheit“ und weisen darauf hin, dass es sich in moderner Fachsprache auf die vier Symbole

reduzieren lässt. Dabei ist  die Fakultät von  und die erzeugte Zahl ist durch keine Zahl zwischen  teilbar, weshalb es Primzahlen geben muss, die größer als  sind.

Der Beweis von Euklid wird, hinsichtlich der fundamentalen Bedeutung des Resultats für die Zahlentheorie, wegen seiner Einfachheit bis heute als elegant erachtet. Dennoch liefert er keine starke Methode, zu schätzen, wie viele Primzahlen es unter einer Schranke  mindestens gibt. Zwar kann die Schranke , mit der Primzahlen abzählenden Funktion , induktiv aus Euklids Methode abgeleitet werden, doch dieses Resultat wird für die analytische Zahlentheorie als unbrauchbar angesehen. Dabei ist  der natürliche Logarithmus von . Bereits mit nicht wesentlich schwierigeren Argumenten, zum Beispiel durch Ideen von Leonhard Euler und Pafnuti Lwowitsch Tschebyschow, können wesentlich stärkere Schranken für die Primzahlverteilung hergeleitet werden. Dazu zählt die Schranke

für existierende Konstanten  für alle .

Bedeutung

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

Das Symbol  ist das Produktzeichen. Wegen  gibt es einen kleinsten Teiler  von . Dieser ist notwendigerweise eine Primzahl und teilerfremd zu . Daher ist mit  eine neue Primzahl gefunden.

Zieht man nur die Mengen der ersten aufeinanderfolgenden 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

Ist das Ergebnis von  wobei das Symbol  für das Primorial von  steht, wieder eine Primzahl, so nennt man diese auch Euklidische Primzahl. Ein etwas verallgemeinerter Begriff ist die Primorial-Primzahl, die durch  erzeugt wird. Es ist eine offene Frage, ob es unendlich viele Primorial-Primzahlen gibt. Die bis heute größte gefundene Primorial-Primzahl ist die -stellige Zahl . Zum Überprüfen, ob eine Zahl prim ist, gibt es Primzahltests, wie den von Miller-Rabin. Die bis heute größte gefundene Primzahl ist jedoch die -stellige Mersenne-Primzahl .

Zahlentheoretische Forschung 
Die Aussage, dass es unendlich viele Primzahlen gibt, führte zu der Frage, wie dicht sie in den natürlichen Zahlen liegen. Damit ist das langfristige Verhalten der Abstände zwischen verschiedenen Primzahlen gemeint. Zum Beispiel finden sich bis zur Zahl 10000 nur einhundert Quadratzahlen, also viel weniger als natürliche Zahlen. Analog dazu kann gefragt werden, wie häufig Primzahlen bis zu einer Schranke (wie zum Beispiel 10000) auftauchen und wie sich diese Häufigkeit verhält, wenn die Schranke immer größer gewählt wird.

Eine Folgerung des Beweises von Euklid für die Folge der Primzahlen ist die Ungleichung

Diese konnte von Bonse weiter verbessert werden zu

für alle  was auch Bonsesche Ungleichung genannt wird. Im Jahr 2000 bewies Michael Dalezman das etwas stärkere Resultat

ebenfalls gültig für alle 

Durch den Satz des Euklid ist es ausgeschlossen, alle Primzahlen niederzuschreiben. Jedoch gibt es Bemühungen, im Detail zu schätzen, wie viele Primzahlen in gewissen Bereichen anzutreffen sind, zum Beispiel im Intervall  Approximative Antworten auf solche Fragen liefert der (weiter unten diskutierte) Primzahlsatz. Dieser konnte erst Ende des 19. Jahrhunderts streng bewiesen werden. Aber bereits 1859 hatte Bernhard Riemann eine Formel hergeleitet, welche die Verteilung der Primzahlen bis ins letzte Detail ausdrückt. Diese beinhaltet als entscheidende Zutat die Nullstellen der Riemannschen Zeta-Funktion, die definiert werden kann durch

Eine detailliertere Übersicht zu Verallgemeinerungen des Satzes des Euklid ist im Abschnitt Stärkere Resultate gegeben.

Für die Kryptographie 

Große Primzahlen werden bei der Verschlüsselung von Daten (zum Beispiel im Internet) verwendet. Die Sicherheit solcher Systeme beruht auf der Annahme, dass es kein schnelles Verfahren gibt, eine Zahl in ihre Primfaktoren zu zerlegen. Beim RSA-Kryptosystem nimmt eine Person, die eine Nachricht verschlüsseln möchte, zwei große Primzahlen  und  mit großem Abstand zueinander, und bildet die zusammengesetzte Zahl  Mit deren Hilfe können nun Nachrichten (wenn zuvor in Zahlen umgewandelt) durch einen öffentlichen Schlüssel, der aus  und  erzeugt wurde, verschlüsselt werden. Dieser Schlüssel steht jedermann zur Verfügung, gibt jedoch keine Einsicht in das Kryptosystem an sich. Mit dem Wissen um  und  kann eine Nachricht aus der Öffentlichkeit an den Privatmenschen anschließend wieder entschlüsselt werden, da mit dem Wissen um  und  auch der „Gegenschlüssel“ erzeugt werden kann, der den Klartext wieder herstellt. Dieser Gegenschlüssel steht nur der Privatperson zur Verfügung und ist daher ein privater Schlüssel. Zum Brechen des Systems ist folglich die Faktorisierung von  erforderlich.

Der Satz des Euklid gewährleistet, dass beliebig große Primzahlen zur Erzeugung eines solchen Kryptosystems gefunden werden können.

Auswahl weiterer Beweise 
Für den Satz des Euklid wurden seit dem achtzehnten Jahrhundert zahlreiche alternative Beweise gefunden, z. B. durch Christian Goldbach (1730), Leonhard Euler (1736, 1737), Victor-Amédée Lebesgue (1843, 1856, 1859, 1862), James Joseph Sylvester (1871, 1888), Leopold Kronecker (1875/76), Ernst Eduard Kummer (1878) sowie Thomas Jean Stieltjes (1890). Modernere Beweise stammen u. a. von George Pólya (1921), Paul Erdös (1934, 1938), Richard Bellman (1947), Hillel Fürstenberg (1955), André Weil (1979), Lawrence C. Washington (1980) und Andrew Granville (2007, 2009).

In diesem Artikel wird nur eine Auswahl an Beweisen aufgeführt.

Über die Fermat-Zahlen 
Dieser Beweis geht auf Christian Goldbach aus dem Jahr 1730 zurück. Er entstammt einem Brief von Goldbach an Leonhard Euler vom 20. Juli. Über die Fermat-Zahlen lässt sich eine unendlich lange (monoton wachsende) Folge von natürlichen Zahlen konstruieren, die paarweise teilerfremd sind. Das heißt: Wenn man je zwei beliebige unterschiedliche Zahlen dieser Folge auswählt, haben diese keinen gemeinsamen Teiler. Da sie aber alle in Primfaktoren zerfallen, folgt schon der Satz des Euklid.

Es sei  die -te Fermat-Zahl. Die Teilerfremdheit von  und  für unterschiedliche  wird über die Rekursionsformel

ersichtlich, die mittels vollständiger Induktion gezeigt werden kann. Gilt nun  und ist  ein gemeinsamer Teiler von  und , dann muss dieser wegen der obigen Formel (mit ) auch 2 teilen. Da die Fermat-Zahlen ungerade sind, ist schon .

Beweis von Stieltjes 
Im Jahr 1890 lieferte Thomas Jean Stieltjes den folgenden Beweis: Zu jeder endlichen Liste von paarweise verschiedenen Primzahlen  wird das Produkt  betrachtet. Ist  eine dieser Primzahlen und  eine Zerlegung in ganze Zahlen  und , so kann  nicht  und  teilen, da sonst  bereits  teilen würde, was dem Fundamentalsatz der Arithmetik widerspräche. Damit teilt keines der  die Zahl , weshalb es mehr als die Primzahlen der Liste geben muss.

Über die Transzendenz der Kreiszahl 

Dieser Beweis wird J. Hacks im Jahr 1899 zugeschrieben. Dass die Kreiszahl  irrational ist, also nicht als Verhältnis zweier ganzer Zahlen geschrieben werden kann, konnte bereits von Johann Heinrich Lambert bewiesen werden. Im Jahr 1882 konnte Ferdinand von Lindemann dieses Resultat durch den Satz von Lindemann-Weierstraß verschärfen, indem er zeigte, dass  sogar eine transzendente Zahl ist, d. h. niemals Nullstelle eines nicht-trivialen Polynoms mit ausschließlich rationalen Koeffizienten ist. Auf Leonhard Euler geht wiederum die Formel

zurück. Diese Formel entsteht aus dem Euler-Produkt der Riemannschen Zeta-Funktion, ausgewertet an der Stelle , und folgt aus der Tatsache, dass natürliche Zahlen eindeutig in Primfaktoren zerfallen. Dass das Ergebnis den Wert  annimmt, war lange nicht klar und Gegenstand des Basler Problems. Das Produkt auf der linken Seite durchläuft alle Primzahlen, man hat also

Gäbe es nur endlich viele Primzahlen, dann wäre die linke Seite als Produkt endlich vieler rationaler Zahlen eine rationale Zahl. Die rechte Seite  ist jedoch, da  als transzendente Zahl niemals Quadratwurzel einer rationalen Zahl ist, irrational. Dies erzeugt einen Widerspruch.

Ähnlich kann auch mit allen positiven geraden Zahlen argumentiert werden, da stets

Dabei ist

die Menge aller rationalen Vielfachen von . Seit dem Beweis der Irrationalität der Apéry-Konstante  im Jahr 1979 ist diese Methode auch auf

anwendbar. Jedoch verwendet der Originalbeweis der Irrationalität von , erbracht von Roger Apéry, den Primzahlsatz.

Über die Irrationalität der Eulerschen Zahl 
Der Beweis der Irrationalität der Eulerschen Zahl  konnte bereits 1737 von Leonhard Euler erbracht werden. Um mit dieser die Unendlichkeit der Primzahlen zu zeigen, wird die Möbiusfunktion  benötigt,

die also u. a. stets den Wert 0 annimmt, falls die Eingabe  durch eine Quadratzahl größer als 1 teilbar ist. Wie R. C. Buck im Jahre 1944 zeigen konnte, gilt für Werte  mit  die Identität

Gäbe es nur endlich viele Primzahlen  so müsste jede Zahl  größer als  durch eine Quadratzahl teilbar sein. Dies hat den Hintergrund, dass dann mindestens eine Primzahl doppelt in der Faktorisierung von  vorkommen muss. Mit  gälte dann:

Die linke Seite ist ein endliches Produkt rationaler Zahlen, doch die rechte Seite ist eine irrationale Zahl. Dies erzeugt einen Widerspruch.

Fürstenbergs topologischer Beweis 

Im Jahr 1955 veröffentlichte Hillel Fürstenberg, damals noch Student an der Yeshiva University, einen Beweis des Satzes des Euklid, der lediglich topologische Mittel verwendet. Dabei werden, grob gesagt, bloß Eigenschaften von Mengensystemen ausgenutzt und ein Widerspruch erzeugt. Der Beweis überraschte die Mathematikergemeinschaft wegen seiner außergewöhnlichen Methodik. Der Kerngedanke von Fürstenberg ist, dass bei nur endlich vielen existierenden Primzahlen eine unmögliche Topologie konstruiert werden könnte.

Beim Beweis wird eine Topologie auf der Menge  der ganzen Zahlen definiert. Dabei ist eine Menge  offen, wenn sie leer ist oder für jedes  ein  existiert, sodass  Also ist jede nicht-leere offene Menge unendlich groß. Es kann gezeigt werden, dass dies eine Topologie definiert. Entscheidend ist, dass jedes  auch abgeschlossen ist. Aus der Identität

wird aus der Annahme, dass die Primzahlen eine endliche Menge bilden, gefolgert, dass  offen ist, was damit aber eine unendlich mächtige Menge sein müsste.

Erdös’ kombinatorischer Beweis 
Paul Erdös lieferte mehrere Beweise für die Unendlichkeit der Primzahlen. Einer davon zeigt über ein kurzes Argument den weiter unten diskutierten Satz von Euler über Primzahlen, und der andere über ein etwas schwächeres (aber schnelleres) kombinatorisches Argument die Unendlichkeit der Primzahlen: Ist  die (vollständige) Menge aller Primzahlen, die kleiner als eine natürliche Zahl  sind, so lässt sich jede Zahl kleiner oder gleich  eindeutig als ein Produkt

mit  und einer Quadratzahl  schreiben. Dabei ist  gleich 0, falls der Primfaktor in gerader Anzahl auftaucht und entsprechend 1, falls er in ungerader Anzahl in Erscheinung tritt. Damit gibt es  Möglichkeiten für die Wahl des Primzahlprodukts. Es folgt  und schließlich . Durch hinreichend große Wahl von  entsteht ein Widerspruch.

Washingtons Beweis mittels kommutativer Algebra 
Ein Beweis von Lawrence C. Washington aus dem Jahr 1980 nutzt kommutative Algebra. Es wird ein abstrakter Satz verwendet, nämlich, dass ein Dedekindring mit nur endlich vielen Primidealen bereits ein Hauptidealring ist. Als solcher ist der Dedekindring dann ein faktorieller Ring, seine Elemente haben also eine eindeutige Zerlegung in Primelemente. Im Umkehrschluss bedeutet dies, dass ein Dedekindring mit keiner eindeutigen Primelementzerlegung unendlich viele Primideale haben muss. Bekannt ist, dass jeder Ganzheitsring  eines Zahlkörpers  ein Dedekindring ist. Es kann gezeigt werden, dass für jedes Primideal  höchstens  Primzahlen  über  liegen, also gewissermaßen zu  „korrespondieren“. Dabei ist  der Grad der Körpererweiterung. Für den Beweis des Satzes des Euklid reicht es demnach aus, die Existenz eines solchen Dedekindrings mit fehlender Primelementzerlegung nachzuweisen. Ein Beispiel ist  mit , denn zum Beispiel gilt

Stärkere Resultate

Satz von Euler 

Leonhard Euler konnte im Jahr 1737 zeigen, dass die Reihe der Kehrwerte aller Primzahlen divergiert, also

Dies bedeutet anschaulich, dass sich für jede noch so große Zahl immer (endlich viele) Primzahlen finden lassen, deren summierte Kehrwerte die gegebene Zahl überschreiten. Diese Aussage ist stärker als der Satz des Euklid, da sie die Unendlichkeit der Primzahlen impliziert, deren Unendlichkeit jedoch a priori nicht die Divergenz der Reihe: Beispielsweise gibt es unendlich viele ganze Zehnerpotenzen, aber es ist  Für den Beweis verwendete Euler das nach ihm benannte Euler-Produkt und führte sein Argument auf die Divergenz der harmonischen Reihe  zurück.

Im Jahr 1874 konnte Franz Mertens dieses Ergebnis verbessern, indem er ausrechnete, wie schnell die Summe in Abhängigkeit einer Abbruchschranke anwächst. Mertens zeigte, dass es eine Zahl  gibt, sodass

wobei der von  abhängige Fehler  für steigende Werte gegen 0 strebt. Die Funktion  wächst zwar langsam an, ist jedoch unbeschränkt. In der Tat divergiert die Reihe  entsprechend „langsam“: Ein Computer, der jede Nanosekunde einen neuen Summanden addiert, wäre nach ca. 15 Milliarden Jahren der Berechnung bei einer Zahl, die etwas größer als 4 ist.

Ebenfalls verwandt zu Euler’s Satz ist die Beobachtung

von James Joseph Sylvester aus dem Jahr 1888.

Dirichletscher Primzahlsatz 

Im Jahr 1837 bewies Peter Dirichlet, dass jede arithmetische Progression natürlicher Zahlen bereits unendlich viele Primzahlen enthalten muss, wenn Startwert und der konstant hinzukommende Summand teilerfremd sind. Zum Beispiel enthält die Progression 7, 11, 15, 19, 23 … unendlich viele Primzahlen, da 7 und 4 teilerfremd sind. Dieses Resultat ist stärker als der Satz des Euklid, da dieser als Spezialfall aus dem Dirichletschen Primzahlsatz, angewendet auf die Progression 1, 2, 3, 4, 5 …, hervorgeht.

Der Beweis dieses Satzes ist eine typische Anwendung der analytischen Zahlentheorie. Er nutzt die Tatsache, dass Dirichletsche L-Funktionen an der Stelle  nicht Null werden. Trotzdem findet das Resultat auch in der algebraischen Zahlentheorie Anwendung, zum Beispiel an einer kritischen Stelle im Beweis des Hasse-Minkowski-Prinzips.

Der Beweis des Satzes basiert auf einer Verallgemeinerung des Satzes von Euler. Genau genommen zeigte Dirichlet, dass die Reihe der Kehrwerte der Primzahlen in der arithmetischen Progression divergiert. Für teilerfremde  und  gilt also

Der Dirichletsche Primzahlsatz konnte später von Carl Ludwig Siegel und Arnold Walfisz verschärft werden. Durch den Satz von Siegel-Walfisz wurde u. a. gezeigt, dass die Anzahl der Primzahlen in Progressionen mit gleichem Abstandsprinzip asymptotisch gleich häufig sind. Demnach enthalten z. B. die Progressionen 1, 1001, 2001, 3001, 4001, … und 7, 1007, 2007, 3007, 4007, … asymptotisch betrachtet gleich viele Primzahlen.

Eine modernere und noch stärkere Fassung des Dirichletschen Primzahlsatzes ist der Satz von Bombieri und Winogradow.

Bertrandsches Postulat 

Das Bertrandsche Postulat sagt aus, dass zwischen jeder Zahl  und ihrem Doppelten mindestens eine Primzahl liegt. Wählt man etwa , so liegt im Bereich  die Primzahl . Es ist benannt nach Joseph Bertrand, der es für alle Argumente  zeigte. Erstmals vollständig bewiesen wurde dieses Resultat von Pafnuti Lwowitsch Tschebyschow. Es folgten weitere teils einfachere Beweise durch Paul Erdös und Srinivasa Ramanujan, der dabei auch die Ramanujan-Primzahlen betrachtete, die einer gewissen Ungleichung genügen. Im Gegensatz zum Satz des Euklid, der aus dem Postulat durch beliebig große Wahl von  folgt, macht das Betrandsche Postulat eine erste „starke“ Häufigkeitsanalyse über die Primzahlen. Zwar kann gezeigt werden, dass zwischen beliebig groß werdenden Primzahlen beliebig große Lücken entstehen können, aber das Postulat gibt eine Schranke für die Lücke in Abhängigkeit der Größe der Primzahl: Ist  eine Primzahl, so gilt für die darauf folgende Primzahl  die Abschätzung .

Verwandte Fragestellungen um die Dichte der Primzahlen sind mitunter deutlich schwieriger zu beweisen. Es wird vermutet, dass zwischen zwei benachbarten positiven Quadratzahlen stets eine Primzahl liegt. Diese Legendresche Vermutung konnte jedoch bisher nicht bewiesen werden. Allerdings konnte Albert Ingham 1937 beweisen, dass sich für hinreichend große  zwischen den benachbarten Kubikzahlen  und  stets eine Primzahl befindet.

Primzahlsatz 

Die untere Schranke des Satzes des Euklid für die Anzahl der Primzahlen bis zu einer Größe  kann deutlich verbessert werden. Ende des 19. Jahrhunderts gelang es Jacques Hadamard und Charles-Jean de La Vallée Poussin unabhängig voneinander zu zeigen, dass die Anzahl der Primzahlen  unter einer positiven Schranke  ungefähr gleich  ist, und dass der relative Fehler in dieser Schätzung für unbeschränkt wachsende  gegen 0 strebt. Es gilt also

Dabei ist  der natürliche Logarithmus von . Oft wird bei der Formulierung des Primzahlsatzes statt der Funktion  auch der Integrallogarithmus gewählt. Aus  ergibt sich der Satz des Euklid als direkte Folgerung. Als eine weitere Folgerung des Primzahlsatzes ergibt sich eine Möglichkeit, zu schätzen, wie groß die zehnte, hundertste, tausendste oder allgemein -te Primzahl ist, wenn man sie in ihrer aufsteigenden Folge 2, 3, 5, 7, … betrachtet. Das Gesetz lautet  für die -te Primzahl , das heißt, dass  auf lange Sicht gleich schnell wächst wie . Beispielsweise ist  und .

Im Gegensatz zu Euklids Beweis der Unendlichkeit der Primzahlen verwendeten die ersten Beweise der Primzahlsätze analytische Methoden, die auf nullstellenfreien Regionen von L-Funktionen fußen. Es wurden jedoch von Paul Erdös und Atle Selberg auch elementare Beweise des Primzahlsatzes gefunden, die ohne analytische Methoden auskommen. Ein weiterer elementarer Beweis stammt von Florian K. Richter aus dem Jahr 2021.

Die Frage, wie groß die Abweichung der Abschätzung des Primzahlsatzes von der eigentlichen Zählfunktion ist, ist Gegenstand der Riemannschen Vermutung.

Satz von Chen 

Im Jahr 1966 gelang dem chinesischen Mathematiker Chen Jingrun der Nachweis folgender „Annäherung“ an die bisher unbewiesene Goldbachsche Vermutung:
Jede hinreichend große gerade Zahl kann als Summe einer Primzahl und einer Zahl mit höchstens zwei Primfaktoren geschrieben werden.
Dies impliziert insbesondere den Satz des Euklid, da es bei nur endlich vielen Primzahlen keine Möglichkeit gäbe, beliebig große Zahlen so darzustellen. In der Tat, wäre  die „größte“ Primzahl, so wäre die größte „Chen-Zahl“ gegeben durch .

Der Ausdruck „hinreichend groß“ im Satz von Chen bedeutet, dass es eine minimale Zahl gibt (die aber sehr groß sein kann!), so dass die Aussage ab dort immer stimmt. Knapp 50 Jahre nach Chens Beweis, im Jahr 2015, fand Tomohiro Yamada eine explizite Schranke, ab der der Satz von Chen definitiv anwendbar ist.
Jede gerade Zahl größer als  kann als Summe einer Primzahl und einer Zahl mit höchstens zwei Primfaktoren geschrieben werden.
Dabei ist  die Eulersche Zahl.

Satz von Green-Tao 

Im Jahr 2004 zeigten Ben Green und Terence Tao den Satz von Green-Tao, dass es in der Folge der Primzahlen beliebig lange arithmetische Progressionen gibt. Zum Beispiel ist 3, 5, 7 eine Progression von Primzahlen der Länge 3, da alle benachbarten Zahlen den gleichen Abstand haben. Die längste bekannte (Stand 2020) arithmetische Folge von Primzahlen hat die Länge 27. Explizit ist sie gegeben durch

Verwandte Probleme 
Während durch den Satz des Euklid bekannt ist, dass die Menge der Primzahlen unendlich groß ist, erweisen sich Fragestellungen nach der Unendlichkeit gewisser Teilmengen von Primzahlen mitunter schwierig.

Primzahlzwillinge 

Zum Beispiel ist die Frage, ob es unendlich viele Primzahlzwillinge gibt, bis heute nicht beantwortet. Ein Paar  von Primzahlen heißt Zwilling, wenn  gilt, sich beide also bloß um 2 unterscheiden. Die ersten Primzahlzwillinge sind

Mit Hilfe des Brunschen Siebs konnte von Viggo Brun gezeigt werden, dass es eine Konstante  gibt, sodass für jedes  und die Anzahl  aller Primzahlzwillinge bis  gilt:

Als Folgerung ergibt sich, dass die Reihe aller Kehrwerte der Primzahlzwillinge konvergiert, also

und zwar gegen die Brunsche Konstante  Damit ist ein Beweis der Unendlichkeit der Menge aller Primzahlzwillinge analog zum Satz von Euler nicht möglich. Nicht-triviale untere Schranken von  sind bis heute lediglich Gegenstand von Vermutungen. So wurde 1922 von Godfrey Harold Hardy und John Edensor Littlewood vermutet, dass sich die Anzahl  der Primzahlzwillinge unter einer wählbaren Schranke  asymptotisch verhält wie

Dabei ist

Dies hätte als Konsequenz, dass es unendlich viele Primzahlzwillinge gibt, da der Term  aufgrund des langsamen Wachstums der Logarithmen viel schneller wächst als der quadrierte Logarithmus  Auch die Frage, ob es unendlich viele Primzahlvierlinge oder -sechslinge gibt, ist ungeklärt. Allerdings konnten Daniel Goldston, Cem Yıldırım und János Pintz nachweisen, dass es auf gewisse Weise langfristig immer wieder „relativ dünn“ zwischen Primzahlen wird, im Sinne von

Dabei bedeutet das Symbol  Limes inferior. Seitdem wurde stark daran gearbeitet, die Abschätzungen der Abstände kleiner werden zu lassen. Schließlich gelang Yitang Zhang ein Durchbruch, indem er bewies, dass es unendlich oft vorkommt, dass zwei benachbarte Primzahlen näher als  voneinander entfernt sind. Es gilt also

Damit wurde erstmals gezeigt, dass Primzahlabstände einen festen Abstand immer wieder unterschreiten. Das Resultat wurde 2015 von James Maynard auf den Abstand 600 verbessert. Die Primzahlzwillings-Vermutung ist äquivalent zu

Fermat- und Mersenne-Primzahlen 
Auch die Frage, ob unendlich viele Zahlen der Folgen  (mit  Primzahl) bzw.  wieder Primzahlen sind, ist ungeklärt. Während jedoch angenommen wird, dass es unendlich viele Mersenne-Primzahlen gibt, wird davon ausgegangen, dass es außer  und  keine weitere Fermat-Primzahl gibt. So konnte schon Leonhard Euler zeigen, dass  durch 641 teilbar ist. Damit widerlegte er die Vermutung Fermats, dass jede der Zahlen  eine Primzahl sei.

Literatur 
 Die Elemente von Euklid. In: Ostwalds Klassiker der exakten Wissenschaften. Verlag Europa-Lehrmittel, 4. Auflage, 2015.
 Benno Artmann: Euclid – The creation of mathematics. Springer-Verlag, New York, 1999.
 Romeo Meštrović: Euclid’s theorem on the infinitude of primes: a historical survey of its proofs (300 B.C. – 2017) and another new proof. 2018.
 Paul Pollack: Not Always Burried Deep: Selections from Analytic and Combinatorial Number Theory. In: American Mathematical Society. 2009.
 Paulo Ribenboim: The little book of bigger primes. Springer-Verlag, New York, 2004.

Weblinks

Einzelnachweise 

Euklid, Satz von
Primzahl
Euklid