数学者が選んだ証明
1940 年、イギリスの数学者 G・H・ハーディは『ある数学者の弁明』という小さな本を出した。数学の美しさとは何かを語るために、彼は古代ギリシアから 2 つの定理を選んだ。1 つは が分数で表せないこと。もう 1 つが、素数が無限にあることのエウクレイデスによる証明である。
ハーディはこう書いている。この証明は背理法による。背理法は、エウクレイデスが大いに好んだもので、数学者の最も優れた武器の 1 つである。それはチェスのどんな捨て駒よりもはるかに見事な手だ。チェスの指し手が差し出すのはポーンか、せいぜい駒 1 つだが、数学者が差し出すのはゲームそのものなのだ。
ところが、エウクレイデスが実際に書いた証明は、背理法の形をとっていない。2009 年、マイケル・ハーディとキャサリン・ウッドゴールドは論文「素朴な単純さ」で原文を読み直し、エウクレイデスは「素数がいくつか与えられたら、そのほかにもう 1 つ作れる」と、新しい素数を作る手順として示していることを指摘した。もう 1 つよくある誤解は、「素数を全部掛けて 1 を足した数は素数になる」というものである。 は で、素数ではない。証明に必要なのは、その数が「並べた素数のどれでも割り切れない」ことだけである。
ハンガリーの数学者ポール・エルデシュは、神はあらゆる定理の最も美しい証明を集めた「本」を持っている、とよく語った。神を信じなくてもいいが、本は信じるべきだ、とも語ったと伝えられる。1998 年、マルティン・アイグナーとギュンター・ツィーグラーは、その「本」に載りそうな証明を集めた『天書の証明』を出版した。第 1 章は、素数が無限にあることの 6 通りの証明である。
起源
最も古い記録は、紀元前 300 年ごろのエウクレイデスの『原論』第 9 巻 命題 20 である。命題はこう述べる。「素数は、あらかじめ与えられたどんな個数の素数よりも多い」。
エウクレイデスは数を線分で表し、3 つの素数 A, B, C を例にとって証明した。A, B, C のすべてで割り切れる最小の数 DE をとり、それに単位 DF を足して EF とする。EF が素数なら、A, B, C とは別の素数が見つかったことになる。素数でなければ、ある素数 G で割り切れる。G が A, B, C のどれかなら、G は DE も EF も割り切るので、差の単位 DF も割り切ることになり、これはおかしい。よって G は新しい素数である。
命題が「無限にある」と言わずに「どんな個数よりも多い」と言っていることにも意味がある。アリストテレス以来、ギリシアの学問は、完結した無限の集まりを扱うことを避け、「いくらでも先へ進める」という形で無限を語った。
その後、素数は「無限にある」だけでなく、どれくらい多いかが問われるようになった。1737 年、オイラーは、すべての自然数についての和と、すべての素数についての積が等しいという式を見つけ、素数の逆数の和 が限りなく大きくなることを示した。1837 年、ディリクレは、たとえば 4 で割って 1 余る数の中にも素数が無限にあるように、初項と公差が互いに素な等差数列の中にも素数が無限にあることを証明した。1896 年にはアダマールとド・ラ・ヴァレ・プーサンが、 以下の素数がおよそ 個あるという素数定理を証明した。1955 年には、ヒレル・ファーステンバーグが、位相空間の言葉を使って半ページほどの新しい証明を発表している。
証明
エウクレイデスの考えを、いまの言葉で書く。
-
素数をいくつか、たとえば 個とって とする。それらを全部掛けて 1 を足した数を とおく。
-
なので、 は少なくとも 1 つの素数で割り切れる( を割り切る 1 より大きい最小の数は素数である)。その素数を とする。
-
もし が のどれかと等しければ、 は積を割り切る。
-
割り切る 2 つの数の差も割り切るので となるが、1 を割り切る素数は無い。
-
よって は最初の表に無い、新しい素数である。
-
どんな有限の表から始めても、表に無い素数が 1 つ見つかる。したがって素数は無限にある。
を で割った余りは、どれも 1 になる。これが証明の芯である。 自身が素数とは限らないが、素数でなくても、その素因数はどれも新しい。
オイラーの方法では、素数が有限個しかないと仮定すると、次の式の左辺は有限の値にとどまる。 ところが右辺は を大きくするといくらでも大きくなるので、矛盾が起きる。左辺の積を展開すると、素因数がすべて 以下の自然数の逆数がちょうど 1 回ずつ現れることが、この不等式の理由である。
応用
暗号の素数は尽きない。 インターネットの通信を守る RSA 暗号では、1024 ビット(約 309 桁)ほどの素数を 2 つ選んで掛け合わせ、鍵を作る。素数定理によれば、1024 ビットの素数はおよそ 個ある。世界中の機械が鍵を作り続けても、同じ素数を偶然選ぶ心配はまず無い。素数が無限にあることは、この供給が尽きないことの保証でもある。
知られている最大の素数。 2024 年 10 月、分散計算の仕組み GIMPS に参加したルーク・デュラントは、 が素数であることを確かめた。十進法で 4102 万 4320 桁ある。いくら大きな素数が見つかっても、エウクレイデスの手順を使えば、それより大きな素数があることは確かである。
13 年と 17 年のセミ。 北アメリカの周期ゼミは、13 年または 17 年ごとに一斉に地上に出る。周期が素数なのは、ほかの周期を持つ天敵や、別の周期のセミの集団と重なりにくいからだ、という仮説がある。周期 12 年のセミは周期 4 年の天敵と 12 年ごとに出会うが、17 年のセミなら 68 年に 1 度である。仮説は 1997 年の吉村仁の研究などで論じられているが、決着はついていない。
図示
シミュレーション
つまみで表に入れる素数の数 を変えると、それらの積に 1 を足した が作られ、素数ごとの時計の針が回って、どれも余り 1 の位置で止まる。右には の素因数が、表に無い新しい素数として現れる。「見つけた素数を足していく」では、いちばん小さい新しい素数を表に足していき、2, 3, 7, 43, 13, 53, 5, … と、順番の読めない列ができていく。
広がる学問
- 数学 素数が無限にあることは、どれくらい多いかを問う素数定理や、等差数列の中の素数の研究へ続いた。差が 2 の素数の組(双子素数)が無限にあるかどうかは、いまも分かっていない。
- 情報科学 RSA 暗号の鍵の生成は、大きな素数を乱数で選び、素数かどうかを高速に判定することで成り立っている。巨大な素数の探索は、計算機の誤りを見つける試験にも使われる。
- 生物学 周期ゼミの周期が素数であることを、天敵や交雑を避けた結果として説明する仮説が、数理モデルを使って調べられている。
- 哲学 エウクレイデスは「無限」と言わず「どんな個数よりも多い」と書いた。完結した無限を認めるか、どこまでも続く手順としてだけ認めるかは、数学の哲学の大きな問いであり続けている。
参考文献
- エウクレイデス『原論』第 9 巻 命題 20(中村幸四郎・寺阪英孝・伊東俊太郎・池田美恵 訳『ユークリッド原論』共立出版、1971)
- G. H. Hardy, A Mathematician's Apology (Cambridge University Press, 1940), §12.
- Michael Hardy, Catherine Woodgold, "Prime Simplicity", The Mathematical Intelligencer 31 (2009), 44-52.
- Martin Aigner, Günter M. Ziegler, Proofs from THE BOOK (Springer, 1998), Chapter 1.
- Leonhard Euler, "Variae observationes circa series infinitas"(E72), Commentarii Academiae Scientiarum Petropolitanae 9 (1744), 160-188.
- Jin Yoshimura, "The Evolutionary Origins of Periodical Cicadas during Ice Ages", The American Naturalist 149 (1997), 112-124.
- GIMPS, "Mersenne Prime Discovery: 2^136279841-1 is Prime!"(2024 年 10 月 21 日)