Schon Euklid fand etwa 300 Jahre vor Christus folgenden Beweis: Angenommen, es gäbe nur endlich viele Primzahlen und n sei ihre Anzahl. Dann könnte man sie mit p1 bis pn bezeichnen. Das Produkt a=p1*p2*… *pn ist dann natürlich durch jede der Primzahlen teilbar, denn sie sind ja alle Faktoren von a. Ist eine Primzahl jedoch ein Teiler von a, kann sie kein Teiler von a+1 sein, denn dann müsste sie folglich auch ein Teiler von 1 sein und wäre somit keine Primzahl. Da von p1 bis pn keine Primzahl a+1 teilt, muss a+1 also entweder selbst eine neue Primzahl sein oder das Produkt aus neuen Primzahlen. Damit gebe es also mindestens n+1 Primzahlen. Das ist ein Widerspruch dazu, dass ihre Anzahl n ist und somit ist die Annahme, es gäbe nur endlich viele Primzahlen, falsch. Folglich gibt es unendlich viele Primzahlen.

Wem der Beweis durch Widerspruch zu abstrakt ist, kann ähnlich wie oben argumentieren, ohne einen Widerspruch verwenden zu müssen. Dazu nimmt man einfach an, es gäbe MINDESTENS n Primzahlen. Das ist eine schwächere Annahme als oben, wo man von GENAU n Primzahlen ausgeht. Dann geht die Argumentation aber genau so wie oben weiter. Man betrachtet die ersten n Primzahlen, multipliziert sie, addiert 1 und erhält dann eine Zahl, die mindestens eine neue Primzahl als Teiler hat. Dann kann man folgen: Gibt es mindestens n Primzahlen, so gibt es sogar mindestens n+1 Primzahlen. Einfacher ausgedrückt: Egal, wie viele Primzahlen man schon gefunden hat, gibt es immer noch mindestens eine weitere. Folglich muss es unendlich viele Primzahlen geben.

Eine noch etwas hübschere Abwandlung des Beweises von Euklid stammt aus dem Jahr 2005. Wenn n eine beliebige natürliche Zahl größer als 1 ist, so haben n und n+1 natürlich keine Primfaktoren gemeinsam, denn so ein Primfaktor müsste dann ja auch Teiler ihrer Differenz, also Teiler von 1 sein. Zusammen genommen haben n und n+1 also mindestens zwei verschiedene Primfaktoren. Also hat auch das Produkt n(n+1) mindestens zwei verschiedene Primfaktoren. Dann verfahren wir mit n(n+1) genau so wie mit n: Wir betrachten nun n(n+1) und n(n+1)+1. Diese haben wieder verschiedene Primfaktoren. n(n+1) hat mindesten zwei (siehe oben) und n(n+1)+1 mindestens einen weiteren. Das Produkt n(n+1)(n(n+1)+1) hat also schon mindestens drei verschiedene Primfaktoren. Dieses Spiel kann man beliebig weiter treiben und erhält in jedem Schritt eine Zahl mit mindestens einem verschiedenen Primfaktor mehr als die Zahl im vorangegangenen Schritt hatte. Folglich muss es unendlich viele Primzahlen geben.

Primzahlen