Zum Beweis dafür, daß es unendlich viele Primzahlen gibt, nimmt Euklid im neunten Buch seiner „Elemente“ zunächst das Gegenteil an, um es dann ad absurdum zu führen.

Angenommen also, es gäbe genau n Primzahlen, wobei n eine (vielleicht sehr große) endliche Zahl bezeichne. Dann ließen sich sämtliche Primzahlen in dieser Form auflisten: pl, p2, p3,..., pn. Hierbei wäre zum Beispiel pl die Zwei, p2 die Drei, p3 die Fünf und so fort. Jede andere natürliche Zahl müßte dann durch mindestens eine der Primzahlen aus dieser vollständigen Liste teilbar sein.

Jetzt wird die Zahl N betrachtet, die das Produkt aus sämtlichen n Primzahlen sein soll, also N = pl mal p2 mal p3 mal ... mal pn. Zu dieser Zahl wird eine Eins hinzugezählt, so daß wir N + 1 erhalten. Diese Zahl N + 1 ist aber durch keine der Primzahlen pl, p2,...,pn teilbar, denn sie hinterließe bei jedem solchen Teilungsversuch eine 1 als Rest. Mithin können pl, p2,...,pn nicht sämtliche Primzahlen sein, wiewohl dies die vollständige Liste sein sollte.

Da also die Annahme, es gäbe endlich viele Primzahlen, zu einem Widerspruch führt, muß es unendlich viele Primzahlen geben.