メルセンヌ数

ウィキペディア

メルセンヌ数

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/09/09 16:37 UTC 版)

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

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

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

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

基本的な性質

M_n は 2^{n − 1} の約数の総和に等しい。

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

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

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

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

完全数

M_p = 2^p − 1が素数ならば、2^p−1(2^p − 1) は完全数である。

例

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

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

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

メルセンヌ数の素因数

p を素数とする。

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

倍積完全数

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

メルセンヌ素数

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

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

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

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

古代～中世

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

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

メルセンヌの予想

メルセンヌの予想の表: p ≦ 263

〇：Mpが素数の場合／×：Mpが合成数の場合 水色が正解、ピンク色が間違いを示す。
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年、マラン・メルセンヌは「素数 p で 2^p − 1 が素数になるのは、p ≦ 257 では p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257 の11個の場合だけである」という予想を発表した。しかしメルセンヌ自身はその予想を証明することができず、しかもその予想の一部は誤っていた。

最初の成果はメルセンヌが予想を発表してから128年後、1772年にオイラー（p = 31 では素数）によって証明された。その次の成果はさらに104年後、1876年にリュカ（効率的な素数判定法リュカ・テストを考案、p = 67 では素数でない、p = 127 では素数）が証明した。その後リュカ・テストは改良され、メルセンヌの予想にない素数3個が発見された（p = 61（1883年）、p = 89（1911年）、p = 107（1914年））。メルセンヌが予想した最後の数 p = 257 について決着がついたのは1922年のことであり、 p = 257 も合成数だった。

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

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

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

GIMPSによる発見

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

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

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

素数判定法

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

リュカ・テスト

p が (4j + 3) 型の素数のとき、S₀ = 3, S_n = S_n−1² − 2 (n ≧ 1) で {S_n} を定義すると、

• 任意の $S_{k}$ Portal:数・プロジェクト:数