2. Der Beweis von Leonhard Euler

Wir diskutieren nun einen auf Leonard Euler (1744) zurückgehenden Beweis der Unendlichkeit der Primzahlen, der unendliche Reihen und Produkte verwendet. Hierzu betrachten wir zunächst die spezielle geometrische Reihe der positiven Potenzen von 1/2:

∑_n ≥ 1 ¹_2ⁿ = ¹₂ + ¹₄ + ¹₈ + … + ¹_2ⁿ + …

Diese Reihe hat den Wert 1. Wir können diesen Wert mit Hilfe einer altmodisch organisierten unendlichen Räuberbande veranschaulichen: Der Hauptmann bekommt die halbe Beute. Danach bekommt jeder gemäß seinem Rang die Hälfte von dem, was noch übrig ist. Die ganze Beute wird in dieser Weise verteilt.

Illustration der unendlichen Summe 1/2 + 1/4 + 1/8 + 1/16 + … = 1

Im Kontrast dazu gilt:

Satz (Divergenz der harmonischen Reihe)

Es gilt

∑_n ≥ 1 ¹_n = 1 + ¹₂ + ¹₃ + … + ¹_n + … = ∞.

Die Unendlichkeit der Summe lässt sich mit einem bereits in der Scholastik des Mittelalters gefundenen Argument in einer verblüffend einfachen und anschaulichen Art und Weise beweisen: Wir setzen Klammern derart, dass die Summen innerhalb der Klammern stets größergleich 1/2 sind:

Beweis

Es gilt

¹₁ + ¹₂ + (¹₃ + ¹₄) + (¹₅ + … + ¹₈) + (¹₉ + … + ¹₁₆) + …

≥ ¹₂ + ¹₂ + (¹₄ + ¹₄) + (¹₈ + … + ¹₈) + (¹₁₆ + … + ¹₁₆) + …

≥ ¹₂ + ¹₂ + ¹₂ + … = ∞.

Der Beweis der Unendlichkeit der Primzahlen von Euler verwendet die Divergenz der harmonischen Reihe. Weiter benötigen wir noch die allgemeine Formel für die geometrische Reihe:

Satz (Konvergenz der geometrischen Reihe)

Sei q eine reelle Zahl mit |q| < 1. Dann gilt:

∑_n ≥ 0 qⁿ = 1 + q + q² + … + qⁿ + … = ¹_1 − q.

Beweis

Ausmultiplizieren zeigt, dass

(1 + q + … + qⁿ)(1 − q) = 1 − q^n + 1 für alle n ≥ 0.

(Dies gilt für alle reellen Zahlen q.) Wegen |q| < 1 konvergiert die Potenz q^n + 1 gegen 0, wenn n gegen unendlich konvergiert. Damit gilt

∑_n ≥ 0 qⁿ = lim_{n → ∞} (1 + q + … + qⁿ) = lim_n →∞ ^{1 − q^n + 1}_1 − q = ¹_1 − q.

Für den Spezialfall q = 1/2 erhalten wir 2 als Wert. Im Vergleich zur oben betrachteten Summe beginnt die Summation hier bei q⁰ = 1 und nicht bei q¹ = 1/2, sodass der Wert der Reihe um 1 erhöht ist.

Wir betrachten nun eine Primzahl p. Dann gilt |1/p| < 1 und damit

∑_n ≥ 0 ¹_pⁿ = ¹_1 − 1/p = ^p_p − 1 > 1.

Nach diesen Vorbereitungen können wir nun den Satz von Euklid mit einem ganz neuartigen Argument zeigen:

Satz (Unendlichkeit der Primzahlen)

Es gibt unendlich viele Primzahlen.

Beweis

Annahme, es gibt nur endlich viele Primzahlen p₁ < … < p_k. Dann ist jede natürliche Zahl n ≥ 1 von der Form n = p₁^n₁ … p_k^n_k mit gewissen Exponenten n₁, …, n_k ≥ 0 (Existenz einer Primfaktorzerlegung). Damit erhalten wir durch Anwendung der Formel für die geometrische Reihe, des Distributivgesetzes und der Divergenz der harmonischen Reihe:

∏_{1 ≤ i ≤ k} ¹_{1 − 1/p_i} = ∏_{1 ≤ i ≤ k} ∑_n ≥ 0 ¹_{p_iⁿ}

= ∑_{n₁, … n_k ≥ 0} $\frac{1}{p_{1}^{n_{1}} … p_{k}^{n_{k}}}$ ≥ ∑_n ≥ 1 ¹_n = ∞.

Das endliche Produkt auf der linken Seite (mit k Faktoren) ist also unendlich, Widerspruch.

Verwenden wir die Eindeutigkeit der Primfaktorzerlegung, so können wir die Abschätzung „≥“ durch „=“ ersetzen. Für das Beweisziel der Unendlichkeit der Primzahlen ist dies aber nicht nötig. Es genügt, dass in den Nennern der vorletzten Summe jede natürliche Zahl mindestens einmal auftaucht.

Zur Illustration der Argumentation betrachten wir die entscheidende distributive Umformung für einen endlichen Spezialfall:

Beispiel

Wir beschränken uns auf die Primzahlen p = 2, 3, 5 und auf die natürlichen Zahlen n = 0, 1, 2. Dann gilt:

∏_{p = 2, 3, 5} ∑_{n = 0, 1, 2} ¹_pⁿ = ∏_{p = 2, 3, 5} (¹_p⁰ + ¹_p¹ + ¹_p²)

