素数是指正因数只有 $1$ 和 $p$ 本身的整数 $p>1$;每个不是素数的整数 $n>1$ 都是合数,即可以分解为 $n=a\cdot b$,其中 $1<a,b<n$。欧几里得《原本》(约公元前300年)第九卷命题20的目标——Heath 的英译表述为“素数多于任意指定的一批素数”——是证明集合 $\mathbb{P}=\{2,3,5,7,11,\dots\}$ 不可能被任何有限的清单穷尽。

注意欧几里得本人表述的逻辑形态:它并非断言“素数有无穷多个”,而是一个构造——给我任意指定的一批素数,我就能找出一个不在其中的素数。无穷只以“有限清单不可能完备”的形式出现,这正是古希腊数学处理无穷的方式。

证明依赖《原本》此前已经建立的两根支柱:每个大于 $1$ 的整数都有素因子(第七卷命题31),以及一个初等事实——两个数的公约数也整除它们的差,这正是第3步“+1”技巧的发动机。