Der Satz von Euklid besagt, dass es unendlich viele Primzahlen gibt. Der klassische Beweis erfolgt durch Widerspruch. Er setzt eine endliche Liste aller Primzahlen [latex]p_1, p_2, dots, p_n[/latex] voraus. Anschließend wird die Zahl [latex]P = p_1 p_2 cdots p_n + 1[/latex] betrachtet. Diese Zahl [latex]P[/latex] ist entweder eine Primzahl oder nicht. Falls sie eine Primzahl ist, ist sie eine neue Primzahl, die nicht in der Liste enthalten ist.





