メルセンヌ数とは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > デジタル大辞泉 > メルセンヌ数の意味・解説 

メルセンヌ‐すう【メルセンヌ数】

読み方:めるせんぬすう

2の冪(べき)乗から1を引いた形で表される自然数17世紀フランス神学者物理学者メルセンヌ考案n番目の数はMn=2n−1表されるこのうち素数であるメルセンヌ数はメルセンヌ素数とよばれ、巨大素数探索対象となっている。


メルセンヌ数

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2025/04/06 23:46 UTC 版)

メルセンヌ数(メルセンヌすう、: Mersenne number)とは、2の冪よりも 1 小さい自然数、すなわち 2n − 1n は自然数)の形の自然数のことである。これを Mn で表すことが多い。メルセンヌ数を小さい順に列挙すると

1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, ... (オンライン整数列大辞典の数列 A000225)

となる。メルセンヌ数は2進法表記で n 桁の 11⋯11、すなわちレピュニットとなる。

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

基本的な性質

Mn2n − 1約数の総和に等しい。

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

2ab − 1 = (2a − 1)(1 + 2a + 22a + ⋯ + 2(b−1)a).

また、この等式より、m | n のとき Mm | Mn である。一方、 p が素数でも Mp が素数とは限らない。最小の反例は p = 11 の場合であり、M11 = 2047 = 23 × 89 が成り立つ。

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

完全数

Mp = 2p − 1が素数ならば、2p−1(2p − 1)完全数である[1][3]

  • 6 = 2 × 3 = 2 × ( 1 + 2 )
  • 28 = 2 × 7 = 2 × ( 1 + 2 + 22)

この定理はすでに紀元前3世紀頃のユークリッド原論で証明されていた[4]。したがって、完全数の探索はメルセンヌ素数の探索に終始された。

p > 1ならば、2p−1(2p − 1) は明らかに偶数であるが、偶数の完全数でこの生成式から得られるもの以外はないのか2000年間にわたって未解決であったが、18世紀オイラーによりこの形に限ることが証明された[3]

メルセンヌ数の素因数

p を素数とする。

  • Mp の素因数は 2p を法として 1 と合同[5]、かつ 8 を法として 1 または −1 と合同である[6]
  • p ≡ 3 (mod 4) のとき、Mp2p + 1 で割れることと、2p + 1 が素数であることは同値である[6]
  • ある計算可能な正定数 c が存在して、Mp の最大素因数を q について、qcp log p [7]

倍積完全数

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

メルセンヌ素数

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

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

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

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

古代~中世

メルセンヌ素数の探求は紀元前3世紀ごろに端を発する。古代エジプトの数学者エウクレイデスは『原論』の中で、「2n − 1 が素数ならば、2n − 1(2n − 1)完全数である」ことを証明した[8]。ここから、メルセンヌ素数の探索は完全数の探索にも繋がることとなる[9][注釈 1]

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

メルセンヌの予想

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

1644年マラン・メルセンヌは「素数 p2p − 1 が素数になるのは、p ≦ 257 では p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257 の11個の場合だけである」という予想を公表した[12][16]。しかしメルセンヌ自身はその予想を証明することができず、しかもその予想の一部は誤っていた。

成果をもたらしたのはメルセンヌが予想を公表してから128年後、1772年オイラーp = 31 では素数)[1][17]である。その次の成果はさらに104年後、1876年リュカ(効率的な素数判定法リュカ・テスト英語版を考案、p = 67 では素数でない、p = 127 では素数[1][18])によってもたらされた。その後リュカ・テストは改良が加えられ、メルセンヌが予想した範囲にない3個が付け加えられた(p = 611883年)、p = 891911年)、p = 1071914年))。メルセンヌが予想した最後の数 p = 257 について決着がついたのは1922年のことであり、 p = 257 も合成数だった[1][19]

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

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

1952年、ラファエル・M・ロビンソンが SWAC を利用して M521 から M2281 まで、5つのメルセンヌ素数を発見[1]して以降、発見にはコンピュータが使用されており、コンピュータの進歩と共に新たなメルセンヌ素数が発見されつつある。

GIMPSによる発見

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

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

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

素数判定法

知られている素数の中で最大のものが1876年以降ほぼ一貫してメルセンヌ素数である理由は、この判定法にある[要出典]

リュカ・テスト

p(4j + 3) 型の素数のとき、S0 = 3, Sn = Sn−12 − 2 (n ≥ 1){Sn} を定義すると、

  • Portal:数・プロジェクト:数


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「メルセンヌ数」の関連用語

メルセンヌ数のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



メルセンヌ数のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
デジタル大辞泉デジタル大辞泉
(C)Shogakukan Inc.
株式会社 小学館
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのメルセンヌ数 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS