メルセンヌ数

メルセンヌ数（メルセンヌすう、英: Mersenne number）とは、2の冪よりも 1 小さい自然数、すなわち 2n − 1（n は自然数）の形の自然数のことである。これを Mn で表すことが多い。メルセンヌ数を小さい順に列挙すると 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, ... (オンライン整数列大辞典の数列 A000225) となる。メルセンヌ数は2進法表記で n 桁の 11⋯11、すなわちレピュニットとなる。 Mn = 2n − 1 が素数ならば n もまた素数であるが、逆は成立しない (M11 = 2047 = 23 × 89)。素数であるメルセンヌ数をメルセンヌ素数（メルセンヌそすう、英: Mersenne prime）という。なお、「メルセンヌ数」という語で、n が素数であるもののみを指したり、さらに狭義の意味でメルセンヌ素数を指す場合もある。 Mn が素数ならば n もまた素数であることは、次の式から分かる： 2ab − 1 = (2a − 1)(1 + 2a + 22a + ⋯ + 2(b−1)a). 対偶命題「n が合成数ならば Mn は合成数である」が示される。また、この等式より、m | n のとき Mm | Mn である。一方、 p が素数でも Mp が素数とは限らない。最小の反例は p = 11 の場合であり、M11 = 2047 = 23 × 89 が成り立つ。 (奇)素数 p に対して Mp が素数であるかどうかは、リュカ-レーマー・テストによって判定できる (#素数判定法節を参照)。 Mp = 2p − 1 が素数ならば、2p−1(2p − 1) は完全数である。この定理はすでに紀元前3世紀頃のユークリッド原論で証明されていた。したがって、完全数の探索はメルセンヌ素数の探索に終始された。 2p−1(2p − 1) は明らかに偶数であるが、偶数の完全数でこの生成式から得られるもの以外はないのか2000年間にわたって未解決であったが、18世紀にオイラーによりこの形に限ることが証明された。 p を素数とする。 Mp の素因数は 2p を法として 1 と合同、かつ 8 を法として 1 または −1 と合同である。 p ≡ 3 (mod 4) のとき、Mp が 2p + 1 で割れることと、2p + 1 が素数であることは同値である。 ある計算可能な正定数 c が存在して、Mp の最大素因数を q について、q ≥ cp log p 。 メルセンヌ素数（メルセンヌそすう、Mersenne prime）とは、素数であるメルセンヌ数のことである。 2022年2月現在知られている最大のメルセンヌ素数は、2018年12月に発見された、それまでに分かっている中で51番目のメルセンヌ素数 282589933 − 1 であり、十進法で表記したときの桁数は2486万2048桁に及ぶ。 メルセンヌ素数の探求は紀元前3世紀ごろに端を発する。古代エジプトの数学者エウクレイデスは『原論』の中で、「2n − 1 が素数ならば、2n − 1(2n − 1) は完全数である」ことを証明した。ここから、メルセンヌ素数の探索は完全数の探索にも繋がることとなる。 小さいメルセンヌ素数がいつから知られているかは定かではないが、少なくとも最初の4つの完全数はゲラサのニコマコスの『算術入門』ですでに言及されている。5番目から7番目の完全数は、13世紀イスラムの数学者イブン・ファッルース (fr:Ibn Fallus) が論文に記している。ヨーロッパでは、5番目の完全数が1456年と1461年の日付が付された古い写本に記されており、6番目と7番目のメルセンヌ素数および完全数も1603年にピエトロ・カタルディ（英: Pietro Cataldi）によって発見されている。 1644年、マラン・メルセンヌは「素数 p で 2p − 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 も合成数だった。 結局メルセンヌの11個の予想のうち2つは外れた。なおかつ、間に予想できなかった3つが含まれていたことを考えれば予想は正しかったとはいえないが、その後の歴史を見ても大きな原動力となり先駆的であったことに敬意を表し、素数であるメルセンヌ数をメルセンヌ素数という[要出典]。 1903年10月、アメリカの数学者フランク・ネルソン・コールは実際の素因数分解を探し求め、ニューヨークで開かれたアメリカ数学会の会議で 193707721 × 761838257287 を黒板に計算し、M67 と一致することを証明した。この間一言もしゃべらず、席に戻った後、少し間を置いて拍手が沸き起こったと伝えられている。 1952年、ラファエル・M・ロビンソンが SWAC を利用して M521 から M2281 まで、5つのメルセンヌ素数を発見して以降、発見にはコンピュータが使用されており、コンピュータの進歩と共に新たなメルセンヌ素数が発見されつつある。 1996年、メルセンヌ素数を発見することを目的として作られた分散コンピューティングによるプロジェクト GIMPS が発足し、35番目のメルセンヌ素数 M1,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 によって発見された中では、発見順序と桁数が逆転した初めてのケースである。 知られている素数の中で最大のものが1876年以降ほぼ一貫してメルセンヌ素数である理由は、この判定法にある[要出典]。 p が (4j + 3) 型の素数のとき、S0 = 3, Sn = Sn−12 − 2 (n ≥ 1) で {Sn} を定義すると、 M p ∤ S k   ( 0 ≦ k ≦ p − 2 ) {\displaystyle M_{p}\not \mid S_{k}\ (0\leqq k\leqq p-2)} ならば、Mp は合成数である M p ∣ S p − 2 {\displaystyle M_{p}\mid S_{p-2}} ならば、Mp は素数である アルゴリズムは以下の擬似コードで表される。 入力: 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 が奇素数のとき、S0 = 4, Sn = Sn−12 − 2 (n ≥ 1) で{Sn} を定義すると、 M p ∤ S k   ( 0 ≦ k ≦ p − 2 ) {\displaystyle M_{p}\not \mid S_{k}\ (0\leqq k\leqq p-2)} ならば、Mp は合成数である M p ∣ S p − 2 {\displaystyle M_{p}\mid S_{p-2}} ならば、Mp は素数である リュカ–レーマー・テストは二進計算機用のアルゴリズムに向いており、コンピュータによるメルセンヌ素数の発見には、この判定法が用いられてきた。例えば、2p ≡ 1 (mod Mp) より、A·2p + B ≡ A + B (mod Mp) が成り立つので、Mp で割る割り算の代わりに、二進法で 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） における Mp がそうである。さらに49, 50, 51番目の候補として p = 74207281, 77232917, 82589933 が挙がっており、間に素数がないかどうか検証中である。 メルセンヌ素数は小さい順番から並べると 3, 7, 31, 127, 8191, 131071, 524287, 2147483647, ... (A000668) となる。