メルセンヌ数

メルセンヌ数（メルセンヌすう、テンプレート:Lang-en-short）とは、2の冪よりもテンプレート:Math 小さい自然数、すなわちテンプレート:Math（テンプレート:Mvar は自然数）の形の自然数のことである。これをテンプレート:Mvar で表すことが多い。メルセンヌ数を小さい順に列挙すると

テンプレート:数列

となる。メルセンヌ数は2進法表記でテンプレート:Mvar 桁のテンプレート:Math、すなわちレピュニットとなる。

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

基本的な性質

テンプレート:Mvar はテンプレート:Math の約数の総和に等しい。

テンプレート:Mvar が素数ならばテンプレート:Mvar もまた素数である。このことは、nが合成数のメルセンヌ数が次のように因数分解できることから分かる^[1]テンプレート:Sfn：

テンプレート:Math

また、この等式より、テンプレート:Math のときテンプレート:Math である。一方、テンプレート:Mvar が素数でもテンプレート:Mvar が素数とは限らない。最小の反例はテンプレート:Math の場合であり、テンプレート:Math が成り立つ。

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

完全数

テンプレート:Math が素数ならば、テンプレート:Math は完全数である^[1]^[2]。この定理はすでに紀元前3世紀頃のユークリッド原論で証明されていたテンプレート:Sfn。したがって、完全数の探索はメルセンヌ素数の探索に終始された。

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

メルセンヌ数の素因数

テンプレート:Mvar を素数とする。

テンプレート:Mvar の素因数はテンプレート:Math を法としてテンプレート:Math と合同テンプレート:Sfn、かつテンプレート:Math を法としてテンプレート:Math またはテンプレート:Math と合同である^[3]。
テンプレート:Math のとき、テンプレート:Mvar がテンプレート:Math で割れることと、テンプレート:Math が素数であることは同値である^[3]。
ある計算可能な正定数テンプレート:Mvar が存在して、テンプレート:Mvar の最大素因数をテンプレート:Mvar について、テンプレート:Math ^[4]。

倍積完全数

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

メルセンヌ素数

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

2024年10月現在発見されているメルセンヌ素数は全部で52個ある。その中で最大のものは2024年 10月に発見されたテンプレート:Math であり、十進法で表記したときの桁数は4102万4320桁に及ぶ^{[GIMPS 1]}。

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

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

古代～中世

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

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

メルセンヌの予想

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

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

1644年、マラン・メルセンヌは「素数テンプレート:Mvar でテンプレート:Math が素数になるのは、テンプレート:Math ではテンプレート:Math の11個の場合だけである」という予想を公表した^[7]^[11]。しかしメルセンヌ自身はその予想を証明することができず、しかもその予想の一部は誤っていた。

成果をもたらしたのはメルセンヌが予想を公表してから128年後、1772年のオイラー（テンプレート:Math では素数）^[1]テンプレート:Sfnである。その次の成果はさらに104年後、1876年、リュカ（効率的な素数判定法テンプレート:Ill2を考案、テンプレート:Math では素数でない、テンプレート:Math では素数^[1]テンプレート:Sfn）によってもたらされた。その後リュカ・テストは改良が加えられ、メルセンヌが予想した範囲にない3個が付け加えられた（テンプレート:Math（1883年）、テンプレート:Math（1911年）、テンプレート:Math（1914年））。メルセンヌが予想した最後の数テンプレート:Math について決着がついたのは1922年のことであり、テンプレート:Math も合成数だった^[1]テンプレート:Sfn。

結局メルセンヌの4個の予想のうち2つは外れた。なおかつ、間に予想できなかった3つが含まれていたことを考えれば予想は正しかったとはいえないが、その後の歴史を見ても大きな原動力となり先駆的であったことに敬意を表し、素数であるメルセンヌ数をメルセンヌ素数というテンプレート:要出典。

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

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

GIMPSによる発見

1996年、メルセンヌ素数を発見することを目的として作られた分散コンピューティングによるプロジェクト GIMPS が発足し、35番目のメルセンヌ素数テンプレート:Math（1996年11月13日、Joel Armengaud^{[GIMPS 2]}）以来、GIMPSによるメルセンヌ素数の発見が続いている。

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

2008年9月6日、GIMPS は45番目の素数候補が、ドイツで発見されたと報じたテンプレート:要出典。これは、GIMPS によって発見された中では、発見順序と桁数が逆転した初めてのケースである。

