Satz des Euklid

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 P₁, P₂, ... P_N.

Das Produkt dieser Primzahlen sei Z.

Z = P₁ × P₂ × ... × P_N

Die Zahl (Z + 1) ist dann per Definition durch keine der Primzahlen teilbar, da jede Division einen Rest von 1 liefert. Jede nicht-Primzahl > 1 lässt sich aber durch eine Primzahl teilen: also ist (Z + 1) selbst eine Primzahl. Diese Primzahl Z + 1 ist aber größer als alle angenommenen Primzahlen P₁, P₂, ... P_N, ein Widerspruch. Die Annahme, es gäbe nur endlich viele Primzahlen, ist also unhaltbar.