初等整数論/算術の基本定理の直接証明

以前に解説した算術の基本定理の証明は間接的なものであった（ただし、代数体の整数論にも拡張しうる点で重要である）。実は算術の基本定理は直接証明することもできる。本記事ではそれについて解説する。

定理 1.13 (算術の基本定理, 素因数分解の一意性／再掲）

素因数分解は順序を考慮しなければただ一通りに表せる。

証明
素因数分解が存在することは定理 1.10で既に触れた。したがって、今すべきことは2通り以上に素因数分解される数が存在しないことを証明することとなる。 仮にそのような数が存在したとして、その最小のものを $N$ とし、その異なる素因数分解を以下のように表す。

$N=p_{1}p_{2}p_{3}\cdots p_{n}=q_{1}q_{2}q_{3}\cdots q_{m},p_{1}\leq p_{2}\leq \cdots ,q_{1}\leq q_{2}\leq \cdots$

すなわち $p_{1}$ は前者の素因数分解に現れる素数の中で最小のものであり $q_{1}$ は後者の素因数分解に現れる素数の中で最小のものである。

このとき $p_{1}=q_{i}$ とすると

$N/p_{1}=N/q_{i}=p_{2}p_{3}\cdots p_{n}=q_{1}q_{2}\cdots {\hat {q_{i}}}\cdots q_{m}$

（ここで ${\hat {q_{i}}}$ は $q_{1},q_{2},\ldots ,q_{m}$ のうち $q_{i}$ のみ現れないことを指す）となり、 $N/p_{1}$ も2通り以上に素因数分解される数となり $N$ がそのような最小の数と仮定したことに反する。よって $p_{1}\neq q_{i}$ である。特に $p_{1}\neq q_{1}$ である。

素数自身は1通りの素因数分解しか持っていないから $N$ は合成数でなければならず $n,m\geq 2$ である。よって $p_{1}^{2}\leq p_{1}p_{2}\leq N,q_{1}^{2}\leq q_{1}q_{2}\leq N$ つまり $p_{1},q_{1}\leq {\sqrt {N}}$ である。 $p_{1}\neq q_{1}$ だから $p_{1}q_{1}<N$ である。

$M=N-p_{1}q_{1}$ とおくと $0<M<N$ より $M$ は1通りの素因数分解しか持たない。 ところで

$M=p_{1}p_{2}p_{3}\cdots p_{n}-p_{1}q_{1}=p_{1}(p_{2}p_{3}\cdots p_{n}-q_{1}),$

$M=q_{1}q_{2}q_{3}\cdots q_{m}-p_{1}q_{1}=q_{1}(q_{2}q_{3}\cdots q_{m}-p_{1})$

より $M$ は $p_{1},q_{1}$ の両方で割り切れるから $M$ の素因数分解には $p_{1},q_{1}$ が共に現れなければならない。つまり $M$ は $p_{1}q_{1}$ の倍数である。よって $N=M+p_{1}q_{1}$ も $p_{1}q_{1}$ の倍数でなければならない。したがって $N/q_{1}=q_{2}q_{3}\cdots q_{m}$ は $p_{1}$ の倍数でなければならないが、$N/q_{1}$ は $N$ より1通りの素因数分解しか持たない。しかし、そうなると $p_{1}$ は $q_{2},q_{3},\ldots ,q_{n}$ のいずれかと一致しなければならず、前に述べた $p_{1}\neq q_{1}$ に反する。

よって矛盾が生じるのが避けられないことから2通り以上に素因数分解される数は存在しないことが導かれた。