メルセンヌ数

M_n が素数ならば n もまた素数であることは、次の式から分かる^[2][3]：

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

対偶命題「n が合成数ならば M_n は合成数である」が示される。また、この等式より、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) は完全数である^[2][4]。この定理はすでに紀元前3世紀頃のユークリッド原論で証明されていた^[5]。したがって、完全数の探索はメルセンヌ素数の探索に終始された。

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

メルセンヌ数の素因数

p を素数とする。

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

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

2022年2月現在知られている最大のメルセンヌ素数は、2018年12月に発見された、それまでに分かっている中で51番目のメルセンヌ素数 2^82589933 − 1 であり、十進法で表記したときの桁数は2486万2048桁に及ぶ^{[GIMPS 1]}。

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

古代～中世

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

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

メルセンヌの予想

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

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

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

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

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

GIMPSによる発見

1996年、メルセンヌ素数を発見することを目的として作られた分散コンピューティングによるプロジェクト GIMPS が発足し、35番目のメルセンヌ素数 M_1,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) 型の素数のとき、S₀ = 3, S_n = S_n−1² − 2 (n ≥ 1) で {S_n} を定義すると、

• ${\displaystyle M_{p}\not \mid S_{k}\ (0\leqq k\leqq p-2)}$ ならば、M_p は合成数である
• ${\displaystyle M_{p}\mid S_{p-2}}$ ならば、M_p は素数である^[22][23][24]

アルゴリズム

アルゴリズムは以下の擬似コードで表される。

入力: p: (4j + 3) 型の素数であるテスト対象の整数出力: PRIME:素数の場合, COMPOSIT:合成数の場合Lucas_Test(p):    var s = 3    var MP = (1 << p) − 1    for n in range(2, p):        s = (s2 − 2) % MP    if s == 0 then:        return PRIME    else:        return COMPOSIT

リュカ–レーマー・テスト

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

• ${\displaystyle M_{p}\not \mid S_{k}\ (0\leqq k\leqq p-2)}$ ならば、M_p は合成数である
• ${\displaystyle M_{p}\mid S_{p-2}}$ ならば、M_p は素数である^[25][26][27]

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

アルゴリズム

アルゴリズムは以下の擬似コードで表される。

入力: p:奇素数であるテスト対象の整数出力: PRIME:素数の場合, COMPOSIT:合成数の場合Lucas_Lehmer_Test(p):    var s = 4    var MP = (1 << p) − 1    for n in range(2, p):        s = (s2 − 2) % MP    if s == 0 then:        return PRIME    else:        return COMPOSIT

入力: p:奇素数であるテスト対象の整数出力: PRIME:素数の場合, COMPOSIT:合成数の場合Lucas_Lehmer_Test_FAST(p):    var s = 4    var m = 2p − 1    for n in range(2, p):        var s2 = s × s        s = (s2 & m) + (s2 >> p)        if s >= m then            s = s − m        s = s − 2    if s == 0 then        return PRIME    else        return COMPOSIT

メルセンヌ素数の一覧

2021年10月現在、メルセンヌ素数は51個まで知られている。ただし、メルセンヌ素数としての番号が確定しているものは48番目までであり、

p = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 24036583, 25964951, 30402457, 32582657, 37156667, 42643801, 43112609, 57885161（オンライン整数列大辞典の数列 A000043）

における M_p がそうである。さらに49, 50, 51番目の候補として p = 74207281, 77232917, 82589933 が挙がっており、間に素数がないかどうか検証中である。

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

となる。

• メルセンヌ素数は無数に存在するか？
• 素数 p に対して M_p が合成数であるとき、これをメルセンヌ合成数と呼ぶことにして、それは無数に存在するか？
• 平方因子を持つメルセンヌ数 M_p（p は素数）が存在するか？
• n を奇数とするとき、次の3つの条件のうち2つが満たされれば、残りの1つも満足されると予想されており、n < 10⁵ に対してこの予想は正しいと確認されている^[34]。

1. M_n が素数
2. n = 2^k ± 1 または 4^k ± 3
3. (2ⁿ + 1)/3 が素数

