メルセンヌ数

メルセンヌ数（メルセンヌすう、テンプレート:Lang-en-short）とは、2の冪よりも 1 小さい自然数、すなわち 2ⁿ − 1（n は自然数）の形の自然数のことである。これを M_n で表すことが多い。2進数で表記すると、n 桁の 11…11 である。特に、素数であるメルセンヌ数をメルセンヌ素数（メルセンヌそすう、テンプレート:Lang-en-short）という。M_n が素数ならば n は素数であるが、逆に n が素数であっても M_n は素数とは限らない (M₁₁ = 23 × 89)。後述するように、効率的な素数判定法によって、巨大な素数の実例としてメルセンヌ素数を発見することが特に興味の対象となっている。このため近年では、分散コンピューティングによるプロジェクト GIMPS (Great Internet Mersenne Prime Search) によるメルセンヌ素数の発見が進められている。

なお、「メルセンヌ数」という語で、n が素数であるもののみを指したり^[1]、さらに狭くメルセンヌ素数を指す場合もある^[2]。

歴史

1644年にマラン・メルセンヌは、 2ⁿ − 1 が素数になるのは、n ≤ 257 では、n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257 だけであると主張した。しかしその主張の一部は誤っていた。リストに含まれていない M₆₁, M₈₉, M₁₀₇ が素数であり、リストに含まれている M₆₇, M₂₅₇ は合成数である^[3]^[4]。

M₃₁ は1772年、レオンハルト・オイラーによって素数であると証明された^[3]^[5]。

M₁₂₇ は1876年、エドゥアール・リュカによって素数であると証明された^[3]^[6]。

M₆₁ が素数であることは、1883年にテンプレート:仮リンクによって示された^[3]。

M₆₇ が素数でないことは、1903年10月、フランク・ネルソン・コールにより示された。彼はニューヨークで開かれたアメリカ数学会で 193707721 × 761838257287 を黒板に計算し、M₆₇ と一致することを証明した。この間一言もしゃべらず、席に戻った後、少し間を置いて拍手が沸き起こったと伝えられている^[7]。

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

数学的性質

M_n が素数ならば n は素数であるが、n が素数であっても M_n は素数とは限らない。前者の対偶である命題「n が合成数ならば M_n は合成数である」は次の式から示される^[3]^[8]。

2^ab − 1 = (2^a − 1){1 + 2^a + 2^2a + ... + 2^(b−1)a}

素因数

p が素数の時、M_p の素因数は 2p を法として 1 と合同^[9]、かつ 8 を法として 1 または −1 と合同である^[10]。また、p が 4 を法として 3 と合同なとき、M_p が 2p + 1 で割れることと、2p + 1 が素数であることは同値である^[10]。また、M_p の最大の素因数 q は q ≧ c₅ p log p（c₅ は計算可能な定数）を満足する（Erdős-Shoreyの定理1）^[11]。

完全数

M_p = 2^p − 1 が素数であるならば、2^p−1(2^p − 1) は完全数となる^[3]^[12]。この定理はすでに紀元前4世紀のエウクレイデス（ユークリッド）によって証明されていた^[13]。およそ二千年の後に、全ての偶数の完全数はこの形の時に限るということが18世紀のレオンハルト・オイラーにより証明された^[12]。

メルセンヌ素数

2024年4月現在、メルセンヌ素数は48個まで知られている。ただし、メルセンヌ素数としての番号が確定しているものは、43番目までであり、

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

における M_p がそうである。さらに44番目の候補として p = 32,582,657 が挙がっており、現在間に素数がないかどうか検証中である。

分散コンピューティングによるプロジェクト GIMPS はメルセンヌ素数を発見することを目的としており、近年発見されたものは全てこのプロジェクトによるものである。

