素数とは、正の約数が $1$ と $p$ 自身だけである整数 $p>1$ のことであり、素数でない整数 $n>1$ はすべて合成数、つまり $1<a,b<n$ を満たす $n=a\cdot b$ と分解される。ユークリッド『原論』(紀元前300年頃)第IX巻命題20の目標は——ヒースの英訳では「素数は、与えられたどんな素数の集まりよりも多い」——集合 $\mathbb{P}=\{2,3,5,7,11,\dots\}$ がどんな有限リストによっても尽くされないことを示すことである。

ユークリッド自身の記述の論理形に注目してほしい。これは「素数は無限に存在する」とは言わず、構成として述べられている——与えられた素数の集まりをどれでも持ってこい、そこに含まれない素数を示そう。無限は、有限リストの完全性が不可能であるという形でのみ現れる。これはまさに古代ギリシャ数学が無限を扱った仕方である。

証明は『原論』ですでに確立された二つの柱に拠る。$1$ より大きい整数はすべて素因数を持つこと(第VII巻命題31)、および二つの数の約数はその差も割り切るという初等的事実——手順3の「+1」の仕掛けのエンジンである。