Satz des Euklid

Darstellung Euklids im Oxford University Museum

Der 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. Euklid selbst formulierte den Satz 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 teilbar ist. Die ersten Primzahlen sind 2, 3, 5 und 7. Der Satz von Euklid besagt, dass die Liste 2, 3, 5, 7, 11, 13 … aller Primzahlen niemals endet, genauso wie die Liste 1, 2, 3, 4, 5, 6 … aller natürlichen Zahlen niemals 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 Euklid's Argument anhand eines Widerspruchsbeweises aufgeführt sei. Jedoch lässt sich der Beweis zu einem Widerspruchsbeweis umformulieren.

Nach dem Fundamentalsatz der Arithmetik zerfallen alle natürlichen Zahlen größer als 1 eindeutig in Primfaktoren. Der Satz von 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 von 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

Originalformulierung des Euklid

Der Satz wurde erstmals in Euklids Elementen im neunten Buch, Proposition 20, niedergeschrieben. Er kann wie folgt ins Deutsche übersetzt werden:

Οἱ πρῶτοι ἀριθμοὶ πλείους εἰσὶ παντὸς τοῦ προτεθέντος πλήθους πρώτων ἀριθμῶν. ῎Εστωσαν οἱ προτεθέντες πρῶτοι ἀριθμοὶ οἱ Α, Β, Γ· λέγω, ὅτι τῶν Α, Β, Γ πλείους εἰσὶ πρῶτοι ἀριθμοί. Εἰλήφθω γὰρ ὁ ὑπὸ τῶν Α, Β, Γ ἐλάχιστος μετρούμενος καὶ ἔστω ΔΕ, καὶ προσκείσθω τῷ ΔΕ μονὰς ἡ ΔΖ. ὁ δὴ ΕΖ ἤτοι πρῶτός ἐστιν ἢ οὔ. ἔστω πρότερον πρῶτος· εὐρημένοι ἄρα εἰσὶ πρῶτοι ἀριθμοὶ οἱ Α, Β, Γ, ΕΖ πλείους τῶν Α, Β, Γ. ̓Αλλὰ δὴ μὴ ἔστω ὁ ΕΖ πρῶτος· ὑπὸ πρώτου ἄρα τινὸς ἀριθμοῦ μετρεῖται. μετρείσθω ὑπὸ πρώτου τοῦ Η· λέγω, ὅτι ὁ Η οὐδενὶ τῶν Α, Β, Γ ἐστιν ὁ αὐτός. εἰ γὰρ δυνατόν, ἔστω. οἱ δὲ Α, Β, Γ τὸν ΔΕ μετροῦσιν· καὶ ὁ Η ἄρα τὸν ΔΕ μετρήσει. μετρεῖ δὲ καὶ τὸν ΕΖ· καὶ λοιπὴν τὴν ΔΖ μονάδα μετρήσει ὁ Η ἀριθμὸς ὤν· ὄπερ ἄτοπον. οὐκ ἄρα ὁ Η ἑνὶ τῶν Α, Β, Γ ἐστιν ὁ αὐτός. καὶ ὑπόκειται πρῶτος. εὑρημένοι ἄρα εἰσὶ πρῶτοι ἀριθμοὶ πλείους τοῦ προτεθέντος πλήθους τῶν Α, Β, Γ οἱ Α, Β, Γ, Η· ὅπερ ἔδει δεῖξαι.

