メルセンヌ数

出典: フリー百科事典『ウィキペディア（Wikipedia）』

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

[編集] 歴史

1644年にマラン・メルセンヌは 2ⁿ -1 が素数になるのは、n ≤ 257 では、n = 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}+\cdots+2^{(b-1)a})=2^{ab}-1.$

q が素数の時、M_q の素因数は 2q を法として 1 と合同、かつ 8 を法として 1 または -1 と合同である。また、q が 4 を法として 3 と合同なとき、M_q が 2q + 1 で割れることと、2q + 1 が素数であることは同値である。また、M_q の最大の素因数 P は $P\ge Cq \log q$ （C は計算可能な定数）を満足することが知られている(Erdos and Shorey, On the greatest prime factor of $2 p - 1$ for a prime p, and other expressions, Acta Arith. 30(1976), 257-265)。

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

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

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, 13466917

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

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]

[編集] 素数判定法

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

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
39	13,466,917	4,053,946	2^13466916M_13466967	2001年	GIMPS
40(?)	20,996,011	6,320,430	2^20996010M_20996011	2003年	GIMPS
41(?)	24,036,583	7,235,733	2^24036582M_24,036,583	2004年	GIMPS
42(?)	25,964,951	7,816,230	2^25,964,950M_25,964,951	2005年	GIMPS
43(?)	30,402,457	9,152,052	2^30,402,456M_30,402,457	2005年	GIMPS
44(?)	32,582,657	9,808,358	2^32,582,656M_32,582,657	2006年	GIMPS

[編集] 未解決問題

メルセンヌ数で素数であるものが無限に存在するか否か、またメルセンヌ数で合成数であるものが無限に存在するか否かは未だに解決されていない。メルセンヌ数の性質から、4n+3と8n+7が共に無限回素数になるなら、メルセンヌ合成数が無限に多く存在することが導かれる。
メルセンヌ数が平方因子をもつかどうかは未だに解決されていない。
qを素数とするとき、次の3つの条件のうち2つが満足されれば、残りの一つも満足されると予想されている：

M_qが素数である
$q = 2 k + / - 1$ or $4 k + / - 3$
$(2 q + 1) / 3$ は素数である。

q < 100000に対してこの予想は正しいと確認されている。

[編集] 関連項目

メルセンヌ・ツイスタ（メルセンヌ素数を用いた擬似乱数発生アルゴリズム）
完全数
GIMPS

[編集] 外部リンク

Mersenne Primes: History, Theorems and Lists（英語）
The Largest Known Primes（英語）

"http://ja.wikipedia.org../../../%E3%83%A1/%E3%83%AB/%E3%82%BB/%E3%83%A1%E3%83%AB%E3%82%BB%E3%83%B3%E3%83%8C%E6%95%B0.html" より作成

カテゴリ: 数論 | 計算数論 | 整数の類 | 数学に関する記事