素因数分解の一意性

2009年6月27日作成／2025年5月25日一部修正

素数について

素数、すなわち $1$ と自分自身でしか割れない数は整数の世界において最も重要な対象の一つである。

$1$ より大きな整数 $N$ が素数でなければ、$N$ は $1$ と $N$ の間に約数 $N_1$ を持っている。だから、$N=N_1 M_1$ とかける。 ここで、 $N_1$ が素数ならばそれでよし、素数でないならば、その $N_1$ もまた $1$ と $N_1$ との間に約数 $N_2$ を持っている。 M1 についても同じように考えていく。そのように繰り返していくと、いつか素数に辿り着く。 なぜなら、$N>N_1>N_2>\cdots$ と小さくなっていくが、無限に小さくなることはないからである。

　よって、$1$ より大きな整数は必ず素数の積として表せる。たとえば、$24=4\times 6, 4=2\times 2, 6=2\times 3$ だから、$24=2\times 2\times 2\times 3=2^3\times 3$ と素数の積で表される。

　しかも、算術の基本定理といって、$1$ より大きな整数は必ず素数の積に一意的に表示できる。ただし、ここで例えば $6=2\times 3=3\times 2$ は、$2$ と $3$ の現れる順序が違うだけなので、そのようなものは同一視する。
　素数が整数の世界において重要なのは、整数が素数の積に、しかも一意的に表示できるからである。

　算術の基本定理の証明は複数のものが知られているが、筆者の知る限りで最も単純だと思うものを上げる。

　$N$ を少なくとも二種類の素因数分解を持つ最小の整数として、$N=p_1 p_2 \cdots p_\ell=q_1 q_2 \cdots q_k, p_1\leq p_2\leq \cdots \leq p_\ell, q_1\leq q_2\leq \cdots q_k$ とおく。
　このとき、$p_1, p_2, \ldots, p_\ell$ と $q_1, q_2, \ldots, q_k$ は共通の素因数を持たない。なぜならば、例えば $p_1=q_1$ ならば、$N/p_1=N/q_1=p_2 \cdots p_\ell=q_2 \cdots q_k$ となって、 $N/p_1$ もまた少なくとも二種類の素因数分解を持つからである。
　$\ell=1, k>1$ ならば、 $p_1=q_1 q_2 \cdots q_k$ より $p_1$ が素数であることに反する。$\ell=k=1$ ならば、$N=p_1=q_1$ でなければならない。よって、$\ell>1, k>1$ でなければならない。
　$l>1, p_1\leq p_2$ より $p_1^2\leq p_1 p_2 \leq N$, 同様に $q_1^2\leq q_1 q_2\leq N$ である。$p_1\neq q_1$ だから $p_1 q_1 　ところが、$N/p_1=p_2 \cdots p_\ell$ と素因数分解される。つまり、$N/p_1$ は少なくとも二種類の素因数分解を持つことになり、$N$ の最小性に矛盾する。
　ここから、$N$ の素因数分解の一意性が示せた。（証明終）

---

　素数は整数の世界において重要な対象であるが、素数それ自体の探求もまた多くの人をひき付けるテーマである。

　素数はどれだけ存在しているか。素数をどのようにして見つけ出せばいいのだろうか。など、素数に関する問題は無数にある。
　Paulo Ribenboim氏の素数に関する著書、 The New Book of Prime Number Records, Springer-Verlag, 1996 では、素数について次の6つのテーマに分けて扱っている。

1. 素数はどれだけたくさん存在するか？
2. ある自然数が素数か否かどうやって判定するか？
3. 素数を定義する関数は存在するか？
4. 素数はどのように分布しているか？
5. どのような特殊な素数が考察されてきたか？
6. 素数に関する発見的・確率論的な結果

　このうち、すぐに答えられるのは最初の問いである。すなわち、素数は無限に多く存在する。
　これはユークリッドの有名な定理である。ユークリッドの証明は次の通りである。素数が有限個しか存在しないとして、すべての素数の積に1を加えた数を考える。この数も素因数を一つ持つが、その素数は「すべての素数の積」の素因数になっていなければならない。よって、その素数は1を割り切ることになり、矛盾する。よって、素数は無限に多く存在しなければならない。

　素数が無限に多く存在することの証明は他にもたくさんある。Paulo Ribenboim氏の著書にはそのいくつかが記されている。

　（5/25/2025追記）素因数分解が一意的であることの証明も他にもたくさんある。当サイトの「初頭整数論の基本定理の証明」にそのいくつかを紹介している。このページで紹介した証明は G. H. Hardy and E. M. Wright, D. R. Heath-Brown, J. Silverman, A. Wiles, An Introduction to the Theory of Numbers, the 6th edition, Oxford University Press, 2008 の 2.11節の証明を参考とした。