『素数』を数えて落ちつくんだ……。“素数の無限性”の証明する「エラトステネスの篩」「ユークリッドの証明」「エルンスト・クンマーの証明」をやさしく解説してみた

ニコニコニュース / 2021年4月5日 19時0分

　今回紹介するのは、Gaudaro440さんが投稿した『【ゆっくり数学】素数の無限性と３つの証明』という動画です。音声読み上げソフトを使用して、素数が無限に存在することの証明についての解説を行いました。

エラトステネスの篩の素数判定法

霊夢：
　まず、エラトステネスの篩という素数判定法の紹介をする。この方法自体はかなり有名だから、知っている人も多いかもしれない。おまけにエラトステネスは紀元前200年に活躍したエジプト数学者、つまりかなり古い時代に考案されたやり方なんだ。

　たとえば2～20までの数字があったとする。この中から素数となるものを見つけ出す。やり方は単純、まず2以外の偶数をすべて消す。次に3以外の3の倍数を全部消す。はい、終わり。

　これで残ったやつが素数です。エラトステネスの篩の最強なところは、この圧倒的計算量の少なさである。このためアルゴリズムに使われたりする。さて、このエラトステネスの篩から、こんな疑問が生じる。先程は1から20までで考えていたが、これを無限個の自然数で操作するとき、そして操作が有限回で終わるかどうかというのは、素数が有限個か無限個か？という問いと同じになる。

　実は、素数は無限に存在する。篩は限られた自然数の中で素数を見つけ出すには最強だが、残念ながらこれで素数が無限個あることは証明できない。しかし、かわりにいろんな数学者が素数が無限にあることを証明してくれた。

ユークリッド（エウクレイデス）の証明

霊夢：
　古代エジプトの最強数学者、エウクレイデス。またの名をユークリッドである。「幾何学の父」とか言われたりして、非常に有名で多大な貢献をした数学者である。では彼の証明を見ていこう。

　まず、素数が有限個であると仮定する。それをp_1、p_2……p_Nとおいていく。こんどはその有限個の素数の全部の積に1を足したQという数字を考える。こいつはおのおののpで割れない。

　しかし2以上の自然数はなにかしらの素数を約数にもっているはずなので、ここで矛盾が発生する。これはつまり、「新たな素数が必要だ」ということを意味している。

　
エルンスト・クンマーの証明

霊夢：
　次に紹介するのは、エルンスト・クンマーの証明。クンマーは19世紀に活躍したドイツの数学者。それでは証明を見ていこう。

　クンマーの証明も、ユークリッドと同様、素数が有限個であるという仮定からはじまる。次にNを有限個の素数全部の積としてN-1という数を考える。N-1はN個ある素数のどれかで割り切れるはずである。

　ここで有限個ある素数のうち、p.jという素数がN-1を割り切るとする。p.jは当然Nも割り切るはずである。したがって、NとN-1の差である1も割り切るはずであるが、これは素数が2以上であることに矛盾する。したがって素数は無限に存在する。

ジョージ・ポリアの証明

霊夢：
　最後にポリアの証明である。ジョージ・ポリアはハンガリー生まれのアメリカの数学者で、20世紀半ばにはスタンドフォード大学で教授を務めていたときもあった。

　フェルマーは当初、「フェルマー数はすべて素数」と考えていた。しかし残念ながらn=5のときは合成数であることをオイラーが証明した。ちなみにnが5以上のときにフェルマー数が素数でないかどうかは未解決である。しかしこのフェルマー数を用いれば、素数が無限にあることを証明することができる。

　まず、フェルマー数を割り切る素数pをもってくる。ここで後で示す補題「素数pがフェルマー数の約数」ならば、「pはそれより前の項のフェルマー数の約数ではない」ということから、それぞれの項のフェルマー数を割り切る素数と異なることを意味する。フェルマー数は無限に作ることができるから、異なる素数も無限に作れる。

　したがって素数が無限に存在することを示すことができた。このように同じ命題に対して複数の証明が考えられることも、数学の醍醐味だったりする。ここで取り上げた証明以外にも、たとえばオイラーも素数の無限性の証明をしているので、興味がある方は調べてみてほしい。