素数が無限に存在するというユークリッドの証明

背理法として、素数が有限個しかないと仮定し、$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$ はすべての素数のリストであるため、$p$ はある $i$ について $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$ より大きいからである。これは矛盾である。したがって当初の仮定——素数が有限個しかない——は偽でなければならず、素数は無限に存在する。