= (¹_2⁰ + ¹_2¹ + ¹_2²) (¹_3⁰ + ¹_3¹ + ¹_3²) (¹_5⁰ + ¹_5¹ + ¹_5²)

= ∑_{n₁, n₂, n₃ = 0, 1, 2} $\frac{1}{2^{n_{1}} 3^{n_{2}} 5^{n_{3}}}$ ,

wobei die 27 Summanden durch Ausmultiplizieren der drei Produkte entstehen.

Bemerkung

In unserem Beweis verwenden wir unendliche Summen. Dass die distributive Umformung auch hier legitim ist, können wir so einsehen:

Der Wert einer konvergenten unendlichen Reihe ∑_n ≥ 0 x_n ist nach Definition der Limes der Folge ihrer Partialsummen s_n = x₀ + … + x_n. Weiter ist (nach einem Satz über konvergente Folgen) der Grenzwert des gliedweisen Produktes von endlich vielen konvergenten Folgen das Produkt der Grenzwerte der Folgen, sodass wir ein endliches Produkt „∏“ und einen Grenzwert „lim“ vertauschen können. Damit gilt in der Situation des obigen Beweises:

∏_{1 ≤ i ≤ k} ∑_n ≥ 0 ¹_{p_iⁿ} = ∏_{1 ≤ i ≤ k} lim_{n → ∞} ∑_m ≤ n ¹_{p_i^m}

= lim_{n → ∞} ∏_{1 ≤ i ≤ k} ∑_m ≤ n ¹_{p_i^m}

= lim_{n → ∞} ∑_{n₁, … n_k ≤ n} $\frac{1}{p_{1}^{n_{1}} … p_{k}^{n_{k}}}$ ≥ ∑_n ≥ 1 ¹_n = ∞.

Wir verwenden hier nur noch das Distributivgesetz für endliche Produkte und endliche Summen wie im obigen Beispiel.

Aus dem Beweis von Euler gewinnen wir:

Korollar

Es gilt:

(a)	∏_{p prim, p ≤ n} ¹_1 − 1/p ≥ ∑_m ≤ n ¹_m für alle n ≥ 1.

(b)	∏_{p prim} ¹_1 − 1/p = ∞.

Beweis

Sei n ≥ 1. Sind p₁ < … < p_k alle Primzahlen kleinergleich n, so gibt es für jede Zahl m ≤ n Exponenten n₁, …, n_k ≥ 0 mit m = p₁^n₁ … p_k^n_k. Damit folgt wie in obiger Argumentation, dass

∏_{1 ≤ i ≤ k} ¹_{1 − 1/p_i} = ∑_{n₁, … n_k ≥ 0} $\frac{1}{p_{1}^{n_{1}} … p_{k}^{n_{k}}}$ ≥ ∑_m ≤ n ¹_m.

Dies zeigt (a). Für das unendliche Produkt in (b) ergibt sich:

∏_{p prim} ¹_1 − 1/p = lim_{n → ∞} ∏_{p prim, p ≤ n} ¹_1 − 1/p ≥ ∑_n ≥ 1 ¹_n = ∞.

Zum Korollar: Die Partialprodukte ∏_{p prim, p ≤ n} ¹_1 − 1/p (rot)

und die Partialsummen ∑_m ≤ n ¹_m (blau) für n ≤ 100 im Vergleich

Experimentell: Die Partialprodukte ∏_{p prim, p ≤ n} ¹_1 − 1/p (rot)

und die Partialsummen ∑_m ≤ n² ¹_m (blau) für n ≤ 100 im Vergleich

Der Beweis von Euler verwendet grundlegende Ergebnisse der reellen Analysis, allen voran den Konvergenzsatz für die geometrische Reihe und den Divergenzsatz für die harmonische Reihe. Setzen wir diese Ergebnisse als bekannt voraus, so ist der Beweis wieder sehr klar und letztendlich auch kurz: Ein Quotient

^p_p − 1 = ¹_1 − 1/p

lässt sich als unendliche Summe

∑_n ≥ 0 ¹_pⁿ

schreiben. Für große Primzahlen liegen diese Werte nahe bei 1. Multiplizieren wir diese Werte für endlich viele Primzahlen

p₁, p₂, …, p_k

auf, so erhalten wir einen endlichen Wert, erzeugen dabei aber alle Summanden 1/n der harmonischen Reihe, deren Nenner sich mit Hilfe der Primzahlen p₁, …, p_k darstellen lässt (d. h. in der Form n = p₁^e₁ … p_k^e_k mit e_i ≥ 0). Da die harmonische Reihe divergiert, können endlich viele Primzahlen nicht ausreichen, um alle Zahlen n zu erzeugen. Wir können das Argument kurz so beschreiben:

Die Divergenz der harmonischen Reihe erzwingt die Unendlichkeit der Primzahlen.

Mit der Eindeutigkeit der Primfaktorzerlegung erhalten wir:

∏_{p prim} ¹_1 − 1/p = ∑_n ≥ 1 ¹_n.

Wissen wir also bereits, dass es unendlich viele Primzahlen gibt, so können wir hieraus die Divergenz der harmonischen Reihe folgern. Damit zeigt das Argument von Euler stärker:

Die Divergenz der harmonischen Reihe und die Unendlichkeit der Primzahlen sind äquivalent.

Das ist nun wirklich eine neue Einsicht, die ebenso großartig ist wie die Argumentation von Euklid! Die Analysis klopft an die Zahlentheorie und bittet um Eintritt. Eulers Argument ist der Beginn einer großen Partnerschaft.