Es gibt mehr Primzahlen als jede vorgelegte Anzahl von Primzahlen. Die vorgelegten Primzahlen seien a, b, c. Ich behaupte, dass es mehr Primzahlen gibt als a, b, c. Man bilde die kleinste von a, b, c gemessene Zahl. Sie sei DE, und man füge zu DE die Einheit DF hinzu. Entweder ist EF dann eine Primzahl, oder nicht. Zunächst sei es eine Primzahl. Dann hat man mehr Primzahlen als a, b, c gefunden, nämlich a, b, c, EF. Zweitens sei EF keine Primzahl. Dann muss es von irgendeiner Primzahl gemessen werden; es werde von der Primzahl g gemessen. Ich behaupte, dass g mit keiner der Zahlen a, b, c zusammenfällt. Wenn möglich, tue es dies nämlich, a, b, c messen nun auch DE; auch g müsste dann DE messen. Es misst aber auch EF. g müsste also auch den Rest, die Einheit DF, messen, während es eine Zahl ist; dies wäre Unsinn. Also fällt g mit keiner der Zahlen a, b, c zusammen; und es ist eine Primzahl nach Voraussetzung. Man hat also mehr Primzahlen als die vorgelegte Anzahl a, b, c gefunden, nämlich a, b, c, g.

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 $p_{1},...,p_{n}$ (Euklid behandelt hier den Fall $n=3$) eine neue Primzahl zu gewinnen, indem man die Zahl $p_{1}\cdot p_{2}\cdots p_{n}+1$ bildet und einen ihrer Primfaktoren bestimmt. 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. Unter der Annahme, es gebe nur die Primzahlen 2, 3 und 5, wird die Zahl

$2\cdot 3\cdot 5+1=31$

betrachtet. Diese müsste nun durch 2, 3 oder 5 teilbar sein, da dies alle Primzahlen sind und somit alle Zahlen in diese Bausteine zerfallen. Jedoch wäre dann auch 1 durch 2, 3 oder 5 teilbar, da schon $2\cdot 3\cdot 5$ durch 2, 3 und 5 teilbar war. Das folgt daraus, dass die Differenz zweier Zahlen mit gemeinsamem Teiler wieder diesen Teiler hat. Zum Beispiel ist die Differenz zweier gerader Zahlen wieder gerade. Diese Widerspruch zeigt, dass es mehr Primzahlen als 2, 3 und 5 geben muss. In der Tat ist 31 zum Beispiel wieder eine (neue) Primzahl.

In heutiger Sprache

Trotz Euklids direktem Argument wird der Satz von 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 $M$ von Primzahlen $p_{1},\ldots ,p_{n}.$ Dann gibt es mindestens eine weitere Primzahl $p_{n+1},$ die nicht in $M$ enthalten ist.

Dazu bildet Euklid das kleinste Vielfache $m=p_{1}\cdot p_{2}\cdots p_{n}$ aller Primzahlen aus $M$. Dabei ist wichtig, dass alle bisherigen Primzahlen Teiler von $m$ sind. Dann bildet er $m\!+\!1$ und unterscheidet zwei Fälle:

1. $m\!+\!1=:p_{n+1}$ ist Primzahl, dann ist $p_{n+1}\not \in M$ eine weitere Primzahl.
2. $m\!+\!1$ ist keine Primzahl, dann hat $m\!+\!1$ einen Primteiler $q.$ Angenommen, es wäre $q=:p_{i}\in M,$ dann wäre $q$ ein Teiler von $m.$ Es ist aber auch Teiler von $m\!+\!1,$ und müsste folglich auch Teiler sein von der Differenz $(m\!+\!1)-m=1.$ Ein Widerspruch!

Der Beweis kommt auch ohne die Fallunterscheidung aus:

Angenommen, es gäbe nur endlich viele Primzahlen, in etwa $p_{1},...,p_{r}$. Dann wäre die Zahl $m+1$ wegen des Fundamentalsatzes der Arithmetik durch ein $p_{j}$ teilbar, also auch $p_{j}|1$, ein Widerspruch.

Bewertung

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 $q_{1}$, ... $q_{n}$ 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.

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 $x$ mindestens gibt. Zwar kann die Schranke $\pi (x)>\log(\log(x))$, mit der Primzahl zählenden Funktion $\pi (x)$, induktiv aus Euklids Methode abgeleitet werden, doch dieses Resultat wird für die analytische Zahlentheorie als unbrauchbar angesehen. Dabei ist $\log(x)$ der natürliche Logarithmus von $x$. 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

$c_{2}{\frac {x}{\log(x)}}<\pi (x)<c_{1}{\frac {x}{\log(x)}}$

für existierende Konstanten $c_{1},c_{2}>0$ für alle $x>2$.

Bedeutung

Erzeugung neuer Primzahlen

