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) unterschiedliche Primzahlen P1, P2, ... PN. Diese seien o.B.d.A. (ohne Beschränkung der Allgemeinheit) 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. Da die Menge aller Primzahlen demnach kein größtes Element hat, ist die Zahl ihrer Elemente unendlich.