欧几里得关于素数无穷多的证明

为反证,假设素数只有有限个,设 $p_1, p_2, \dots, p_n$ 是它们的完整列表。

考虑数 $N = p_1 p_2 \cdots p_n + 1$。由于 $N > 1$,它必有至少一个素因子,记为 $p$(大于 $1$ 的每个整数都有素因子)。

由假设,$p_1, \dots, p_n$ 是所有素数的列表,故对某个 $i$,$p$ 必等于 $p_i$。特别地,$p$ 整除乘积 $p_1 p_2 \cdots p_n$。

但 $p$ 也整除 $N = p_1 p_2 \cdots p_n + 1$。若 $p$ 同时整除 $p_1 p_2 \cdots p_n$ 与 $N$,则 $p$ 整除它们的差:$p \mid \big(N - p_1 p_2 \cdots p_n\big) = 1$。

没有任何素数能整除 $1$,因为每个素数都大于 $1$。这是矛盾。因此最初的假设——素数只有有限个——必定为假,所以素数有无穷多个。