メルセンヌ数

メルセンヌ数（メルセンヌすう、）とは、2の冪よりも 小さい自然数、すなわち （ は自然数）の形の自然数のことである。これを で表すことが多い。メルセンヌ数を小さい順に列挙すると
となる。メルセンヌ数は2進法表記で 桁の 、すなわちレピュニットとなる。
 が素数ならば もまた素数であるが、逆は成立しない ()。素数であるメルセンヌ数をメルセンヌ素数（メルセンヌそすう、）という。なお、「メルセンヌ数」という語で、 が素数であるもののみを指したり、さらに狭義の意味でメルセンヌ素数を指す場合もある。
基本的な性質.
 が素数ならば もまた素数であることは、次の式から分かる：
対偶命題「 が合成数ならば は合成数である」が示される。また、この等式より、 のとき である。一方、 が素数でも が素数とは限らない。最小の反例は の場合であり、 が成り立つ。
(奇)素数 に対して が素数であるかどうかは、リュカ-レーマー・テストによって判定できる (#素数判定法節を参照)。
完全数.
 が素数ならば、 は完全数である。この定理はすでに紀元前3世紀頃のユークリッド原論で証明されていた。したがって、完全数の探索はメルセンヌ素数の探索に終始された。
 は明らかに偶数であるが、偶数の完全数でこの生成式から得られるもの以外はないのか2000年間にわたって未解決であったが、18世紀にオイラーによりこの形に限ることが証明された。
メルセンヌ数の素因数.
 を素数とする。
メルセンヌ素数.
メルセンヌ素数（メルセンヌそすう、Mersenne prime）とは、素数であるメルセンヌ数のことである。
2022年2月現在知られている最大のメルセンヌ素数は、2018年12月に発見された、それまでに分かっている中で51番目のメルセンヌ素数 であり、十進法で表記したときの桁数は2486万2048桁に及ぶ。
メルセンヌ素数の発見の歴史.
古代～中世.
メルセンヌ素数の探求は紀元前3世紀ごろに端を発する。古代エジプトの数学者エウクレイデスは『原論』の中で、「 が素数ならば、 は完全数である」ことを証明した。ここから、メルセンヌ素数の探索は完全数の探索にも繋がることとなる。
小さいメルセンヌ素数がいつから知られているかは定かではないが、少なくとも最初の4つの完全数はゲラサのニコマコスの『算術入門』ですでに言及されている。5番目から7番目の完全数は、13世紀イスラムの数学者イブン・ファッルースが論文に記している。ヨーロッパでは、5番目の完全数が1456年と1461年の日付が付された古い写本に記されており、6番目と7番目のメルセンヌ素数および完全数も1603年にによって発見されている。
メルセンヌの予想.
1644年、マラン・メルセンヌは「素数 で が素数になるのは、 では の11個の場合だけである」という予想を公表した。しかしメルセンヌ自身はその予想を証明することができず、しかもその予想の一部は誤っていた。
成果を見るのはメルセンヌが予想を公表してから128年後、1772年、オイラー（ では素数）。その次の成果はさらに104年後、1876年、リュカ（効率的な素数判定法を考案、 では素数でない、 では素数）であった。その後リュカ・テストは改良が加えられ、メルセンヌが予想した範囲にない3個が付け加えられた（（1883年）、（1911年）、（1914年））。メルセンヌが予想した最後の数 について決着がついたのは1922年のことであり、 も合成数だった。
結局メルセンヌの11個の予想のうち2つは外れた。なおかつ、間に予想できなかった3つが含まれていたことを考えれば予想は正しかったとはいえないが、その後の歴史を見ても大きな原動力となり先駆的であったことに敬意を表し、素数であるメルセンヌ数をメルセンヌ素数という。
1903年10月、アメリカの数学者フランク・ネルソン・コールは実際の素因数分解を探し求め、ニューヨークで開かれたアメリカ数学会の会議で を黒板に計算し、 と一致することを証明した。この間一言もしゃべらず、席に戻った後、少し間を置いて拍手が沸き起こったと伝えられている。
1952年、ラファエル・M・ロビンソンが 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 によって発見された中では、発見順序と桁数が逆転した初めてのケースである。
素数判定法.
知られている素数の中で最大のものが1876年以降ほぼ一貫してメルセンヌ素数である理由は、この判定法にある。
リュカ・テスト.
 が 型の素数のとき、, で を定義すると、
アルゴリズム.
アルゴリズムは以下の擬似コードで表される。
 入力: "p": 型の素数であるテスト対象の整数
 出力: "PRIME":素数の場合, "COMPOSIT":合成数の場合
 Lucas_Test("p"):
 var s = 3
 var MP = (1 « p) − 1
 for n in range(2, p):
 s = (s"2" − 2) % MP
 if s == 0 then:
 return "PRIME"
 else:
 return "COMPOSIT"
リュカ–レーマー・テスト.
 が奇素数のとき、, で を定義すると、
リュカ–レーマー・テストは二進計算機用のアルゴリズムに向いており、コンピュータによるメルセンヌ素数の発見には、この判定法が用いられてきた。例えば、 より、 が成り立つので、 で割る割り算の代わりに、二進法で 桁のシフト演算と足し算だけで計算できる。
アルゴリズム.
アルゴリズムは以下の擬似コードで表される。
 入力: "p":奇素数であるテスト対象の整数
 出力: "PRIME":素数の場合, "COMPOSIT":合成数の場合
 Lucas_Lehmer_Test("p"):
 var s = 4
 var MP = (1 « p) − 1
 for n in range(2, p):
 s = (s"2" − 2) % MP
 if s == 0 then:
 return "PRIME"
 else:
 return "COMPOSIT"
 入力: "p":奇素数であるテスト対象の整数
 出力: "PRIME":素数の場合, "COMPOSIT":合成数の場合
 Lucas_Lehmer_Test_FAST("p"):
 var s = 4
 var m = 2"p" − 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番目までであり、
における がそうである。さらに49, 50, 51番目の候補として が挙がっており、間に素数がないかどうか検証中である。
メルセンヌ素数は小さい順番から並べると
となる。