fundamentale Ausage über die Existenz unendlich vieler Primzahlen.

Bei Euklid findet sich der erste Beweis für folgenden Satz:

Es gibt unendlich viele Primzahlen.

In moderner Formulierung liest sich Euklids Beweis so: Ist A = {p₁,…, p_k} eine beliebige gegebene endliche Menge von Primzahlen, so ist die Zahl \begin{eqnarray}n={p}_{1}\cdot \ldots \cdot {p}_{k}+1\equiv 1\space \mathrm{mod}\space \space {p}_{j}\end{eqnarray} für jedes p_j ∈ A, also durch keine der Primzahlen aus A teilbar. Da es aber sicher eine Primzahl p gibt, die n teilt, enthält A noch nicht alle Primzahlen. Weil aber A eine beliebige endliche Menge von Primzahlen war, kann die Menge aller Primzahlen nicht endlich sein.

Dieser Beweis wird häufig als einer der ältesten „eleganten“ Beweise der Mathematik zitiert.