素数

だからこそ素数は算術の「原子」と呼ばれる。それぞれの数を作るレシピはただ一通りしかなく、素数とその指数を知れば、その数の約数についてすべてが分かる。

存在性（最小反例法）： 素数の積として書けない整数 $n > 1$ が存在すると仮定し、そのような最小の整数を $m > 1$ とおく。素数はそれ自身1個の素数の積なので $m$ は合成数であり、$1 < a, b < m$ を満たす整数によって $m = a b$ と書ける。$m$ の最小性より $a$ と $b$ はともに素数の積であるため、その積 $m = a b$ も素数の積となり矛盾する。

ユークリッドの補題： 素数 $p$ が $p \mid a b$ かつ $p \nmid a$ を満たすとする。$p$ は素数で $p \nmid a$ だから $\gcd(p, a) = 1$ である。ベズーの等式より $p x + a y = 1$ を満たす整数 $x, y$ が存在する。両辺に $b$ を掛けると $p(b x) + (a b)y = b$ となり、$p$ は $p(b x)$ と $a b$ の両方を割り切るので $p$ は右辺も割り切り、$p \mid b$ が従う。

一意性： 背理法により2通りの異なる素因数分解をもつ整数が存在するとし、そのような最小の整数を $n = p_1 p_2 \cdots p_r = q_1 q_2 \cdots q_s$（ただし $p_1 \le \cdots \le p_r$ かつ $q_1 \le \cdots \le q_s$）とおく。$p_1 \mid q_1 q_2 \cdots q_s$ よりユークリッドの補題を繰り返し適用すると、$p_1$ はある素数 $q_j$ を割り切り、$p_1 = q_j \ge q_1$ となる。対称性から $q_1 \ge p_1$ も成り立つので $p_1 = q_1$ である。両辺を $p_1$ で割ると、より小さい整数 $n / p_1 < n$ が2通りの異なる素因数分解をもつことになり、$n$ の最小性に矛盾する。

ユークリッドの論法(紀元前300年頃):素数が有限個 $p_1, p_2, \ldots, p_k$ しかないと仮定する。それらすべてを掛け合わせて1を足す:$N = p_1 p_2 \cdots p_k + 1$。$N$ をどの $p_i$ で割っても余りは1になるので、どの $p_i$ も $N$ を割り切らない。しかし $N$ は(算術の基本定理により)何らかの素因数を持たねばならず、それはリストにない素数である。よって、そのリストは最初から完全ではなかった。

ステップ1（ユークリッド数の構成）： $\{p_1, p_2, \dots, p_k\}$ を任意の有限個の素数の集合とする。リスト内のすべての素数の積に $1$ を足した整数 $N = p_1 p_2 \cdots p_k + 1$ を作る。$p_1 \ge 2$ より $N \ge 2 + 1 = 3 > 1$ である。

ステップ2（素因数の存在）： 算術の基本定理により、すべての整数 $N > 1$ は少なくとも1つの素因数 $q$ をもち、$q \mid N$ となる（$N$ 自身が素数なら $q = N$、$N$ が合成数なら $q < N$）。

**ステップ3（$q$ が新しい素数であることの証明）：** 背理法により、ある番号 $i$ について $q = p_i$ と仮定する。すると $q \mid p_1 p_2 \cdots p_k$ であり、かつ $q \mid N$ なので、素数 $q$ はその差 $q \mid (N - p_1 p_2 \cdots p_k) = 1$ を割り切らなければならない。しかしすべての素数は $q \ge 2$ を満たすためこれは不可能である。ゆえに $q \notin \{p_1, p_2, \dots, p_k\}$ であり、いかなる有限リストもすべての素数を含み得ないことが証明された。