8. Die Größe der nächsten Primzahl

Ein mathematischer Beweis zeigt einen bestimmten Satz. In vielen Fällen wird aber mehr als die behauptete Aussage bewiesen und wir haben bereits gesehen, dass es lohnt sich, diese zusätzliche Information zu analysieren und explizit festzuhalten. Dass wir Euklids Beweis noch keineswegs erschöpfend behandelt haben, zeigt die folgende Überlegung:

Ist n ≥ 1 beliebig und sind p₁ < … < p_n die ersten n Primzahlen, so ist jeder Primteiler p von a = p₁ · … · p_n + 1 von p₁, …, p_n verschieden ist. Da wir die ersten n Primzahlen ohne Auslassungen zugrunde gelegt haben, gilt p_n < p ≤ a. Im Fall n = 1 ist p = a = 3. Ist n ≥ 2, so gilt

a = p₁ · … · p_n + 1 = 2 · 3 · … · p_n + 1 < p_nⁿ.

Damit erhalten wir:

Korollar (Größenabschätzung für die nächste Primzahl)

Für alle n ≥ 1 sei p_n die n-te Primzahl. Dann gilt für alle n ≥ 2:

p_n < p_n + 1 ≤ p₁ · … · p_n + 1 < p_nⁿ.

Zur Illustration des Ergebnisses betrachten wir die folgende Tabelle mit Primzahlen (erste Spalte), Nachfolgerprimzahlen (zweite Spalte) und den Plus-Eins-Zahlen wie im Beweis von Euklid:

p₁ = 2	p₂ = 3	p₁ + 1 = 2
p₂ = 3	p₃ = 5	p₁ · p₂ + 1 = 7
p₃ = 5	p₄ = 7	p₁ · p₂ · p₃ + 1 = 31
p₄ = 7	p₅ = 11	p₁ · … · p₄ + 1 = 211
p₅ = 11	p₆ = 13	p₁ · … · p₅ + 1 = 2311
p₆ = 13	p₇ = 17	p₁ · … · p₆ + 1 = 30031

Die Größenabschätzung, die der Beweis des Satzes von Euklid liefert, ist also bereits für die ersten Primzahlen nicht besonders gut. Wir werden bei der Diskussion alternativer Beweise der Unendlichkeit der Primzahlen andere Abschätzungen kennenlernen. Im Abschnitt über die Verteilung der Primzahlen werden wir zudem das Bertrandsche Postulat diskutieren, demzufolge zwischen jeder Zahl größergleich 2 und ihrem Doppelten mindestens eine Primzahl liegt. Für die Primzahlaufzählung bedeutet dies, dass p_n < p_n + 1 < 2p_n für alle n ≥ 1 gilt. Aus dem Argument von Euklid können wir diese Abschätzung nicht gewinnen. Aber immerhin haben wir eine erste obere Schranke gefunden: Zwischen p_n und p_nⁿ liegt immer mindestens eine Primzahl.