Der Beweis des Satzes von Euklid zeigt eine Möglichkeit auf, wie aus einer oder mehreren vorgegebenen Primzahlen $p_{1},p_{2},\dotsc ,p_{k}$ mindestens eine weitere Primzahl berechnet werden kann. Dazu bildet man das Produkt dieser Zahlen und addiert 1 zu dem Produkt, also

$n:=p_{1}p_{2}\dotsm p_{k}+1=\prod _{i=1}^{k}p_{i}+1$.

Wegen $n>1$ gibt es einen kleinsten Teiler $d>1$ von $n$. Dieser ist notwendigerweise eine Primzahl und teilerfremd zu $p_{1},...,p_{k}$. Daher ist mit $d$ eine neue Primzahl gefunden.

Zieht man nur Mengen von aufeinander folgenden Primzahlen in Betracht, also $p_{1}=2,p_{2}=3,p_{3}=5,\dotsc$, und bildet daraus die Zahlen

$P_{r}:=2\cdot 3\dotsm p_{r}+1=\prod _{i=1}^{r}p_{i}+1$,

dann stellen sich die ersten fünf dieser Zahlen als prim heraus, die nächsten fünf als zusammengesetzt. Beispielsweise ist

$P_{6}=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13+1=30031=59\cdot 509$.

Ist das Ergebnis von $2\cdot 3\cdots p_{n}+1=p_{n}\#+1$, wobei das Symbol $\#$ für das Primorial von $p_{n}$ steht, wieder eine Primzahl, so nennt man diese auch Euklidsche Primzahl. Ein etwas verallgemeinerter Begriff ist die Primorial-Primzahl. Es ist eine offene Frage, ob es unendlich viele Primorial-Primzahlen gibt. Die bis heute größte gefundene Primorial-Primzahl ist die 476311-stellige Zahl $1\,098\,133\#-1$. 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 eine 24862048-stellige Mersenne-Primzahl $P$ mit $P=2^{82\,589\,933}-1$.

Für die Kryptographie

→ Hauptartikel: RSA-Kryptosystem

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 $p$ und $q$ mit großem Abstand zueinander, und bildet die zusammengesetzte Zahl $pq=N$. Mit Hilfe dieser können nun Nachrichten (wenn zuvor in Zahlen umgewandelt) durch einen öffentlichen Schlüssel, der aus $p$ und $q$ 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 $p$ und $q$ kann eine Nachricht aus der Öffentlichkeit an den Privatmenschen anschließend wieder entschlüsselt werden, da mit dem Wissen um $p$ und $q$ 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 $N$ erforderlich.

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

Auswahl weiterer Beweise

Für den Satz von Euklid wurden ab dem achtzehnten Jahrhundert zahlreiche alternative Beweise gefunden, z. B. durch Christian Goldbach (1730), Leonhard Euler (1736, 1737), Henri Léon Lebesgue (1843, 1856, 1859, 1862), James Joseph Sylvester (1871, 1888), Leopold Kronecker (1875), 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 (1943), Hillel Fürstenberg (1955), André Weil (1979), Lawrence C. Washington (1980) und Andrew Granville (2007, 2009).

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

Über die Fermat-Zahlen

Dieser Beweis geht auf Christian Goldbach aus dem Jahr 1730 zurück. Er entstammt aus 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 alle paarweise teilerfremd sind. Das heißt, dass wenn man je zwei beliebige unterschiedliche Zahlen dieser Folge auswählt, diese keine gemeinsamen Teiler haben. Da sie aber alle in Primfaktoren zerfallen, folgt schon der Satz von Euklid.

Es sei $F_{n}=2^{2^{n}}+1$ die $n$-te Fermat-Zahl. Die Teilerfremdheit von $F_{a}$ und $F_{b}$ für unterschiedliche $a,b$ wird über die Rekursionsformel

$\prod _{k=0}^{n-1}F_{k}=F_{n}-2$

ersichtlich, die mittels vollständiger Induktion gezeigt werden kann. Ist nun $a<b$ und $d>0$ ein gemeinsamer Teiler von $F_{a}$ und $F_{b}$, dann muss dieser wegen der oberen Formel ($n=b$) auch 2 teilen. Da die Fermat-Zahlen ungerade sind, ist schon $d=1$.

