じつに6年ぶりの大発見！…なんと「桁数が4102万4320」の素数を叩き出した「1」の魔法
「素数シリーズ三部作」（『素数が奏でる物語』『素数はめぐる』『有限の中の無限』）でブルーバックスを代表する人気著者コンビ・西来路文朗さんと清水健一さん。最新刊『ガウスの黄金定理』も大好評のお二人が、新しい「数の世界」を案内してくださいます！
今回は、今日11月11日にちなんで、「1が並ぶ数」にまつわるお話です。
先月、じつに6年ぶりに最大の素数が見つかるという数学界を盛り上げるビッグニュースが飛び込んできました。これまで最大だった素数を1600万桁以上も上回る、なんと4102万4320桁の数字だというのですから驚きです。
そしてさらに、こんな巨大な数が素数かどうかを判定する方法と、「1が並ぶ数」に深い関係があるというのですが、いったいどういうことなのでしょうか!?
52番目のメルセンヌ素数
「1だけが並ぶ数」の深すぎる世界を探訪した記事〈これが「ポッキー」ではなくて「1」に見えてしまったら、相当の数論好きかも…「1だけが並ぶ数」の深すぎる世界〉では、すべての桁が1である数「レピュニット数」の話から始めて、2進法のレピュニット数である「メルセンヌ数」についてご紹介しました。
「メルセンヌ数」が素数になる時って、どんな時…？ メルセンヌ数の不思議な世界が、もっとよくわかる前半は、こちらから
それを受けて、「1だけが並ぶ数」の世界さらなる奥を探るこの記事では、メルセンヌ数2ⁿ−1の、nが素数pである場合を考えます。
メルセンヌ数2ᵖ−1は、pが
2, 3, 5, 7, 13, 17, 19, 31, 61, 89, …
の場合に素数になります。素数pに対して、2ᵖ−1が素数のときメルセンヌ素数とよばれています。
現在52個のメルセンヌ素数が見つかっていますが、52番目のメルセンヌ素数は先月発見されたばかりで、4102万4320桁にもおよぶ巨大な数字です。
素数かどうかをどう判定する？
2ᵖ−1がメルセンヌ素数であるかどうかは、すぐにはわかりません。
2ᵖ−1がメルセンヌ素数であることを判定する方法に、リュカ・レーマーテストがあります。このテストは、フランスの数学者・リュカが1878年にメルセンヌ数の素数判定法を見出した後に、アメリカの数学者・レーマーが改良したものです。
で定義されるSₙに対し、
Sₚ₋₁が2ᵖ−1で割り切れる⇔2ᵖ−1は素数
が成り立ちます。先月の52番目のメルセンヌ数の発見にも、リュカ・レーマーテストが使われました。
たとえば、p＝3のとき、2ᵖ−1＝2³−1＝7、p−1＝2であり、
S₂＝4²−2＝14
となります。S₂が7で割り切れるので、7はメルセンヌ素数です。
p＝5のとき、2ᵖ−1＝2⁵−1＝31、p−1＝4であり、
S₂＝4²−2＝14
S₃＝14²−2＝194
S₄＝194²−2＝37634
となります。
37634＝31×1214
より、S₄が31で割り切れるので、31はメルセンヌ素数です。
巨大な数の場合は？
リュカ・レーマーテストは、数列Sₙを2ᵖ−1で割った余りを調べます。pが大きくなると，2ᵖ−1がとても大きな数になります。2ᵖ−1をどのように表すか，そして，どのように割り算をおこなうか，という問題が生じます。
この問題を解決する1つの方法が2進法です。
2進法で問題解決
メルセンヌ数2ᵖ−1は2進法で書くと
111… 11 （p桁）
という特別な形の数になります。10進法で2ᵖ−1で割ることは、2進法ではp桁の111… 11で割ることです。そして，2進法で100… 00をp桁の111… 11で割った余りは、下位の0をp個とることを繰り返すと得られます。
たとえば、p＝3のとき、2³−1＝7を2進法で表すと
111
となります。2進法で
1000＝111＋1
だから、1000を111で割った余りが1になります。この余りの1は、1000の下位の0を3つとることで得られます。
このような計算で、2進法では
1, 10, 100, 1000, 10000, 100000, 1000000, …
を111で割った余りは
1, 10, 100, 1, 10, 100, 1, …
となります。
下位の0を3つとることを繰り返すことで得られます。
下位に0が並ばない数では？
また，2進法で1011のように下位に0が並ばない数を111で割る場合，
1011＝1000＋11
と変形します。右辺を111で割った余りは
1＋11
です。2進法で
1＋11＝100
なので、1011を111で割った余りは100になることがわかります。
ところで、これと同様の原理を用いて手計算で発見された最大の素数が何桁におよぶか、想像がつきますか？
手計算で発見された最大の素数
リュカは1876年に、このような原理を使って
2¹²⁷−1＝170141183460469231731687303715884105727
が素数であることを示しています。
リュカは上で紹介した数列ではなく，Sₙ=S²ₙ₋₁−2の式が同じで，初項がS₁＝3の数列Sₙを使って，2進法のS₁₂₆が
111111111111111111111111111111111
111111111111111111111111111111111
111111111111111111111111111111111
1111111111111111111111111111（127桁）
で割り切れることを示しました。
じつに、127桁におよぶ数字です。これができたときの感動には、計り知れないものがあります。
リュカの結果は、手計算で発見された最大のメルセンヌ素数です。
巨大な素数は暗号に使われている
メルセンヌ数2ⁿ−1は2進法で表すとn桁の111… 11でした。
このため、コンピュータで巨大な素数を得るのに、メルセンヌ素数が活躍しています。
実際、近年発見されている巨大な素数のほとんどがメルセンヌ素数です。そして、巨大な素数はRSA暗号などに使われ、私たちの情報のセキュリティのためになくてはならない存在となっています。
一見シンプルな「1が並ぶ数」ですが、その背後には奥深い数の世界が広がっています。
この記事の執筆者・西来路さんと清水さんによる最新刊はこちら！
ガウスの黄金定理 平方剰余の相互法則で語る数論の世界
オイラーが発見し、ルジャンドルが証明に挑み、ガウスが証明した「平方剰余の相互法則」は、何がどうすごいのか？ 予備知識ゼロから理解できる！
西来路さんと清水さんの好評既刊「素数シリーズ」