2004年 5月15日、GIMPS は41番目の素数候補が発見されたことを発表した。検証後723万5733桁の数、2^24036583 − 1 が素数であることが確認された。
2005年 2月27日、GIMPS は42番目の素数候補がドイツの眼科医によって発見されたことを報告した。781万6230桁の数、2^25964951 − 1 であり、[1]に掲載されている。
2005年12月15日、GIMPS は43番目の素数候補が米国のセントラル・ミズーリ州立大学（現テンプレート:仮リンク）の教授2名によって発見されたと報じた。2^30402457 − 1、915万2052桁 [2]。
2006年9月4日、GIMPS は44番目の素数候補が、43番目の素数候補を発見したのと同じ教授2名によって発見されたと報じた。2^32582657 − 1、980万8358 桁[3]。
2008年8月23日、GIMPS は46番目の素数候補が、カリフォルニア大学ロサンゼルス校の数学部のコンピュータによって発見されたと報じた。2^43112609 − 1、1297万8189 桁（十進法で表記すると 2^43112609 − 1 ≒ 3.1647 × 10^12978188）[4]。発見順では45番目だが、次に発見されたメルセンヌ素数と発見時期が近かったため、46番目の候補として45番目の候補と同時に発表された。この素数は電子フロンティア財団が賞金をかけた1000万桁以上の最初の素数となるため、GIMPS によって同校数学部に50,000ドル、慈善事業に25,000ドル、残りを前の6つのメルセンヌ素数の発見者へ分配することになった。
2008年9月6日、GIMPS は45番目の素数候補が、ドイツで発見されたと報じた。2^37156667 − 1、1118万5272 桁[5]。これは、GIMPS によって発見された中では、発見順序と桁数が逆転した初めてのケースである。

素数判定法

メルセンヌ数が素数かどうかを調べるための判定法としてリュカ・テスト (Lucas test) とリュカ-レーマー・テスト (Lucas-Lehmer primality test) がある。

リュカ・テスト

p が (4j + 3) 型の素数のとき、S₀ = 3, S_n = S_n−1² − 2 (n ≧ 1) と定義すると、

<math>M_p \not | S_k \ \ (0 \leqq k \leqq p-2)</math> ならば、M_p は合成数である。

<math>M_p \mid S_{p-2}</math> ならば、M_p は素数である^[14]^[15]^[16]。

証明はリュカ・テストの証明を参照。

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

デリック・ヘンリー・レーマー (en) は、エドゥアール・リュカの判定法を改良し、今日ではリュカ-レーマー・テスト (Lucas-Lehmer primality test) と呼ばれる、メルセンヌ数に対する素数判定法を確立した。

p が奇素数のとき、M_p が素数となるための必要十分条件は、S₀ = 4, S_n = S_n−1² − 2 (n ≧ 1) と定義したときに S_p−2 が M_p で割り切れることである^[17]^[18]^[19]。

リュカ-レーマー・テストは二進法を用いたコンピュータの処理に向いており、コンピュータによるメルセンヌ素数の発見には、この判定法が用いられてきた。例えば、2^p ≡ 1 (mod M_p) より、A・2^p + B ≡ A + B (mod M_p) が成り立つので、M_p で割る割り算の代わりに、二進法で p 桁のシフト演算と足し算だけで計算できる。現在「最大の」素数がメルセンヌ素数である理由はこの判定法にあると言える。

証明はリュカ-レーマー・テストの証明を参照。

発見されているメルセンヌ素数の表

テンプレート:OEIS