Satz von Euler

→ Hauptartikel: Satz von Euler (Primzahlen)

Leonhard Euler

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

${\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{5}}+{\frac {1}{7}}+{\frac {1}{11}}+{\frac {1}{13}}+\cdots =\infty .$

Diese Aussage ist stärker als der Satz von 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 $1+{\tfrac {1}{10}}+{\tfrac {1}{100}}+{\tfrac {1}{1000}}+\cdots =1{,}111\ldots ={\tfrac {10}{9}}<\infty .$ Für den Beweis verwendete Euler das nach ihm benannte Euler-Produkt und führte sein Argument auf die Divergenz der harmonischen Reihe

$1+{\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{4}}+\cdots$

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 $M$ gibt, so dass

$\sum _{p\leq x \atop p{\text{ Primzahl}}}{\frac {1}{p}}=\log(\log(x))+M+o(1),$

wobei der von $x$ abhängige Fehler $o(1)$ für steigende Werte immer mehr gegen 0 geht. Die Funktion $f(x)=\log(\log(x))$ wächst zwar langsam an, ist jedoch unbeschränkt. In der Tat divergiert die Reihe ${\tfrac {1}{2}}+{\tfrac {1}{3}}+{\tfrac {1}{5}}+{\tfrac {1}{7}}+{\tfrac {1}{11}}+{\tfrac {1}{13}}+\cdots$ 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

$\prod _{p\leq x \atop p{\text{ Primzahl}}}\left({\frac {1}{1-{\frac {1}{p}}}}\right)\geq \sum _{n\leq x}{\frac {1}{n}}\geq \log(x)$

von James Joseph Sylvester aus dem Jahr 1888.

Beweis von Stieltjes

Im Jahr 1890 lieferte Thomas Jean Stieltjes den folgenden Beweis: Zu jeder endlichen Liste von paarweise verschiedenen Primzahlen $p_{1},...,p_{k}$ wird das Produkt $P=p_{1}\cdots p_{k}$ betrachtet. Ist $p_{i}$ einer dieser Primzahlen und $P=AB$ eine Zerlegung in ganze Zahlen $A$ und $B$, so kann $p_{i}$ nicht $A$ und $B$ teilen, da sonst $p_{i}^{2}$ bereits $P$ teilen würde, was dem Fundamentalsatz der Arithmetik widerspräche. Damit teilt keines der $p_{i}$ die Zahl $A+B$, weshalb es mehr als die Primzahlen der Liste geben muss.

Über die Irrationalität der Kreiszahl

Die Kreiszahl ist irrational, hat also unendlich viele Nachkommastellen, die kein sich wiederholendes Muster zeigen. Daraus kann die Unendlichkeit der Menge der Primzahlen gefolgert werden.

Dieser Beweis wird J. Hacks im Jahr 1899 zugeschrieben. Dass die Kreiszahl $\pi =3{,}141...$ irrational ist, also nicht als Verhältnis zweier ganzer Zahlen geschrieben werden kann, konnte bereits von Johann Heinrich Lambert bewiesen werden. Auf Leonhard Euler geht wiederum die Formel

$\prod _{p\,\mathrm {Primzahl} }{\frac {1}{1-p^{-2}}}=\sum _{n=1}^{\infty }{\frac {1}{n^{2}}}={\frac {\pi ^{2}}{6}}$

zurück. Diese Formel entsteht aus dem Euler-Produkt der Riemannschen Zeta-Funktion, ausgewertet am Punkt $s=2$, und folgt aus der Tatsache, dass natürliche Zahlen eindeutig in Primfaktoren zerfallen. Dass das Ergebnis den Wert ${\tfrac {\pi ^{2}}{6}}$ annimmt war lange nicht klar und Gegenstand des Basler Problems. Das Produkt auf der linken Seite durchläuft alle Primzahlen, man hat also

${\frac {4}{3}}\cdot {\frac {9}{8}}\cdot {\frac {25}{24}}\cdot {\frac {49}{48}}\cdot {\frac {121}{120}}\cdots ={\frac {\pi ^{2}}{6}}.$

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 $\pi$ irrational ist, irrational.

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

