素数は無限個存在する

前回, 算術の基本定理を学び, どのような自然数も素数の積に掛け算の順番を除いては一意的に書けることを証明しました｡ 与えられた自然数を素数の積に分解することを素因数分解と言うのでした｡ この｢数の原子｣とも言える素数を深く知ることが様々な数の性質を研究する上で重要です｡ 素数に関する研究で数多くの謎が解明されてきましたが, 未だに素数は謎でいっぱいです｡ 問題文を理解するのはすごく簡単でも, 世界中の誰もが解けていない問題もたくさんあります｡

これまでの人類の知の財産として築かれてきた素数に関する知識をこれからご紹介していきたいと思います｡ さらに, 一緒に未解決問題にも挑戦してみましょう｡ 問題を理解し, どのような予想が立てられるか, 色々と考えてみましょう｡

さて, 数を構成する上で基礎的なブロックの素数ですが, 素朴な疑問として素数は何個あるのでしょうか? すべての素数をメモしたノートを持っていれば, どんな自然数が必要になってもノートに書かれた素数を掛け合わせば得ることができる, そんな素数ノートはあるのでしょうか? 現実には, そのようなノートは存在しません｡ というのも素数は無限個あることが知られているからです｡ それも紀元前3世紀頃にはすでに証明されていたのです｡ とても歴史のある事実ですね｡

いきなり無限個あると言われても実感がわかないので少し素数の個数に関するデータをみてみましょう｡ (後でこれらのデータをPythonを使って得る方法を説明します｡)

まず, 10以下の素数は2, 3, 5, 7の4つですね｡ 割り合いでいうと\(4/10=0.4\), つまり40%くらいは素数ですね｡ 次に100以下の素数をリストしてみます:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

全部で25個あるので割合は\(25/100=0.25\)となり25%は素数になります｡ 割り合いが40%から25%に減りましたね｡ このように\(n\)個以下の素数の個数を計算して割合を求めていきましょう｡ 便利のためにこの｢\(n\)個以下の素数の個数｣に\(\pi(n)\)という名前をつけましょう｡ これまでのデータから\(\pi(10)=4\)と\(\pi(100)=25\)がわかっています｡ \(n\)をもっと大きくしたときの\(\pi(n)\)を計算した結果をしたの表にまとめてみました｡

この表の最初の列は\(n\)を, 二番目は\(n\)以下の素数の個数\(\pi(n)\), 三番目の列は割合\(\pi(n)/n\)です｡ ここから読み取れるのは\(n\)が大きくなるにつれて素数の個数は増えていますが割合は徐々に減っているということです｡ このまま\(n\)の値が大きくなっていったらそのうち割合がゼロになって新しい素数は見つからなくなってしまうのではと不安になりますね｡ 次は\(\pi(n)\)をグラフにしてその動きを見てみましょう｡ まずは\(n\)が10までの\(\pi(n)\)のグラフです｡ 階段状のグラフが得られました｡ \(n\)が素数のときに階段が一段上がっています｡

次に\(n\)が100までの\(\pi(n)\)のグラフです｡ これも\(n\)が素数になるたびに階段が一段上がっています｡

次が\(n\)が1000までの\(\pi(n)\)のグラフです｡ これも階段状のグラフですが, \(n\)が大きいため段差が目立たなくなって来ました｡

最後に\(n\)が\(1000000=10^6\)までのグラフです｡ (このグラフは\(10^6\)までの整数\(0\)から\(1000\)ずつ増やして\(\pi(n)\)の値を計算してあります｡)

さて, これらのグラフを眺めていると徐々に\(\pi(n)\)の値は\(n\)が大きくなるにつれ大きくなっているように見て取れます｡ ただグラフを見る上で注意しなくてはならないのはこれまでのグラフのy軸はx軸(nの値)の目盛りより小さいということです｡ では試しに\(y=x\)のグラフも一緒に書いてみましょう｡

するとどうでしょう｡ \(y=x\)のグラフに比べて\(\pi(n)\)のグラフは上昇具合が緩やかですね｡ これが\(n\)までの素数の割合が上のテーブルでゼロに向かっていた理由です｡ それでは\(\pi(x)\)の上昇具合をうまく表す関数はあるのでしょうか? その答えは素数定理と呼ばれる定理によって与えられています｡ 素数定理によれば\(\pi(n)\)の上昇具合はだいたい\(n/\ln(n)\)と等しいということです｡ ここで\(\ln(n)=\log_{e}(n)\)は自然対数とよばれる底が\(e\)(ネイピア数)の対数です｡ この定理の証明は今の段階ではとても難しいので与えません｡ では\(\pi(n)\)のグラフに\(n/\ln(n)\)のグラフを書き加えてみます｡

するとどうでしょうか｡ 2つのグラフはピッタリと一致するわけではありませんが, かなり近いところにあることが見てとれます｡ 素数定理はこの2つの比(\(\pi(n)/(n/\ln(n))\))が\(n\)が大きくなるにつれて1に近づくことを主張する定理です｡

さて, これまで素数の個数のデータとグラフを見てきて素数が無限個ありそうだなと思えてきませんか? もちろん素数定理から素数が無限個あることは従うのですが, 素数定理の証明は難解で比較的最近(1896年)証明されました｡ 一方, 素数が無限個あるという事実自体は先に述べたように紀元前3世紀頃には証明されていました｡ そこで私たちはそんな古代からあるユークリッドの原論に記された証明を学んでみましょう｡