#	p	M_p	M_p の桁数	発見日	発見者
1	2	3	1	紀元前5世紀^[20]	古代ギリシャの数学者
2	3	7	1	紀元前5世紀^[20]	古代ギリシャの数学者
3	5	31	2	紀元前3世紀^[20]	古代ギリシャの数学者
4	7	127	3	紀元前3世紀^[20]	古代ギリシャの数学者
5	13	8191	4	1456年	不明^[21]
6	17	131071	6	1588年	テンプレート:仮リンク
7	19	524287	6	1588年	ピエトロ・カタルディ
8	31	2147483647	10	1772年	レオンハルト・オイラー
9	61	2305843009213693951	19	1883年	テンプレート:仮リンク
10	89	618970019…449562111	27	1911年	テンプレート:仮リンク
11	107	162259276…010288127	33	1914年	R・E・パワーズ^[22]
12	127	170141183…884105727	39	1876年	エドゥアール・リュカ
13	521	686479766…115057151	157	1952年1月30日	テンプレート:仮リンク, 使用:SWAC
14	607	531137992…031728127	183	1952年1月30日	ラファエル・M・ロビンソン
15	1,279	104079321…168729087	386	1952年6月25日	ラファエル・M・ロビンソン
16	2,203	147597991…697771007	664	1952年10月7日	ラファエル・M・ロビンソン
17	2,281	446087557…132836351	687	1952年10月9日	ラファエル・M・ロビンソン
18	3,217	259117086…909315071	969	1957年9月8日	ハンス・リーゼル, 使用:BESK
19	4,253	190797007…350484991	1,281	1961年11月3日	アレクサンダー・フルウィッツ, 使用:IBM 7090
20	4,423	285542542…608580607	1,332	1961年11月3日	アレクサンダー・フルウィッツ
21	9,689	478220278…225754111	2,917	1963年5月11日	ドナルド・ギリース, 使用:ILLIAC II
22	9,941	346088282…789463551	2,993	1963年5月16日	ドナルド・ギリース
23	11,213	281411201…696392191	3,376	1963年6月2日	ドナルド・ギリース
24	19,937	431542479…968041471	6,002	1971年3月4日	テンプレート:仮リンク, 使用:IBM 360/91
25	21,701	448679166…511882751	6,533	1978年10月30日	テンプレート:仮リンク & ローラ・ニッケル, 使用:CDC Cyber 174
26	23,209	402874115…779264511	6,987	1979年2月9日	ランドン・カート・ノル
27	44,497	854509824…011228671	13,395	1979年4月8日	ハリー・ネルソン & テンプレート:仮リンク
28	86,243	536927995…433438207	25,962	1982年9月25日	デイヴィッド・スローウィンスキー
29	110,503	521928313…465515007	33,265	1988年1月28日	ウォルター・コルキット & ルーク・ウェルシュ
30	132,049	512740276…730061311	39,751	1983年9月19日^[20]	デイヴィッド・スローウィンスキー
31	216,091	746093103…815528447	65,050	1985年9月1日^[20]	デイヴィッド・スローウィンスキー
32	756,839	174135906…544677887	227,832	1992年2月19日	デイヴィッド・スローウィンスキー & テンプレート:仮リンク使用:Harwell Lab Cray-2^[23]
33	859,433	129498125…500142591	258,716	1994年1月4日^[24]	デイヴィッド・スローウィンスキー & ポール・ゲイジ
34	1,257,787	412245773…089366527	378,632	1996年9月3日	デイヴィッド・スローウィンスキー & ポール・ゲイジ^[25]
35	1,398,269	814717564…451315711	420,921	1996年11月13日	GIMPS / Joel Armengaud^[26]
36	2,976,221	623340076…729201151	895,932	1997年8月24日	GIMPS / Gordon Spence^[27]
37	3,021,377	127411683…024694271	909,526	1998年1月27日	GIMPS / Roland Clarkson^[28]
38	6,972,593	437075744…924193791	2,098,960	1999年6月1日	GIMPS / Nayan Hajratwala^[29]
39	13,466,917	924947738…256259071	4,053,946	2001年11月14日	GIMPS / Michael Cameron^[30]
40	20,996,011	125976895…855682047	6,320,430	2003年11月17日	GIMPS / Michael Shafer^[31]
41	24,036,583	299410429…733969407	7,235,733	2004年5月15日	GIMPS / Josh Findley^[32]
42	25,964,951	122164630…577077247	7,816,230	2005年2月18日	GIMPS / Martin Nowak^[33]
43	30,402,457	315416475…652943871	9,152,052	2005年12月15日	GIMPS / テンプレート:仮リンク & Steven Boone^[34]
44テンプレート:Ref label	32,582,657	124575026…053967871	9,808,358	2006年9月4日	GIMPS / カーティス・クーパー & Steven Boone^[35]
45テンプレート:Ref label	37,156,667	202254406…308220927	11,185,272	2008年9月6日	GIMPS / Hans-Michael Elvenich^[36]
46テンプレート:Ref label	42,643,801	169873516…562314751	12,837,064	2009年4月12日	GIMPS / Odd Magnar Strindmo
47テンプレート:Ref label	43,112,609	316470269…697152511	12,978,189	2008年8月23日	GIMPS / エドソン・スミス^[36]
48テンプレート:Ref label	57,885,161	581887266…724285951	17,425,170	2013年1月25日	GIMPS / カーティス・クーパー^[37]^[38]

テンプレート:Note label44-48番目は未確定の順番。過去には29番目のメルセンヌ素数は30, 31番目が発見された後に発見されている。また47番目の後に45, 46番目が発見されている。

未解決問題

メルセンヌ素数は無限に存在するか？
素数 p に対して M_p が合成数であるとき、これをメルセンヌ合成数と呼ぶことにして、それは無限に存在するか？
平方因子を持つメルセンヌ数 M_p（p は素数）が存在するか？
n を奇数とするとき、次の3つの条件のうち2つが満足されれば、残りの1つも満足されると予想されており、n < 100000 に対してこの予想は正しいと確認されている^[39]。