$\prod _{p\,\mathrm {Primzahl} }{\frac {1}{1-p^{-2k}}}\in \mathbb {Q} \pi ^{2k}.$

Seit dem Beweis der Irrationalität der Apéry-Konstante $\zeta (3)$ im Jahr 1979 ist diese Methode auch auf

$\prod _{p\,\mathrm {Primzahl} }{\frac {1}{1-p^{-3}}}=\zeta (3)$

anwendbar. Jedoch verwendet der Originalbeweis der Irrationalität von $\zeta (3)$, erbracht von Roger Apéry, den Primzahlsatz.

Über die Irrationalität der Eulerschen Zahl

Der Beweis der Irrationalität der Eulerschen Zahl $e=2{,}71828\ldots$ konnte bereits 1737 von Leonhard Euler erbracht werden. Um mit dieser die Unendlichkeit der Primzahlen zu zeigen, wird die Möbiusfunktion $\mu (n)$ benötigt

$\mu (n)={\begin{cases}(-1)^{k},&{\mbox{wenn }}n{\mbox{ quadratfrei, wobei }}k{\mbox{ die Anzahl der Primfaktoren von }}n{\mbox{ ist}},\\0&{\mbox{sonst,}}\end{cases}}$

die also u. a. stets den Wert 0 annimmt, falls die Eingabe durch eine Quadratzahl teilbar ist. Wie R. C. Buck im Jahre 1944 zeigen konnte, gilt für Werte $|x|<1$ die Identität

$\prod _{n=1}^{\infty }(1-x^{n})^{\frac {\mu (n)}{n}}=(1-x)\cdot {\frac {1}{\sqrt {1-x^{2}}}}\cdot {\frac {1}{\sqrt[{3}]{1-x^{3}}}}\cdot {\frac {1}{\sqrt[{5}]{1-x^{5}}}}\cdot {\sqrt[{6}]{1-x^{6}}}\cdots =e^{-x}.$

Gäbe es nur endlich viele Primzahlen $p_{1},...,p_{k}$, so müsste jede Zahl $n$ größer als $P=p_{1}\cdot p_{2}\cdots p_{k}$ durch eine Quadratzahl teilbar sein. Dies hat den Hintergrund, dass dann mindestens eine Primzahl doppelt in der Faktorisierung von $n$ vorkommen muss. Mit $x=-{\tfrac {1}{P!}}$ gölte dann:

$\prod _{n=1}^{P}\left(1-\left(-{\frac {1}{P!}}\right)^{n}\right)^{\mu (n){\frac {P!}{n}}}=e.$

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

→ Hauptartikel: Fürstenbergs Beweis der Unendlichkeit der Primzahlen

Hillel Fürstenberg

Im Jahr 1955 veröffentlichte Hillel Fürstenberg, damals noch Student an der Yeshiva University, einen Beweis des Satzes von 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 $\mathbb {Z}$ der ganzen Zahlen definiert. Dabei ist eine Menge $O$ offen, wenn sie leer ist oder für jedes $a\in O$ ein $b>0$ existiert, so dass $N_{a,b}=\{a+bn\mid n\in \mathbb {Z} \}\subseteq O$. Also ist jede nicht-leere offene Menge unendlich groß. Es kann gezeigt werden, dass dies eine Topologie definiert. Entscheidend ist, dass jedes $N_{a,b}$ auch abgeschlossen ist. Aus der Identität

$\mathbb {Z} \setminus \{-1,1\}=\bigcup _{p\,\mathrm {Primzahl} }N_{0,p}$

wird aus der Annahme, dass die Primzahlen eine endliche Menge bilden, gefolgert, dass $\{-1,1\}$ offen ist, was aber unendlich 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 Satz von Euler über Primzahlen, also die Divergenz der Reihe

${\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{5}}+\cdots$

und der andere über ein etwas schwächeres (aber schnelleres) kombinatorisches Argument die Unendlichkeit der Primzahlen. Ist $\{p_{1},...,p_{n}\}$ die vollständige Menge von Primzahlen, die alle kleiner als eine natürliche Zahl $N$ sind, so lässt sich jede Zahl kleiner oder gleich $N$ eindeutig als ein Produkt