素数判定法

知られている素数の中で最大のものが1876年以降ほぼ一貫してメルセンヌ素数である理由は、この判定法にあるテンプレート:要出典。

リュカ・テスト

テンプレート:Mvar がテンプレート:Math 型の素数のとき、テンプレート:Math, テンプレート:Math テンプレート:Math でテンプレート:Mathを定義すると、

$M_{p} ∤ S_{k} (0 ≦ k ≦ p - 2)$ ならば、テンプレート:Mvar は合成数である
$M_{p} ∣ S_{p - 2}$ ならば、テンプレート:Mvar は素数であるテンプレート:Sfn テンプレート:Sfn テンプレート:Sfn

テンプレート:For2

アルゴリズム

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

入力: p: テンプレート:Math 型の素数であるテスト対象の整数
出力: PRIME:素数の場合, COMPOSIT:合成数の場合
Lucas_Test(p):
    var s = 3
    var MP = (1 << p) − 1
    for n in range(2, p):
        s = (s² − 2) % MP
    if s == 0 then:
        return PRIME
    else:
        return COMPOSIT

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

テンプレート:Mvar が奇素数のとき、テンプレート:Math, テンプレート:Math テンプレート:Math でテンプレート:Math を定義すると、

$M_{p} ∤ S_{k} (0 ≦ k ≦ p - 2)$ ならば、テンプレート:Mvar は合成数である
$M_{p} ∣ S_{p - 2}$ ならば、テンプレート:Mvar は素数であるテンプレート:Sfn テンプレート:Sfn テンプレート:Sfn

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

アルゴリズム

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

