トップに戻る

素数について

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

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

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

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

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

　N を少なくとも二種類の素因数分解を持つ最小の整数として、N =p₁p₂...p_l =q₁q₂...q_k , p₁≤ p₂≤ ...≤ p_l , q₁≤ q₂≤ ...≤ q_k とおく。
　このとき、p₁, p₂, ..., p_l とq₁, q₂, ..., q_k は共通の素因数を持たない。なぜならば、例えばp₁ =q₁ ならば、N /p₁ =N /q₁ = p₂... p_l= q₂...q_k となって、 N /p₁ もまた少なくとも二種類の素因数分解を持つからである。
　l =1, k >1 ならば、 p₁=q₁q₂...q_k より p₁ が素数であることに反する。l =k =1 ならば、N =p₁=q₁ でなければならない。よって、l >1, k >1でなければならない。
　l >1, p₁<p₂よりp₁² <p₁p₂≤ N, 同様に q₁²<q₁q₂≤N である。したがって、p₁q₁< Nである。 M=N-p₁q₁ とおくと、 0<M <N より、Mは一意の素因数分解を持つ。p₁|N より p₁|M, q₁|N よりq₁|M なので、M を素因数分解すると M =p₁q₁... と表せる。すなわち、p₁q₁|M となる。したがって、 N =M +p₁q₁ も p₁q₁ で割り切れる。 すなわち、N /p₁ は q₁ を素因数にもつ。
　ところが、N /p₁=p₂...p_l と素因数分解される。つまり、N /p₁ は少なくとも二種類の素因数分解を持つことになり、 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氏の著書にはそのいくつかが記されている。