$p_{1}^{e_{1}}\cdot p_{2}^{e_{2}}\cdots p_{n}^{e_{n}}\cdot m^{2}$

mit $e_{j}\in \{0,1\}$ und einer Quadratzahl $m^{2}$ schreiben. Dabei ist $e_{j}$ gleich 0, falls der Primfaktor in gerader Anzahl auftaucht und entsprechend 1, falls er in ungerader Anzahl in Erscheinung tritt. Damit gibt es $2^{n}$ Möglichkeiten für die Wahl des Primzahlprodukts. Es folgt $N\leq 2^{n}{\sqrt {N}}$ und schließlich $2^{n}\geq {\sqrt {N}}$. Durch hinreichend große Wahl von $N$ 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 sein muss. 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. Es ist bekannt, dass jeder Ganzheitsring ${\mathcal {O}}_{K}$ eines Zahlkörpers $K$ ein Dedekindring ist. Es kann gezeigt werden, dass für jedes Primideal ${\mathfrak {p}}$ höchstens $[K:\mathbb {Q} ]$ Primzahlen $p$ über ${\mathfrak {p}}$ liegen, also gewissermaßen zu ${\mathfrak {p}}$ „korrespondieren“. Dabei ist $[K:\mathbb {Q} ]$ der Grad der Körpererweiterung. Für den Beweis des Satzes von Euklid reicht es demnach aus, die Existenz eines solchen Dedekindrings mit fehlender Primelementzerlegung nachzuweisen. Ein Beispiel ist ${\mathcal {O}}_{K}=\mathbb {Z} [{\sqrt {-5}}]$, denn zum Beispiel gilt

$6=2\cdot 3=(1-{\sqrt {-5}})(1+{\sqrt {-5}}).$

Stärkere Resultate

Dirichletscher Primzahlsatz

→ Hauptartikel: Dirichletscher Primzahlsatz

Peter Gustav Lejeune Dirichlet

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 von 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 $s=1$ nicht Null werden. Trotzdem findet das Resultat auch in der algebraischen Zahlentheorie Anwendung, zum Beispiel an einer kritischen Stelle vom Beweis des Hasse-Minkowski-Prinzips.

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

→ Hauptartikel: Bertrandsches Postulat

Joseph Bertrand

Das Bertrandsche Postulat sagt aus, dass zwischen jeder Zahl $n\geq 2$ und ihrem Doppelten mindestens eine Primzahl liegen muss. Wählt man etwa $n=3$, so liegt im Bereich $3<p\leq 6$ die Primzahl $p=5$. Es ist benannt nach Joseph Bertrand, der es für alle Argumente $2\leq n\leq 3\,000\,000$ 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 von Euklid, der aus dem Postulat durch beliebig große Wahl von $n$ folgt, macht das Betrandsche Postulat eine erste 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 $p$ eine Primzahl, so gilt für die darauf folgende Primzahl $q$ die Abschätzung $q<2p$.

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.

Primzahlsatz

→ Hauptartikel: Primzahlsatz

Die untere Schranke des Satzes von Euklid für die Anzahl der Primzahlen bis zu einer Größe $x$ 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 $x$ ungefähr ${\tfrac {x}{\log(x)}}$ bemisst, und der relative Fehler in dieser Schätzung für wachsende $x$ gegen 0 strebt. Es gilt also

$\lim _{x\to \infty }{\frac {\pi (x)}{\frac {x}{\log(x)}}}=1.$

Dabei ist $\log(x)$ der natürliche Logarithmus von $x$. Oftmals wird bei der Formulierung des Primzahlsatzes statt der Funktion ${\tfrac {x}{\log(x)}}$ auch der Integrallogarithmus gewählt. Aus $\lim _{x\to \infty }{\tfrac {x}{\log(x)}}=\infty$ ergibt sich der Satz von 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 $n$-te Primzahl ist, wenn man sie in ihrer aufsteigenden Folge 2, 3, 5, 7, ... betrachtet. Das Gesetz lautet $p_{n}\sim n\log(n)$ für die $n$-te Primzahl $p_{n}$, d. h. dass $p_{n}$ auf lange Sicht gleich schnell wächst wie $n\log(n)$. Beispielsweise ist $p_{10\,000}=104\,729$ und $10\,000\log(10\,000)\approx 92\,103$.

