素数とは、正の約数が $1$ とその数自身 $p$ のみである整数 $p > 1$ のことであり、$1$ より大きい整数で素数でないものは $1 < a, b < n$ を満たす $a \cdot b$ の形に分解できるため合成数と呼ばれる。ユークリッドは『原論』（紀元前300年頃）の第7巻定義11および定義13において、これを幾何学的な言葉で「素数とは単位のみによって測られる数であり、合成数とはある数によって測られる数である」と述べている。

ここでの目標は、ユークリッド『原論』第9巻命題20「素数はあらかじめ与えられたどのような個数の素数よりも多い」を証明することである。現代の記法で言えば、すべての素数の集合 $\mathbb{P}$ は無限である（$|\mathbb{P}| = \infty$）。ユークリッドはすべての素数を順番に生み出す公式を作ろうとするのではなく、任意の有限個の素数の集まりから出発して、その集まりに欠けている素数を少なくとも一つ見つけ出す方法を示している。