メルセンヌ数

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

となる（OEISでは  の場合もメルセンヌ数に含めている）。メルセンヌ数は2進法表記で  桁の 、すなわちレピュニットとなる。

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

## 基本的な性質
 は  の約数の総和に等しい。

 が素数ならば  もまた素数である。このことは、nが合成数であるメルセンヌ数は次のように因数分解できることから分かる：
:
また、この等式より、 のとき  である。一方、  が素数でも  が素数とは限らない。最小の反例は  の場合であり、 が成り立つ。

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

### 完全数
が素数ならば、 は完全数である。

#### 例

* 
* 


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

ならば、 は明らかに偶数であるが、偶数の完全数がこの生成式で表されるものに限られるのかはユークリッド以来約2000年間にわたって未解決であったが、18世紀にオイラーによりこの形に限ることが証明された （奇数の完全数が存在するかという問題は今日なお未解決である。）

### メルセンヌ数の素因数
 を素数とする。
* の素因数は  を法として  と合同、かつ  を法として  または  と合同である。
* のとき、 が  で割れることと、 が素数であることは同値である。
*ある計算可能な正定数  が存在して、 の最大素因数を  について、 。

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

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

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

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

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

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

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

#### メルセンヌの予想

1644年、マラン・メルセンヌは「素数  で  が素数になるのは、 では  の11個の場合だけである」という予想を発表した。しかしメルセンヌ自身はその予想を証明することができず、しかもその予想の一部は誤っていた。

最初の成果はメルセンヌが予想を発表してから128年後、1772年にオイラーにより の場合は素数であることが証明された。その次の成果はさらに104年後、1876年にリュカが効率的な素数判定法を考案して、 の場合は素数でないこと、 の場合は素数であることを証明した。その後リュカ・テストは改良されて、メルセンヌの予想に含まれていなかった素数3個が新たに発見された（の場合（1883年）、の場合（1911年）、の場合（1914年））。メルセンヌが予想した最後の数である  の場合が合成数であることが確定したのは1922年であった。

結局メルセンヌの4個の予想のうち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 によって発見された中では、発見順序と桁数が逆転した初めてのケースである。

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

#### リュカ・テスト
 が  型の素数のとき、,   で を定義すると、
* 任意のS_k (0\leqq k\leqq p-2) がM_pで割り切れないならば、 は合成数である
* S_{p-2} がM_pで割り切れるならば、 は素数である

#### リュカ–レーマー・テスト
 が奇素数のとき、,   で を定義すると、
* S_{p-2} がM_pで割り切れないならば、 は合成数である
* S_{p-2} がM_pで割り切れるならば、 は素数である

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

### メルセンヌ素数の一覧
2024年10月現在知られているメルセンヌ素数は下記の表の52個である。ただし、メルセンヌ素数としての番号が確定しているものは50番目までであり、それよりも大きいメルセンヌ素数については、未発見のメルセンヌ素数が途中にないかを検証中である。

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

となる。

## 未解決問題
*メルセンヌ素数は無数に存在するか？
*素数  に対して  が合成数であるとき、これを**メルセンヌ合成数**と呼ぶことにして、それは無数に存在するか？
*平方因子を持つメルセンヌ数 （ は素数）が存在するか？
* を奇数とするとき、次の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個目