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 $\zeta (3)$ · Primzahlsatz

Satz von Euklid

Aussage

Es gibt unendlich viele Primzahlen.

Konstruktive Beweise

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.)

Euklid geht von einer endlichen Menge $\{p_{1},p_{2},\ldots ,p_{r}\}$ von Primzahlen aus und bildet die Zahl

$N=p_{1}\cdot p_{2}\cdot p_{3}\cdot \ldots \cdot p_{r}\ +1.$

Diese Zahl ist durch keine der Primzahlen $p_{i}$ teilbar, da immer ein Rest 1 verbleibt. Damit sind die Primfaktoren von $N$ 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 $N$ ist nicht notwendigerweise selber eine Primzahl, siehe etwa $N=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13+1=59*509.$

Beweise, die die Existenz unendlich vieler paarweise teilerfremder Zahlen zeigen

Es gibt verschiedene Beweise, die alle auf demselben Prinzip aufbauen: Ist $M$ 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 $M$ 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)

Es sei $F_{n}=2^{2^{n}}+1$ für $n\geq 0$ die Folge der Fermat-Zahlen. Es gilt

$F_{m}-2=F_{0}\cdot F_{1}\cdot \ldots \cdot F_{m-1}.$

Diese Aussage lässt sich beispielsweise mit vollständiger Induktion zeigen. Daraus folgt für $n<m$, dass $F_{n}$ die Zahl $F_{m}-2$ teilt. Damit folgt

$\operatorname {ggT} (F_{m},F_{n})=\operatorname {ggT} (F_{m}-(F_{m}-2),F_{n})=\operatorname {ggT} (2,F_{n}).$

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

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

Stieltjes’ Beweis (1890)

Angenommen, $p_{1},p_{2},p_{3},\ldots ,p_{r}$ seien die einzigen Primzahlen, die existieren. Dann kann man die Zahl

$N=p_{1}\cdot p_{2}\cdot p_{3}\cdot \ldots \cdot p_{r}\$

auf verschiedene Arten in der Form $N=m\cdot n$ zerlegen. Jede Primzahl $p_{i}$ teilt entweder $m$ oder $n$, aber nicht beide zugleich. Aus diesem Grund ist $m+n$ durch keine der existierenden Primzahlen teilbar (einer der Summanden $m$ und $n$ ist jeweils teilerfremd zu der Primzahl und somit ein Rest). Da aber $m+n>1$ ist, ist $m+n$ eine weitere, größere Primzahl oder durch eine weitere noch unbekannte Primzahl teilbar.

Anmerkung: Im Spezialfall $m=1,n=N$ ist dies genau Euklids Beweis.

Nichtkonstruktive Beweise

Eulerprodukt für die harmonische Reihe

Als Motivation betrachten wir das Produkt

$\left(1+{\frac {1}{2}}+{\frac {1}{4}}+{\frac {1}{8}}\right)\cdot \left(1+{\frac {1}{3}}+{\frac {1}{9}}\right)$

${}=1+{\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{4}}+{\frac {1}{6}}+{\frac {1}{8}}+{\frac {1}{9}}+{\frac {1}{12}}+{\frac {1}{18}}+{\frac {1}{24}}+{\frac {1}{36}}+{\frac {1}{72}}$

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 $1/16$ hinzufügen, kämen diejenigen Zahlen hinzu, die den Primfaktor 2 viermal enthalten.

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

$\left(1+{\frac {1}{2}}+{\frac {1}{4}}+{\frac {1}{8}}+\ldots \right)\cdot \left(1+{\frac {1}{3}}+{\frac {1}{9}}+{\frac {1}{27}}+\ldots \right)$

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:

$1+{\frac {1}{p}}+{\frac {1}{p^{2}}}+{\frac {1}{p^{3}}}+\ldots ={\frac {1}{1-1/p}}.$

Die obige Rechnung funktioniert auch für mehr als zwei Primzahlen: Ist $\{p_{1},\ldots ,p_{r}\}$ eine beliebige endliche Menge von Primzahlen, so ist das Produkt

$Q={\frac {1}{1-1/p_{1}}}\cdot {\frac {1}{1-1/p_{2}}}\cdots {\frac {1}{1-1/p_{r}}}$

gleich der Summe der Kehrwerte aller natürlichen Zahlen, die durch keine anderen Primzahlen als $p_{1},\ldots ,p_{r}$ teilbar sind.

Wären nun $p_{1},\ldots ,p_{r}$ bereits alle Primzahlen, so wäre die Zahl $Q$ also gleich der Summe der Kehrwerte aller natürlichen Zahlen, also gleich der harmonischen Reihe

$1+{\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{4}}+{\frac {1}{5}}+{\frac {1}{6}}+\ldots$

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

Anmerkung: Die Überlegung liefert allgemein eine Produktdarstellung

$1+{\frac {1}{2^{s}}}+{\frac {1}{3^{s}}}+{\frac {1}{4^{s}}}+\ldots =\prod _{p\ \mathrm {prim} }(1-p^{-s})^{-1}.$

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

Wikipedia-Verweise

• Primzahl
• Satz von Euklid