Wie viele Primzahlen gibt es?

Der griechische Mathematiker Euklid lebte in Alexandria etwa von 365 bis 355 vor Christi Geburt. Er hat sich mit einer ganzen Reihe von interessanten mathematischen Problemen beschäftigt, unter anderem auch mit der Frage, wie viele Primzahlen es überhaupt gibt.

Er kam zu dem Schluss, dass es keine größte Primzahl geben kann, sondern dass es unendlich viele Primzahlen geben muss. Es sagte sich:

Angenommen, es gäbe eine größte Primzahl P; dann kann man eine neue Zahl N ausrechnen, indem man alle Primzahlen von 2 bis P miteinander multipliziert 2 * 3 * 5 * 7 * 11 * 13 * ... * P und dann noch eine 1 dazu addiert, also:

N = ( 2 * 3 * 5 * 7 * 11 * 13 * ... * P ) + 1.

Wenn nun N eine Primzahl ist, dann ist N auf jeden Fall größer als P.

Wenn N aber keine Primzahl ist, überlegte Euklid, gibt es dann trotzdem eine Zahl Q, die eine Primzahl ist und größer als P ist? Das konnte Euklid so beweisen:

Wenn N keine Primzahl ist, dann kann N in zwei oder mehr Primfaktoren zerlegt werden. Welche und wieviele Primfaktoren das sind, das ist an dieser Stelle egal. Wir brauchen von diesen Primfaktoren nur den kleinsten. Diesen nennen wir einfach mal Q. Zu klären ist nun, ob Q größer als P ist.

Probieren wir erstmal, ob es möglich ist, dass Q kleiner oder gleich P ist. Wir wissen: N geteilt durch Q ist eine ganze Zahl, denn Q ist ein Primfaktor von N. Ist Q eine der Faktoren, aus denen N gebildet wurde, dann können wir N/Q wie folgt ausrechnen:

Beachte: Q ist eine ganze Zahl größer als 1, daher ist 1/Q ein echter Bruch.

Das Ergebnis von N geteilt durch Q ist nach dieser Rechnung keine ganze Zahl, wenn Q eine der bekannten Primzahlen kleiner oder gleich P ist! Das kann nicht sein, denn das widerspricht ja der Festlegung, dass Q ein Primfaktor von N ist.

Also folgerte Euklid: Q muss größer als P sein. Und somit war klar, dass P nicht die größte Primzahl sein konnte. Und wenn man diese Rechnung nun mit der größeren Primzahl Q noch einmal von vorne anfängt, dann wird man nie fertig. Also gibt es keine größte Primzahl.