入力: p:奇素数であるテスト対象の整数
出力: PRIME:素数の場合, COMPOSIT:合成数の場合
Lucas_Lehmer_Test(p):
    var s = 4
    var MP = (1 << p) − 1
    for n in range(2, p):
        s = (s² − 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

メルセンヌ素数の一覧

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

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

テンプレート:数列

となる。

#	テンプレート:Mvar	テンプレート:Mvar の桁数	発見日	発見者
1	2	1	紀元前500年?^[12]
2	3	1	紀元前500年?^[12]
3	5	2	紀元前275年?^[12]
4	7	3	紀元前275年?^[12]
5	13	4	1456年テンプレート:Refn	不明テンプレート:Refn
6	17	6	1603年^[7]	テンプレート:仮リンク
7	19	6	1603年^[7]	ピエトロ・カタルディ
8	31	10	1772年	レオンハルト・オイラー
9	61	19	1883年	テンプレート:仮リンク
10	89	27	1911年	テンプレート:仮リンク
11	107	33	1914年	R・E・パワーズ^[13]
12	127	39	1876年	エドゥアール・リュカ
13	521	157	1952年1月30日	テンプレート:仮リンク, 使用：SWAC
14	607	183	1952年1月30日	ラファエル・M・ロビンソン
15	1,279	386	1952年6月25日	ラファエル・M・ロビンソン
16	2,203	664	1952年10月7日	ラファエル・M・ロビンソン
17	2,281	687	1952年10月9日	ラファエル・M・ロビンソン
18	3,217	969	1957年9月8日	ハンス・リーゼル, 使用：BESK
19	4,253	1,281	1961年11月3日	アレクサンダー・フルウィッツ, 使用：IBM 7090
20	4,423	1,332	1961年11月3日	アレクサンダー・フルウィッツ
21	9,689	2,917	1963年5月11日	ドナルド・ギリース, 使用：ILLIAC II
22	9,941	2,993	1963年5月16日	ドナルド・ギリース
23	11,213	3,376	1963年6月2日	ドナルド・ギリース
24	19,937	6,002	1971年3月4日	テンプレート:仮リンク, 使用：IBM 360/91
25	21,701	6,533	1978年10月30日	テンプレート:仮リンク & ローラ・ニッケル, 使用：CDC Cyber 174
26	23,209	6,987	1979年2月9日	ランドン・カート・ノル
27	44,497	13,395	1979年4月8日	ハリー・ネルソン & テンプレート:仮リンク
28	86,243	25,962	1982年9月25日	デイヴィッド・スローウィンスキー
29	110,503	33,265	1988年1月28日	ウォルター・コルキット & ルーク・ウェルシュ
30	132,049	39,751	1983年9月19日^[12]	デイヴィッド・スローウィンスキー
31	216,091	65,050	1985年9月1日^[12]	デイヴィッド・スローウィンスキー
32	756,839	227,832	1992年2月19日	デイヴィッド・スローウィンスキー & テンプレート:仮リンク使用：Harwell Lab Cray-2^[14]
33	859,433	258,716	1994年1月4日^[15]	デイヴィッド・スローウィンスキー & ポール・ゲイジ
34	1,257,787	378,632	1996年9月3日	デイヴィッド・スローウィンスキー & ポール・ゲイジ^[16]
35	1,398,269	420,921	1996年11月13日	GIMPS / Joel Armengaud^{[GIMPS 2]}
36	2,976,221	895,932	1997年8月24日	GIMPS / Gordon Spence^{[GIMPS 4]}
37	3,021,377	909,526	1998年1月27日	GIMPS / Roland Clarkson^{[GIMPS 5]}
38	6,972,593	2,098,960	1999年6月1日	GIMPS / Nayan Hajratwala^{[GIMPS 6]}
39	13,466,917	4,053,946	2001年11月14日	GIMPS / Michael Cameron^{[GIMPS 7]}
40	20,996,011	6,320,430	2003年11月17日	GIMPS / Michael Shafer^{[GIMPS 8]}
41	24,036,583	7,235,733	2004年5月15日	GIMPS / Josh Findley^{[GIMPS 9]}
42	25,964,951	7,816,230	2005年2月18日	GIMPS / Martin Nowak et al.^{[GIMPS 10]}
43	30,402,457	9,152,052	2005年12月15日	GIMPS / テンプレート:仮リンク, Steven Boone^{[GIMPS 11]}
44	32,582,657	9,808,358	2006年9月4日	GIMPS / カーティス・クーパー, Steven Boone^{[GIMPS 12]}
45	37,156,667	11,185,272	2008年9月6日	GIMPS / Hans-Michael Elvenich^{[GIMPS 3]}
46	42,643,801	12,837,064	2009年4月12日	GIMPS / Odd Magnar Strindmo
47	43,112,609	12,978,189	2008年8月23日	GIMPS / エドソン・スミス^{[GIMPS 3]}
48	57,885,161	17,425,170	2013年1月25日	GIMPS / カーティス・クーパー^[17]^{[GIMPS 13]}
テンプレート:Refn	74,207,281	22,338,618	2016年1月7日	GIMPS / カーティス・クーパー^{[GIMPS 14]}
テンプレート:Refn	77,232,917	23,249,425	2017年12月26日	GIMPS / Jonathan Pace^{[GIMPS 15]}
テンプレート:Refn	82,589,933	24,862,048	2018年12月7日	GIMPS / Patrick Laroche^{[GIMPS 16]}
テンプレート:Refn	136,279,841	41,024,320	2024年10月21日	GIMPS / Luke Durant^{[GIMPS 1]}

テンプレート:Reflist

未解決問題

メルセンヌ素数は無数に存在するか？
素数テンプレート:Mvar に対してテンプレート:Mvar が合成数であるとき、これをメルセンヌ合成数^[18]^[19]と呼ぶことにして、それは無数に存在するか？
平方因子を持つメルセンヌ数テンプレート:Mvar（テンプレート:Mvar は素数）が存在するか？
テンプレート:Mvar を奇数とするとき、次の3つの条件のうち2つが満たされれば、残りの1つも満足されると予想されており、テンプレート:Math に対してこの予想は正しいと確認されている^[20]。

脚注

テンプレート:脚注ヘルプ

注釈

テンプレート:Notelist

出典

テンプレート:Reflist

GIMPS

参考文献

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

外部リンク

テンプレート:素数の分類テンプレート:Classes of natural numbers テンプレート:巨大数

↑ ^1.0 ^1.1 ^1.2 ^1.3 ^1.4 ^1.5 テンプレート:Harvnb.
↑ ^2.0 ^2.1 テンプレート:Harvnb
↑ ^3.0 ^3.1 テンプレート:Harvnb
↑ Theorem 1, テンプレート:Harvnb
↑ テンプレート:Cite web
↑ テンプレート:Cite book
↑ ^7.0 ^7.1 ^7.2 ^7.3 ^7.4 テンプレート:Cite web
↑ テンプレート:Cite book
↑ テンプレート:Citation
↑ テンプレート:OEIS
↑ テンプレート:Cite book
↑ ^12.0 ^12.1 ^12.2 ^12.3 ^12.4 ^12.5 Landon Curt Noll, Mersenne Prime Digits and Names.
↑ The Prime Pages, M テンプレート:Sub: Fauquembergue or Powers?.
↑ The Prime Pages, The finding of the 32nd Mersenne.
↑ Chris Caldwell, The Largest Known Primes.
↑ The Prime Pages, A Prime of Record Size! 2 テンプレート:Sup − 1.
↑ テンプレート:Cite news
↑ テンプレート:Cite journal
↑ テンプレート:Cite journal
↑ P. T. Bateman, J. L. Selfridge, S. S. Wagstaff Jr., "The new Mersenne conjecture", American Mathematical Monthly, 96 (1989), 125–128.

[:3-5] 1.0 ^1.1 テンプレート:Cite press release

[:0-13] 2.0 ^2.1 テンプレート:Cite press release

[:1-14] 3.0 ^3.1 ^3.2 テンプレート:Cite press release

[20] テンプレート:Cite press release

[21] テンプレート:Cite press release

[22] テンプレート:Cite press release

[23] テンプレート:Cite press release

[24] テンプレート:Cite press release

[25] テンプレート:Cite press release

[26] テンプレート:Cite press release

[27] テンプレート:Cite press release

[28] テンプレート:Cite press release

[30] テンプレート:Cite press release

[31] テンプレート:Cite press release

[32] テンプレート:Cite press release

[:2-33] テンプレート:Cite press release

[Tannaka1982-1] 1.0 ^1.1 ^1.2 ^1.3 ^1.4 ^1.5 テンプレート:Harvnb.

[Wada1981pp59-61-2] 2.0 ^2.1 テンプレート:Harvnb

[Wada1981p193-3] 3.0 ^3.1 テンプレート:Harvnb

[4] Theorem 1, テンプレート:Harvnb

[6] テンプレート:Cite web

[7] テンプレート:Cite book

[:1-8] 7.0 ^7.1 ^7.2 ^7.3 ^7.4 テンプレート:Cite web

[9] テンプレート:Cite book

[10] テンプレート:Citation

[11] テンプレート:OEIS

[12] テンプレート:Cite book

[isthe-15] 12.0 ^12.1 ^12.2 ^12.3 ^12.4 ^12.5 Landon Curt Noll, Mersenne Prime Digits and Names.

[16] The Prime Pages, M テンプレート:Sub: Fauquembergue or Powers?.

[17] The Prime Pages, The finding of the 32nd Mersenne.

[18] Chris Caldwell, The Largest Known Primes.

[19] The Prime Pages, A Prime of Record Size! 2 テンプレート:Sup − 1.

[29] テンプレート:Cite news

[34] テンプレート:Cite journal

[35] テンプレート:Cite journal

[36] P. T. Bateman, J. L. Selfridge, S. S. Wagstaff Jr., "The new Mersenne conjecture", American Mathematical Monthly, 96 (1989), 125–128.

[1]

[2]

[3]

[4]

[GIMPS 1]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[GIMPS 2]

[GIMPS 3]

[12]

[13]

[14]

[15]

[16]

[GIMPS 4]

[GIMPS 5]

[GIMPS 6]

[GIMPS 7]

[GIMPS 8]

[GIMPS 9]

[GIMPS 10]

[GIMPS 11]

[GIMPS 12]

[17]

[GIMPS 13]

[GIMPS 14]

[GIMPS 15]

[GIMPS 16]

[18]

[19]

[20]

メルセンヌ数

目次

基本的な性質

完全数

メルセンヌ数の素因数

倍積完全数

メルセンヌ素数

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

古代～中世

メルセンヌの予想

GIMPSによる発見

素数判定法

リュカ・テスト

アルゴリズム

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

アルゴリズム

メルセンヌ素数の一覧

未解決問題

脚注

注釈

出典

GIMPS

参考文献

関連項目

外部リンク

ナビゲーションメニュー

メルセンヌ数

基本的な性質

完全数

メルセンヌ数の素因数

倍積完全数

メルセンヌ素数

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

古代～中世

メルセンヌの予想

GIMPSによる発見

素数判定法

リュカ・テスト

アルゴリズム

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

アルゴリズム

メルセンヌ素数の一覧

未解決問題

脚注

注釈

出典

GIMPS

参考文献

関連項目

外部リンク

ナビゲーション メニュー

検索

ナビゲーションメニュー