Warum es unendlich viele Primzahlen gibt

Zweierlei zur Erinnerung: Primzahl heißt eine natürliche Zahl, die nur durch 1 und durch sich selbst teilbar ist. Zum Beispiel sind 2, 3, 37 oder 123 547 Primzahlen. Und: Jede Zahl, die größer ist als 1, ist durch mindestens eine Primzahl teilbar (Beispiele: 30 ist durch die Primzahl 5, 7 ist durch 7 teilbar).

Behauptung: Es gibt unendlich viele Primzahlen.

Beweis: Angenommen, es gäbe endlich viele Primzahlen. Wir nennen diese Anzahl n, und bezeichnen die n Primzahlen mit p1, p2, p3,.. ., pn. Dann müßte dies gelten:

(*) Jede beliebige Zahl, die größer ist als 1. ist durch mindestens eine der Primzahlen pl, p2,... pn teilbar.

Wir multiplizieren jetzt alle n Primzahlen miteinander und zählen dann 1 dazu. Die so erhaltene Zahl pl*p2* ... *pn + 1 ist mit Sicherheit durch keine der n Primzahlen teilbar (stets bleibt ein Rest von 1). Dies widerspricht aber dem oben mit (*) bezeichneten Satz. Also muß unsere Annahme, es gäbe "endlich" viele Primzahlen, falsch sein. Mithin ist das Gegenteil richtig: Es gibt "unendlich" viele.

Quod erat demonstrandum