メルセンヌ数

メルセンヌ数（メルセンヌすう、）とは、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 = (s2 − 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 = (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番目までであり、
（）
における  がそうである。さらに49, 50, 51番目の候補として  が挙がっており、間に素数がないかどうか検証中である。

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

となる。

未解決問題 
メルセンヌ素数は無数に存在するか？
素数  に対して  が合成数であるとき、これをメルセンヌ合成数と呼ぶことにして、それは無数に存在するか？
平方因子を持つメルセンヌ数 （ は素数）が存在するか？
 を奇数とするとき、次の3つの条件のうち2つが満足されれば、残りの1つも満足されると予想されており、 に対してこの予想は正しいと確認されている。 
 が素数
 または 
 が素数

脚注

注釈

出典

GIMPS

参考文献 

 - 全13巻の最初の邦訳。
（ハードカバー）1971年7月。ISBN 4-320-01072-8
（縮刷版）1996年6月。ISBN 4-320-01513-4
（追補版）2011年5月。ISBN 978-4-320-01965-2
 - 前編は1次式の整数論、後編は2次式の整数論。

（前半の英訳）

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

外部リンク 

Mersenne Primes: History, Theorems and Lists
The Largest Known Primes
GIMPS
米フロリダ州の男性、わずか4回の試行で51番目のメルセンヌ素数を発見 | スラド サイエンス
「史上最大の素数」約2年ぶりに更新、50番目のメルセンヌ素数で桁数は2324万9425桁 | スラド サイエンス
史上最大、2,233万8,618桁の素数が発見される | スラド サイエンス
45個目のメルセンヌ素数発見か | スラド サイエンス
43個目のメルセンヌ素数が発見される | スラド
史上最大のメルセンヌ素数発見 | スラド：40個目

数論
整数の類
数学に関する記事
素数
数学のエポニム