Satz: Der Abstand zwischen zwei aufeinanderfolgenden Primzahlen kann beliebig groß werden.
Beweis: Die Zahlen n! + 2, n! + 3, ..., n! + n sind alle keine Primzahlen, denn n! ist durch 2 teilbar, also ist es n! + 2 auch; n! ist durch 3 teilbar, also ist es n! + 3 auch usw. Schließlich ist n! + n durch n teilbar, also ist es n! + n auch.
Der Abstand zwischen der letzten Primzahl vor n! + 2 und der ersten Primzahl nach n! + n beträgt also mindestens n.
Da n beliebig groß werden kann, gibt es auch einen beliebig großen Abstand zwischen zwei aufeinanderfolgenden Primzahlen.
Beispiel: Sei n = 5, also n! = 120. Dann sind die 5 Zahlen 122, 123, 124, 125, 126 keine Primzahlen.
Satz: Es gibt unendlich viele Primzahlen.
Beweis: Angenommen, die Menge P der Primzahlen sei endlich, also P = { p1, ..., pk } mit k ∈ ℕ0.
Sei nun m das Produkt aller dieser Primzahlen:
m = p1 · ... · pk
und sei
n = m + 1.
Dann ist n > 1. Sei d ein Primfaktor von n, d.h. d ∈ P und d | n. Dann gilt
| d | n | |||
| ⇒ | d | m + 1 | ||
| ⇒ | d | 1 | (da d | m mit m = p1 · ... · pk) | |
| ⇒ | d = 1 | ||
| ⇒ | d ∉ P |
Dies ist ein Widerspruch dazu, dass d ∈ P gilt; also ist die Annahme falsch.
Etwas einfacher ist noch folgender Beweis:
Beweis: Angenommen, n sei die größte Primzahl. Dann bilden wir die Zahl z = n! + 1. Diese Zahl z ist größer als n und damit zusammengesetzt. Sei nun d ein Primfaktor von z, d.h. d | z und d prim. Da d prim, gilt d ≤ n und damit d | n!.
Somit gilt
| d | z | |||
| ⇒ | d | n! + 1 | ||
| ⇒ | d | 1 | (da d | n!) | |
| ⇒ | d = 1 |
Dies ist ein Widerspruch dazu, dass d prim ist; also ist die Annahme falsch.