Im Gegensatz zu Euklids Beweis der Unendlichkeit der Primzahlen verwendeten die ersten Beweise der Primzahlsätze analytische Methoden, die auf nullstellenfreien Regionen von sog. 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.

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

Bonsesche Ungleichung

→ Hauptartikel: Bonsesche Ungleichung

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

$p_{n+1}<p_{1}\cdot p_{2}\cdots p_{n}.$

Diese konnte von Bonse weiter verbessert werden zu

$p_{n+1}^{2}<p_{1}\cdot p_{2}\cdots p_{n}$

was auch Bonsesche Ungleichung genannt wird.

Verwandte Probleme

Während durch den Satz von Euklid bekannt ist, dass die Menge der Primzahlen unendlich groß ist, erweisen sich Fragestellungen nach der Unendlichkeit gewisser Teilmengen von Primzahlen mitunter schwierig. So ist die Frage, ob es unendlich viele Zwillingsprimzahlen gibt, bis heute nicht beantwortet. Eine Paar $p<q$ aus Primzahlen heißt Zwilling, wenn $q-p=2$ gilt, sich beide also bloß um 2 unterscheiden. Die ersten Primzahlzwillinge sind

$(3,5),(5,7),(11,13),(17,19),(29,31),(41,43),\ldots .$

Viggo Brun

Mit Hilfe des großen Siebs konnte gezeigt werden, dass es eine Konstante $C>0$ gibt, so dass für jedes $x>2$ und die Anzahl $\pi _{2}(x)$ aller Primzahlzwillinge bis $x$ gilt

$\pi _{2}(x)\leq Cx\left({\frac {\log(\log(x))}{\log(x)}}\right)^{2}.$

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

$\left({\frac {1}{3}}+{\frac {1}{5}}\right)+\left({\frac {1}{5}}+{\frac {1}{7}}\right)+\left({\frac {1}{11}}+{\frac {1}{13}}\right)+\left({\frac {1}{17}}+{\frac {1}{19}}\right)+\left({\frac {1}{29}}+{\frac {1}{31}}\right)\cdots <\infty ,$

und zwar gegen die Brunsche Konstante $B\approx 1{,}90216$. Nicht-triviale untere Schranken von $\pi _{2}(x)$ sind mysteriös. Es wurde 1922 von Godfrey Harold Hardy und John Edensor Littlewood vermutet, dass sich die Anzahl $\pi _{2}(x)$ der Primzahlzwillinge unter einer wählbaren Schranke $x$ asymptotisch verhält wie

$\pi _{2}(x)\sim 2C_{1}{\frac {x}{\log ^{2}(x)}}\sim 2C_{1}\int _{2}^{x}{\frac {\mathrm {d} t}{\log ^{2}(t)}}.$

Dabei ist

$C_{1}=\prod _{p\geq 3,\ \mathrm {Primzahlen} }\left(1-{\frac {1}{(p-1)^{2}}}\right)=0{,}660161815846869573927812110014\dots .$

Dies hätte als Konsequenz, dass es unendlich viele Primzahlzwillinge gibt. Auch die Frage, ob es unendlich viele Primzahlvierlinge oder -sechslinge gibt, ist ungeklärt.

Ähnlich verhält es sich mit der Frage, ob unendlich viele Zahlen der Folgen $2^{p}-1$ (mit $p$ Primzahl) bzw. $2^{2^{n}}+1$ wieder Primzahlen sind, siehe auch Mersenne-Primzahl bzw. Fermat-Primzahl.

Literatur

• Paulo Ribenboim: The little book of bigger primes, Springer- Verlag, New York, 2004.

Weblinks

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

• Video: Satz des Euklid. Pädagogische Hochschule Heidelberg (PHHD) 2012, zur Verfügung gestellt von der Technischen Informationsbibliothek (TIB), doi:10.5446/19866.