メルセンヌ数

n が素数のとき、M_n = 2ⁿ-1 の形をした自然数をメルセンヌ数という。
メルセンヌ数が素数であるとき、そのメルセンヌ数をメルセンヌ素数という。特にメルセンヌ素数に限りメルセンヌ数という場合もある。

Table of contents

1 歴史
 2 数学的性質
 3 素数判定法
 4 発見されているメルセンヌ素数と対応する完全数の表

歴史

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

数学的性質

n が素数でなければ M_n は素数とならないが、n が素数であっても M_n が素数になるとは限らない。前者は次の式から示される；

(2^a - 1)·(1 + 2^a + 2^2a + 2^3a +...+ 2^{(b - 1)a}) = 2^ab - 1.

M_n = 2ⁿ - 1 が素数であるならば、2^{n - 1}(2ⁿ - 1) は完全数となる。この事実はすでに紀元前4世紀のユークリッドによって知られていた。およそ二千年の後に、全ての偶数の完全数はこの形の時に限るという事が18世紀のオイラーにより証明された。

現在メルセンヌ素数は38番目まで知られていて、

n = 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

としたときの M_n がそうである。さらに39番目の候補として n = 13466917 が挙がっており、現在間に素数がないかどうか検証中である。<--fix me

2003年11月17日、GIMPSはさらに40番目の候補として20996011を挙げた。

素数判定法

メルセンヌ数が素数かどうかを調べるための判定法として、ルカステストがある。

M_n が素数となるための必要十分条件は、S₀ = 4, S_k = S_k-1² - 2 (k > 1) と定義したときに S_{n - 2} が M_n で割り切れることである。

発見されているメルセンヌ素数と対応する完全数の表

*M_p* = 2^p-1
No.	p	M_pの桁数	完全数 2^p-1M_p	年	発見者
1	2	1	6	ancient	-
2	3	1	28	ancient	-
3	5	2	496	ancient	-
4	7	3	8128	ancient	-
5	13	4	33550336	1456年	不明
6	17	6	2¹⁶M₁₇	1588年	カタルディ
7	19	6	2¹⁸M₁₉	1588年	カタルディ
8	31	10	2³⁰M₃₁	1772年	レオンハルト・オイラー
9	61	19	2⁶⁰M₆₁	1883年	ぺボジーネ
10	89	27	2⁸⁸M₈₉	1911年	パワーズ
11	107	33	2¹⁰⁶M₁₀₇	1914年	パワーズ
12	127	39	2¹²⁶M₁₂₇	1876年	リュカ
13	521	157	2⁵²⁰M₅₂₁	1952年	ロビンソン
14	607	183	2⁶⁰⁶M₆₀₇	1952年	ロビンソン
15	1,279	386	2¹²⁷⁸M₁₂₇₉	1952年	ロビンソン
16	2,203	664	2²²⁰²M₂₂₀₃	1952年	ロビンソン
17	2,281	687	2²²⁸⁰M₂₂₈₁	1952年	ロビンソン
18	3,217	969	2³²¹⁶M₃₂₁₇	1957年	ハンス・リーゼル
19	4,253	1,281	2⁴²⁵²M₄₂₅₃	1961年	アレクサンダー・フルウィッツ
20	4,423	1,332	2⁴⁴²²M₄₄₂₃	1961年	アレクサンダー・フルウィッツ
21	9,689	2,917	2⁹⁶⁸⁸M₉₆₈₉	1963年	ドナルド・ギリーズ
22	9,941	2,993	2⁹⁹⁴⁰M₉₉₄₁	1963年	ドナルド・ギリーズ
23	11,213	3,376	2¹¹²¹²M₁₁₂₁₃	1963年	ドナルド・ギリーズ
24	19,937	6,002	2¹⁹⁹³⁶M₁₉₉₃₇	1971年	ブライアント・タッカーマン
25	21,701	6,533	2²¹⁷⁰⁰M₂₁₇₀₁	1978年	クルト・ノル & ニッケル
26	23,209	6,987	2²³²⁰⁸M₂₃₂₀₉	1978年	クルト・ノル & ニッケル
27	44,497	13,395	2⁴⁴⁴⁹⁶M₄₄₄₉₇	1979年	ハリー・ネルソン & スローウィンスキー
28	86,243	25,962	2⁸⁶²⁴²M₈₆₂₄₃	1982年	スローウィンスキー
29	110,503	33,265	2¹¹⁰⁵⁰²M₁₁₀₅₀₃	1988年	コルキット & ウェルシュ
30	132,049	39,751	2¹³²⁰⁴⁸M₁₃₂₀₄₉	1983年	スロウィンスキー
31	216,091	65,050	2²¹⁶⁰⁹⁰M₂₁₆₀₉₁	1985年	スロウィンスキー
32	756,839	227,832	2⁷⁵⁶⁸³⁸M₇₅₆₈₃₉	1992年	スロウィンスキー & ゲイジ
33	859,433	258,716	2⁸⁵⁹⁴³²M₈₅₉₄₃₃	1994年	スロウィンスキー & ゲイジ
34	1,257,787	378,632	2^1257786M_1257787	1996年	スロウィンスキー & ゲイジ
35	1,398,269	420,921	2^1398268M_1398269	1996年	GIMPS
36	2,976,221	895,932	2^2976220M_2976221	1997年	GIMPS
37	3,021,377	909,526	2^3021376M_3021377	1998年	GIMPS
38	6,972,593	2,098,960	2^6972592M_6972593	1999年	GIMPS
?	13,466,917	4,053,946	2^13466916M_13466967	2001年	GIMPS
?	20,996,011	6,320,430	2^20996010M_20996011	2003年	GIMPS