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

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

定理 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\le p_2\le \cdots ,q_1\le q_2\le \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 \widehat{q_i}\cdots q_m$

（ここで $\widehat{q_i}$ は $q_1,q_2,\dots ,q_m$ のうち $q_i$ のみ現れないことを指す）となり、 $N/p_1$ も2通り以上に素因数分解される数となり $N$ がそのような最小の数と仮定したことに反する。よって $p_1\ne q_i$ である。特に $p_1\ne q_1$ である。

素数自身は1通りの素因数分解しか持っていないから $N$ は合成数でなければならず $n,m\ge 2$ である。よって $p_1^2\le p_1{p}_2\le N,q_1^2\le q_1{q}_2\le N$ つまり $p_1,q_1\le \sqrt{N}$ である。 $p_1\ne 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,\dots ,q_n$ のいずれかと一致しなければならず、前に述べた $p_1\ne q_1$ に反する。

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