注釈

出典

GIMPS

• 淡中忠郎 著「メルセンヌ数物語」、数学セミナー編集部編 編『数の世界』日本評論社〈数学セミナー増刊 数学セミナー・リーディングス〉、1982年9月30日、65-67頁。 
• 中村滋『フィボナッチ数の小宇宙（ミクロコスモス）　フィボナッチ数、リュカ数、黄金分割』日本評論社、2002年9月30日。ISBN 4-535-78281-4。 
  • 中村滋『フィボナッチ数の小宇宙（ミクロコスモス）　フィボナッチ数、リュカ数、黄金分割』（改訂版）日本評論社、2008年1月25日。ISBN 978-4-535-78492-5。 
• 日本数学会 編 編『岩波　数学辞典』（第3版）岩波書店、1985年12月10日。ISBN 978-4-00-080016-7。 
  • 日本数学会 編 編『岩波　数学辞典』（第4版）岩波書店、2007年3月15日。ISBN 978-4-00-080309-0。 
• 一松信『数のエッセイ』筑摩書店〈ちくま学芸文庫〉、2007年1月10日。ISBN 978-4-480-09041-6。 
• ユークリッド 著、ハイベア・メンゲ編 編『ユークリッド原論』中村幸四郎・寺阪英孝・伊東俊太郎・池田美恵訳・解説、共立出版。  - 全13巻の最初の邦訳。
  • （ハードカバー）1971年7月。ISBN 4-320-01072-8
  • （縮刷版）1996年6月。ISBN 4-320-01513-4
  • （追補版）2011年5月。ISBN 978-4-320-01965-2
• 和田秀男『数の世界　整数論への道』岩波書店〈科学ライブラリー〉、1981年7月10日。ISBN 4-00-005500-3。  - 前編は1次式の整数論、後編は2次式の整数論。
• 和田秀男『コンピュータと素因子分解』（改訂版）遊星社（発行）星雲社（発売）、1999年4月（原著1987年10月20日）。ISBN 4-7952-6858-4 ISBN 4-7952-6889-4。 
• Lucas, Edouard (1878), “Théorie des Fonctions Numériques Simplement Périodiques” (French) (PDF), American Journal of Mathematics (Johns Hopkins University Press) 1 (2): pp. 184-240 et 289-321, doi:10.2307/2369308, http://edouardlucas.free.fr/oeuvres/Theorie_des_fonctions_simplement_periodiques.pdf 
  • （前半の英訳）Lucas, Edouard (1969) (English) (PDF), The Theory of Simply Periodic Numerical Functions, Translated by Sidney Kravitz, Fibonacci Association, p. 77, http://www.fq.math.ca/simply-periodic.html 
• Erdős, P.; Shorey, T. (1976). “On the greatest prime factor of ${\displaystyle 2^{p}-1}$ for a prime p and other expressions”. Acta Arithmetica 30 (3): 257–265. doi:10.4064/aa-30-3-257-265. ISSN 0065-1036. 

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

• 世界大百科事典 第2版『メルセンヌ数』 - コトバンク
• リュカテストによるメルセンヌ素数の発見法 (PDF)
• Weisstein, Eric W. "Mersenne number". mathworld.wolfram.com (英語).
• Weisstein, Eric W. "Mersenne prime". mathworld.wolfram.com (英語).
• Mersenne Primes: History, Theorems and Lists（英語）
• The Largest Known Primes（英語）
• GIMPS（英語）
• 米フロリダ州の男性、わずか4回の試行で51番目のメルセンヌ素数を発見 | スラド サイエンス
• 「史上最大の素数」約2年ぶりに更新、50番目のメルセンヌ素数で桁数は2324万9425桁 | スラド サイエンス
• 史上最大、2,233万8,618桁の素数が発見される | スラド サイエンス
• 45個目のメルセンヌ素数発見か | スラド サイエンス
• 43個目のメルセンヌ素数が発見される | スラド
• 史上最大のメルセンヌ素数発見 | スラド：40個目