Beweis, dass es unendlich viele Primzahlen gibt. Der Beweis geht auf den griechischen Mathematiker Euklid zurück, der um 300 v. Chr. in Alexandria lebte. Sein Beweis beruht auf einer einfachen Widerspruchsüberlegung:
Angenommen, es gäbe nur endlich viele (insgesamt N) Primzahlen P1, P2, ... PN. Diese seien o.B.d.A. aufsteigend geordnet, d.h. es gelte
P1 < P2 < ... < PN
Das Produkt dieser Primzahlen sei Z.
Z = P1 × P2 × ... × PN
Die Zahl (Z + 1) ist dann per definition durch keine der Primzahlen teilbar, da jede Division einen Rest von 1 liefert. Also ist Z + 1 selbst eine Primzahl und als Produkt aller Primzahlen natürlich größer als die angenommene größte Primzahl PN. Dies widerspricht der urspünglichen Annahme, somit gibt es also keine größte Primzahl.