素数が無限個あることの証明

素数が無限個あることを証明したいのですが, 仮に有限個しかないと仮定してみましょう｡ もしこの仮定の下で矛盾が得られた場合にはこの仮定が誤り, すなわち素数が無限個存在することが証明されたことになります｡

素数が有限個しかないと仮定しているので\(p_1, p_2, \dots, p_k\)をすべての素数としましょう｡ つまり\(k\)個しか素数がないということです｡ このときに次の式で定義される自然数\(N\)を考えます｡ \[N=p_1p_2\dots p_k +1.\]

さて, 算術の基本定理からどんな自然数も素数の積に分解できるのでした｡ つまり\(N\)は素数たち\(p_1, p_2, \dots, p_k\)を組み合わせた(同じものを何回使ってもよい)積で表すことができます｡ 添字は本質的なものではないので\(p_1\)が\(N\)の素因数分解に含まれる素数としましょう｡ つまり\(p_1\mid N\)です｡ これと\(p_1 \mid p_1p_2 \cdots p_k\)を合わせると \[ p_1\mid N-p_1 p_2 \dots p_k =1\] となり\(p_1\)が\(1\)を割り切ることがわかります｡ もちろん\(p\)は素数なのでこのようなことは起こるはずがない矛盾です｡ そしてこれは最初に素数が有限個しかないと仮定したことにより生じた矛盾なのでこの仮定が間違っていたと結論付けることができます｡ ゆえに素数は無限個存在することがわかりました｡ 以上で証明を終わりにしたいと思います.

ではどのようにして無限個の素数を発見するか

素数が無限個あることは証明できましたが, ではどうやって新しい素数を発見していけばよいでしょうか? この定理の証明自体は素数を生み出す公式なるものは使っていません｡

証明中に出てきた数\(p_1p_2\dots p_k +1\)を用いるとその素因数分解には\(p_1, p_2, \dots, p_k\)以外の素数が現れることが証明のポイントでした｡ 実際にこのことを使って素数を発見してみましょう｡ 最初の素数\(p_1=2\)から始めると\(p_1+1=3\)は新しい素数｡ そこで\(p_2=3\)と置おくと\(p_1p_2+1=7\)なりこれも新しい素数｡ このように繰り返していくと \[\begin{align*}
2+1 &= 3\\
2\cdot 3 + 1 &=7\\
2\cdot 3 \cdot 7 +1 &= 43\\
2\cdot 3 \cdot 7 \cdot 43 +1 &= 1807 = 13 \cdot 139
\end{align*}\] となり, 新しい素数43, 13, 139などが得られていきます｡

力技の素数判定

与えられた自然数が素数か合成数かはどうやって判定したらよいのでしょうか? そしてもし与えられた自然数がもし合成数だとわかっていたらどのように素因数分解したらよいのでしょうか? 素因数分解に現れる素数のことを素因数といいます｡ (なので素因数分解) 例えば合成数\(n\)が与えられたときに素因数を見つけるためには\(2\)で\(n\)を割ってみる, \(3\)で割ってみる, \(5\)で割ってみる, のようにと\(n\)より小さい素数で順次割ってみて素因数を発見するいわば力ずくの方法があります｡ もしも\(n\)より小さい素数で割り切れたら\(n\)は合成数, そうでなければ\(n\)は素数だと結論できます｡

さて少し実際の数を使ってこの素数判定方法を考察してみましょう｡ 試しに\(n=1000003\)が素数かどうか判断しましょう｡ \(1000003\)より小さい素数は全部で\(\pi(1000002)=78498\)個あります｡ つまり上の素数判定を用いるとこれら\(78498\)の素数で\(1000003\)を割っていき, もし割り切れたら合成数ですし, そうでなければ素数だとわかります｡ しかし, \(78498\)回も割り算を繰り返すのは少し(いやかなり?)大変です｡ そこで数学的な考察をし, 上の判定方法を改善してみましょう｡

\(4x+3\)型の素数

すべての素数を同時に研究するのではなく, 特殊な形の素数に関して成り立つ性質を研究する場面もあります｡ \(2\)以外の素数は奇数ですね｡ 言い換えると, \(2\)以外の素数は\(2\)で割ると\(1\)余る数です｡ これでは当たり前すぎるので\(2\)の代わりに\(4\)を使ってみましょう｡ そして\(4\)で割って\(1\)余るような素数を考えてみましょう｡ 小さい順に書くと, \(5, 13, 17, 29\)などが\(4\)で割ると\(1\)余るような素数です｡ 一方\(3, 7, 11, 19, 23\)などは\(4\)で割ると\(3\)余る素数です｡ 奇素数(2以外の素数)は\(4\)で割った余りは\(1\)か\(3\)です｡ (余りが\(0\)か\(2\)だと偶数になってしまいます｡) つまり, すべての奇素数は余りが\(1\)か\(3\)かの2つのグループに分けられます｡

素数は無限個あるので少なくともどちらかのグループには無限個の素数が含まれています｡ 実は両方のグループに無限個の素数が含まれていることが証明されています｡ ここでは余りが\(3\)のグループに素数が無限個含まれていることを示しましょう｡ つまり, $4$で割ると余りが\(3\)となる素数が無限個あることを証明します｡ 余りが\(3\)ということはある整数\(x\)があって\(4x+3\)と書けるということです｡ これらの素数を\(4x+3\)型の素数と呼びます｡