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) Primzahlen P₁, P₂, ... P_N. Diese seien o.B.d.A. aufsteigend geordnet, d.h. es gelte

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. Also ist Z + 1 selbst eine Primzahl und als Produkt aller Primzahlen natürlich größer als die angenommene größte Primzahl P_N. Dies widerspricht der urspünglichen Annahme, somit gibt es also keine größte Primzahl.