メルセンヌ数

メルセンヌ数（メルセンヌすう、）とは、2の冪よりも 小さい自然数、すなわち （ は自然数）の形の自然数のことである。これを で表すことが多い。メルセンヌ数を小さい順に列挙すると

となる（OEISでは の場合もメルセンヌ数に含めている）。メルセンヌ数は2進法表記で 桁の 、すなわちレピュニットとなる。

「メルセンヌ数」の名は、この形の素数に関する予想を発表したマラン・メルセンヌに由来する。

基本的な性質 は の約数の総和に等しい。

が素数ならば もまた素数である。このことは、nが合成数であるメルセンヌ数は次のように因数分解できることから分かる：

また、この等式より、 のとき である。一方、 が素数でも が素数とは限らない。最小の反例は の場合であり、 が成り立つ。

奇素数 に対して が素数であるかどうかは、リュカ–レーマー・テストによって判定できる (#素数判定法節を参照)。

完全数 が素数ならば、 は完全数である。

例

この定理はすでに紀元前3世紀頃のユークリッド原論で証明されていた。そのため、完全数の探索は専らメルセンヌ素数の探索によって行われた。

ならば、 は明らかに偶数であるが、偶数の完全数がこの生成式で表されるものに限られるのかはユークリッド以来約2000年間にわたって未解決であったが、18世紀にオイラーによりこの形に限ることが証明された （奇数の完全数が存在するかという問題は今日なお未解決である。）

メルセンヌ数の素因数 を素数とする。 の素因数は を法として と合同、かつ を法として または と合同である。 のとき、 が で割れることと、 が素数であることは同値である。 ある計算可能な正定数 が存在して、 の最大素因数を について、 Theorem 1, 。

倍積完全数 メルセンヌ数が素数でない場合も、 が倍積完全数になることがある。 が1の場合は1（唯一の1倍完全数）、4と10の場合はそれぞれ120と523776（いずれも3倍完全数）、6の場合は2016（3倍完全数672の約数の和）になることが知られている。

メルセンヌ素数 メルセンヌ素数（メルセンヌそすう、Mersenne prime）とは、素数であるメルセンヌ数のことである。

2024年10月現在発見されているメルセンヌ素数は全部で52個ある。その中で最大のものは2024年10月に発見された であり、十進法で表記したときの桁数は4102万4320桁に及ぶ。

これより大きい素数は、2024年11月現在メルセンヌ素数以外でも発見されていない。

メルセンヌ素数の発見の歴史

古代～中世 メルセンヌ素数の探索は紀元前3世紀ごろに端を発する。

小さいメルセンヌ素数がいつから知られているかは定かではないが、少なくとも最初の4つの完全数はゲラサのニコマコスの『算術入門』ですでに言及されている。5番目から7番目の完全数は、13世紀イスラムの数学者イブン・ファッルースが論文に記している。ヨーロッパでは、5番目の完全数が1456年と1461年の日付が付された古い写本に記されており、6番目と7番目のメルセンヌ素数および完全数も1603年にによって発見されている。

メルセンヌの予想 + メルセンヌの予想の表: p ≦ 263〇：Mが素数の場合／×：Mが合成数の場合水色が正解、ピンク色が間違いを示す。 p 2 3 5 7 11 13 17 19 M 〇 〇 〇 〇 × 〇 〇 〇 p 23 29 31 37 41 43 47 53 M × × 〇 × × × × × p 59 61 67 71 73 79 83 89 M × 〇 × × × × × 〇 p 97 101 103 107 109 113 127 131 M × × × 〇 × × 〇 × p 137 139 149 151 157 163 167 173 M × × × × × × × × p 179 181 191 193 197 199 211 223 M × × × × × × × × p 227 229 233 239 241 251 257 263 M × × × × × × × ×

1644年、マラン・メルセンヌは「素数 で が素数になるのは、 では の11個の場合だけである」という予想を発表した。しかしメルセンヌ自身はその予想を証明することができず、しかもその予想の一部は誤っていた。

最初の成果はメルセンヌが予想を発表してから128年後、1772年にオイラーにより の場合は素数であることが証明された。その次の成果はさらに104年後、1876年にリュカが効率的な素数判定法を考案して、 の場合は素数でないこと、 の場合は素数であることを証明した。その後リュカ・テストは改良されて、メルセンヌの予想に含まれていなかった素数3個が新たに発見された（の場合（1883年）、の場合（1911年）、の場合（1914年））。メルセンヌが予想した最後の数である の場合が合成数であることが確定したのは1922年であった.。

結局メルセンヌの4個の予想のうち2つは外れた。なおかつ、間に予想できなかった3つが含まれていたことを考えれば彼の予想は正しかったとはいえないが、その後の歴史を見ても大きな原動力となり先駆的であったことに敬意を表して、素数であるメルセンヌ数をメルセンヌ素数という。

1903年10月、アメリカの数学者フランク・ネルソン・コールは実際の素因数分解を探求し、ニューヨークで開かれたアメリカ数学会の会議で を黒板に計算し、 と一致することを証明した。この間一言もしゃべらず、席に戻った後、少し間を置いて拍手が沸き起こったと伝えられている。

1952年、が SWAC を利用して から まで、5つのメルセンヌ素数を発見して以降、発見にはコンピュータが使用されており、コンピュータの進歩と共に新たなメルセンヌ素数が発見されつつある。

GIMPSによる発見 1996年、メルセンヌ素数を発見することを目的として作られた分散コンピューティングによるプロジェクト GIMPS が発足し、35番目のメルセンヌ素数 （1996年11月13日、Joel Armengaud）以来、GIMPSによるメルセンヌ素数の発見が続いている。

2008年8月23日、GIMPS は46番目の素数候補が、カリフォルニア大学ロサンゼルス校の数学部のコンピュータによって発見されたと報じた。この素数は電子フロンティア財団が賞金を懸けた1000万桁以上の最初の素数となるため、GIMPS によって同校数学部に50,000ドル、慈善事業に25,000ドル、残りを前の6つのメルセンヌ素数の発見者へ分配することになった。

2008年9月6日、GIMPS は45番目の素数候補が、ドイツで発見されたと報じた。これは、GIMPS によって発見された中では、発見順序と桁数が逆転した初めてのケースである。

素数判定法 メルセンヌ数には次のような素数判定法があり、素数かどうか効率よく判定することが可能である。

リュカ・テスト が 型の素数のとき、, で を定義すると、 任意の がで割り切れないならば、 は合成数である がで割り切れるならば、 は素数である

リュカ–レーマー・テスト が奇素数のとき、, で を定義すると、 がで割り切れないならば、 は合成数である がで割り切れるならば、 は素数である

リュカ–レーマー・テストは二進計算機用のアルゴリズムに適しており、コンピュータによるメルセンヌ素数の発見には、この判定法が用いられてきた。例えば、 より、 が成り立つので、 で割る割り算の代わりに、二進法で 桁のシフト演算と足し算だけで計算できる。

メルセンヌ素数の一覧 2024年10月現在知られているメルセンヌ素数は下記の表の52個である。ただし、メルセンヌ素数としての番号が確定しているものは51番目までであり、それよりも大きいメルセンヌ素数については、未発見のメルセンヌ素数が途中にないかを検証中である。

メルセンヌ素数は小さい順番から並べると

となる。 # の桁数発見日発見者121紀元前500年?231紀元前500年?352紀元前275年?473紀元前275年?51341456年不明61761603年71961603年ピエトロ・カタルディ831101772年レオンハルト・オイラー961191883年1089271911年11107331914年R・E・パワーズThe Prime Pages, M: Fauquembergue or Powers?.12127391876年エドゥアール・リュカ135211571952年1月30日, 使用：SWAC146071831952年1月30日ラファエル・M・ロビンソン151,2793861952年6月25日ラファエル・M・ロビンソン162,2036641952年10月7日ラファエル・M・ロビンソン172,2816871952年10月9日ラファエル・M・ロビンソン183,2179691957年9月8日ハンス・リーゼル, 使用：BESK194,2531,2811961年11月3日アレクサンダー・フルウィッツ, 使用：IBM 7090204,4231,3321961年11月3日アレクサンダー・フルウィッツ219,6892,9171963年5月11日ドナルド・ギリース, 使用：ILLIAC II229,9412,9931963年5月16日ドナルド・ギリース2311,2133,3761963年6月2日ドナルド・ギリース2419,9376,0021971年3月4日, 使用：IBM 360/912521,7016,5331978年10月30日 & ローラ・ニッケル, 使用：CDC Cyber 1742623,2096,9871979年2月9日ランドン・カート・ノル2744,49713,3951979年4月8日ハリー・ネルソン & 2886,24325,9621982年9月25日デイヴィッド・スローウィンスキー29110,50333,2651988年1月28日ウォルター・コルキット & ルーク・ウェルシュ30132,04939,7511983年9月19日Landon Curt Noll, Mersenne Prime Digits and Names.デイヴィッド・スローウィンスキー31216,09165,0501985年9月1日デイヴィッド・スローウィンスキー32756,839227,8321992年2月19日デイヴィッド・スローウィンスキー & 使用：Harwell Lab Cray-2The Prime Pages, The finding of the 32nd Mersenne.33859,433258,7161994年1月4日Chris Caldwell, The Largest Known Primes.デイヴィッド・スローウィンスキー & ポール・ゲイジ341,257,787378,6321996年9月3日デイヴィッド・スローウィンスキー & ポール・ゲイジThe Prime Pages, A Prime of Record Size! 2 − 1.351,398,269420,9211996年11月13日GIMPS / Joel Armengaud362,976,221895,9321997年8月24日GIMPS / Gordon Spence373,021,377909,5261998年1月27日GIMPS / Roland Clarkson386,972,5932,098,9601999年6月1日GIMPS / Nayan Hajratwala3913,466,9174,053,9462001年11月14日GIMPS / Michael Cameron4020,996,0116,320,4302003年11月17日GIMPS / Michael Shafer4124,036,5837,235,7332004年5月15日GIMPS / Josh Findley4225,964,9517,816,2302005年2月18日GIMPS / Martin Nowak et al.4330,402,4579,152,0522005年12月15日GIMPS / , Steven Boone4432,582,6579,808,3582006年9月4日GIMPS / カーティス・クーパー, Steven Boone4537,156,66711,185,2722008年9月6日GIMPS / Hans-Michael Elvenich4642,643,80112,837,0642009年4月12日GIMPS / Odd Magnar Strindmo4743,112,60912,978,1892008年8月23日GIMPS / エドソン・スミス4857,885,16117,425,1702013年1月25日GIMPS / カーティス・クーパー4974,207,28122,338,6182016年1月7日GIMPS / カーティス・クーパー5077,232,91723,249,4252017年12月26日GIMPS / Jonathan Pace5182,589,93324,862,0482018年12月7日GIMPS / Patrick Laroche136,279,84141,024,3202024年10月21日GIMPS / Luke Durant

未解決問題 メルセンヌ素数は無数に存在するか？ 素数 に対して が合成数であるとき、これをメルセンヌ合成数と呼ぶ。メルセンヌ合成数は無数に存在するか？ 平方因子を持つメルセンヌ数 （ は素数）が存在するか？ を奇数とするとき、次の3つの条件のうち2つが満たされれば、残りの1つも満足されると予想されており、 に対してこの予想は正しいと確認されているP. T. Bateman, J. L. Selfridge, S. S. Wagstaff Jr., "The new Mersenne conjecture", American Mathematical Monthly, 96 (1989), 125–128.。 が素数 または が素数

脚注

注釈

出典

GIMPS

参考文献

- 全13巻の最初の邦訳。 （ハードカバー）1971年7月。ISBN 4-320-01072-8 （縮刷版）1996年6月。ISBN 4-320-01513-4 （追補版）2011年5月。ISBN 978-4-320-01965-2 - 前編は1次式の整数論、後編は2次式の整数論。

（前半の英訳）

関連項目 二重メルセンヌ数 完全数 巨大な素数の一覧 ハノイの塔 - メルセンヌ素数 を発見したリュカによって考案されたパズル。解に必要な最短手数とその二進数表記は密接な関係がある。 フェルマー数 マラン・メルセンヌ メルセンヌ・ツイスタ - メルセンヌ素数を用いた擬似乱数発生アルゴリズム。 メルセンヌ予想 レピュニット GIMPS メルセンヌ素数と完全数の一覧

外部リンク

Mersenne Primes: History, Theorems and Lists The Largest Known Primes GIMPS