メルセンヌ数

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

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

//Msub が素数ならば n}} もまた素数であるが、逆は成立しない 。素数であるメルセンヌ数をメルセンヌ素数という。なお、「メルセンヌ数」という語で、n}} が素数であるもののみを指したり、さらに狭義の意味でメルセンヌ素数を指す場合もある『[[#CITEREF日本数学会1985。//

1. 基本的な性質
---------

Msub が素数ならば n}} もまた素数であることは、次の式から分かる中村：

対偶命題「n}} が合成数ならば Msub は合成数である」が示される。また、この等式より、//m// !}} //n//}} のとき //M//sub である。一方、 p}} が素数でも Msub が素数とは限らない。最小の反例は 1=//p// = 11}} の場合であり、//M//sub が成り立つ。

素数 p}} に対して Msub が素数であるかどうかは、リュカ-レーマー・テストによって判定できる 。

1.1. 完全数
--------

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

2sup は明らかに偶数であるが、偶数の完全数でこの生成式から得られるもの以外はないのか2000年間にわたって未解決であったが、18世紀にオイラーによりこの形に限ることが証明された。

1.2. メルセンヌ数の素因数
---------------

p}} を素数とする。

Msub の素因数は 2//p//}} を法として 1}} と合同和田、かつ 8}} を法として 1}} または −1}} と合同である。
//p// ≡ 3 }} のとき、Msub が 2//p// + 1}} で割れることと、2//p// + 1}} が素数であることは同値である。
ある計算可能な正定数 c}} が存在して、Msub の最大素因数を q}} について、//q// ≥ //cp// log //p//}} 。

2. メルセンヌ素数
----------

メルセンヌ素数とは、素数であるメルセンヌ数のことである。

2022年2月現在知られている最大のメルセンヌ素数は、2018年12月に発見された、それまでに分かっている中で51番目のメルセンヌ素数 2sup であり、十進法で表記したときの桁数は2486万2048桁に及ぶ。

2.1. メルセンヌ素数の発見の歴史
------------------

2.1.1. 古代～中世
------------

メルセンヌ素数の探求は紀元前3世紀ごろに端を発する。古代エジプトの数学者エウクレイデスは『原論』の中で、「2//n// − 1}} が素数ならば、2//n// − 1}} は完全数である」ことを証明した『原論』 第9巻, 命題36. (pp. 225–226, Harvnb。ここから、メルセンヌ素数の探索は完全数の探索にも繋がることとなるCite webMath。

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

2.1.2. メルセンヌの予想
---------------

1644年、マラン・メルセンヌは「素数 p}} で 2sup が素数になるのは、//p// ≦ 257}} では //p// =}} 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257}} の11個の場合だけである」という予想を公表した。しかしメルセンヌ自身はその予想を証明することができず、しかもその予想の一部は誤っていた。

成果を見るのはメルセンヌが予想を公表してから128年後、1772年、オイラー和田。その次の成果はさらに104年後、1876年、リュカであった。その後リュカ・テストは改良が加えられ、メルセンヌが予想した範囲にない3個が付け加えられた。メルセンヌが予想した最後の数 //p// =}} 257}} について決着がついたのは1922年のことであり、 //p// =}} 257}} も合成数だった中村。

結局メルセンヌの11個の予想のうち2つは外れた。なおかつ、間に予想できなかった3つが含まれていたことを考えれば予想は正しかったとはいえないが、その後の歴史を見ても大きな原動力となり先駆的であったことに敬意を表し、素数であるメルセンヌ数をメルセンヌ素数というdate=2022年2月}}。

1903年10月、アメリカの数学者フランク・ネルソン・コールは実際の素因数分解を探し求め、ニューヨークで開かれたアメリカ数学会の会議で 193707721 × 761838257287}} を黒板に計算し、//M//sub と一致することを証明した。この間一言もしゃべらず、席に戻った後、少し間を置いて拍手が沸き起こったと伝えられている中村。

1952年、ラファエル・M・ロビンソンが SWAC を利用して //M//sub から //M//sub まで、5つのメルセンヌ素数を発見して以降、発見にはコンピュータが使用されており、コンピュータの進歩と共に新たなメルセンヌ素数が発見されつつある。

2.1.3. GIMPSによる発見
-----------------

1996年、メルセンヌ素数を発見することを目的として作られた分散コンピューティングによるプロジェクト GIMPS が発足し、35番目のメルセンヌ素数 //M//sub以来、GIMPSによるメルセンヌ素数の発見が続いている。

2008年8月23日、GIMPS は46番目の素数候補が、カリフォルニア大学ロサンゼルス校の数学部のコンピュータによって発見されたと報じたdate=2022年2月}}。この素数は電子フロンティア財団が賞金を懸けた1000万桁以上の最初の素数となるため、GIMPS によって同校数学部に50,000ドル、慈善事業に25,000ドル、残りを前の6つのメルセンヌ素数の発見者へ分配することになった。

2008年9月6日、GIMPS は45番目の素数候補が、ドイツで発見されたと報じたdate=2022年2月}}。これは、GIMPS によって発見された中では、発見順序と桁数が逆転した初めてのケースである。

2.2. 素数判定法
----------

知られている素数の中で最大のものが1876年以降ほぼ一貫してメルセンヌ素数である理由は、この判定法にあるdate=2022年2月}}。

2.2.1. リュカ・テスト
--------------

p}} が }} 型の素数のとき、//S//sub, //Ssub }} で //Ssubを定義すると、

ならば、Msub は合成数である
ならば、Msub は素数である中村Lucas

2.2.1.1. アルゴリズム
---------------

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

入力: //p//: }} 型の素数であるテスト対象の整数出力: //PRIME//:素数の場合, //COMPOSIT//:合成数の場合Lucas_Test:var s = 3var MP =  − 1for n in range: s =  % MPif s == 0 then:return //PRIME//else:return //COMPOSIT//

2.2.2. リュカ–レーマー・テスト
-------------------

p}} が奇素数のとき、//S//sub, //Ssub }} で//Ssub を定義すると、

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

2.2.2.1. アルゴリズム
---------------

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

入力: //p//:奇素数であるテスト対象の整数出力: //PRIME//:素数の場合, //COMPOSIT//:合成数の場合Lucas_Lehmer_Test:var s = 4var MP =  − 1for n in range: s =  % MPif s == 0 then:return //PRIME//else:return //COMPOSIT//

入力: //p//:奇素数であるテスト対象の整数出力: //PRIME//:素数の場合, //COMPOSIT//:合成数の場合Lucas_Lehmer_Test_FAST:var s = 4var m = 2//p// − 1for n in range:var s2 = s × s s =  + if s >= m then s = s − m s = s − 2if s == 0 thenreturn //PRIME//elsereturn //COMPOSIT//

2.3. メルセンヌ素数の一覧
---------------

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}}における Msub がそうである。さらに49, 50, 51番目の候補として //p// =}} 74207281, 77232917, 82589933}} が挙がっており、間に素数がないかどうか検証中である。

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

となる。



3. 未解決問題
--------

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

4. 脚注
-----

4.1. 注釈
-------

4.2. 出典
-------

4.3. GIMPS
----------

5. 参考文献
-------

和書- 全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次式の整数論。

6. 関連項目
-------

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

7. 外部リンク
--------

[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]：40個目