メルセンヌ数(メルセンヌすう、英: Mersenne number)とは、2の冪よりも 1 小さい自然数、すなわち 2 − 1(n は自然数)の形の自然数のことである。これを Mn で表すことが多い。メルセンヌ数を小さい順に列挙すると

となる。メルセンヌ数は2進法表記で n 桁の 11⋯11、すなわちレピュニットとなる。

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

## 基本的な性質

Mn が素数ならば n もまた素数である。このことは、nが合成数のメルセンヌ数が次のように因数分解できることから分かる:

また、この等式より、m | n のとき Mm | Mn である。一方、 p が素数でも Mp が素数とは限らない。最小の反例は p = 11 の場合であり、M11 = 2047 = 23 × 89 が成り立つ。

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

### 完全数

Mp = 2 − 1 が素数ならば、2(2 − 1) は完全数である。この定理はすでに紀元前3世紀頃のユークリッド原論で証明されていた。したがって、完全数の探索はメルセンヌ素数の探索に終始された。

p > 1ならば、2(2 − 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)とは、素数であるメルセンヌ数のことである。

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

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

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

#### 古代~中世

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

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

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

メルセンヌの予想の表: p ≦ 263

|  | | | | | | | | |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 〇:Mpが素数の場合/×:Mpが合成数の場合 水色が正解、ピンク色が間違いを示す。 | | | | | | | | |
| p | 2 | 3 | 5 | 7 | 11 | 13 | 17 | 19 |
| Mp | 〇 | 〇 | 〇 | 〇 | × | 〇 | 〇 | 〇 |
| p | 23 | 29 | 31 | 37 | 41 | 43 | 47 | 53 |
| Mp | × | × | 〇 | × | × | × | × | × |
| p | 59 | 61 | 67 | 71 | 73 | 79 | 83 | 89 |
| Mp | × | 〇 | × | × | × | × | × | 〇 |
| p | 97 | 101 | 103 | 107 | 109 | 113 | 127 | 131 |
| Mp | × | × | × | 〇 | × | × | 〇 | × |
| p | 137 | 139 | 149 | 151 | 157 | 163 | 167 | 173 |
| Mp | × | × | × | × | × | × | × | × |
| p | 179 | 181 | 191 | 193 | 197 | 199 | 211 | 223 |
| Mp | × | × | × | × | × | × | × | × |
| p | 227 | 229 | 233 | 239 | 241 | 251 | 257 | 263 |
| Mp | × | × | × | × | × | × | × | × |

1644年、マラン・メルセンヌは「素数 p で 2 − 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つのメルセンヌ素数を発見して以降、発見にはコンピュータが使用されており、コンピュータの進歩と共に新たなメルセンヌ素数が発見されつつある。

#### GIMPSによる発見

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−1 − 2 (n ≥ 1) で {Sn} を定義すると、

- $M_{p}\not \mid S_{k}\ (0\leqq k\leqq p-2)$ ならば、Mp は合成数である
- $M_{p}\mid S_{p-2}$ ならば、Mp は素数である

##### アルゴリズム

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

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

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

- $M_{p}\not \mid S_{k}\ (0\leqq k\leqq p-2)$ ならば、Mp は合成数である
- $M_{p}\mid S_{p-2}$ ならば、Mp は素数である

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

##### アルゴリズム

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

### メルセンヌ素数の一覧

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

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

となる。

## 未解決問題

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

1. Mn が素数
2. n = 2 ± 1 または 4 ± 3
3. (2 + 1)/3 が素数