梅森素数

梅森数是形如2ⁿ－1的数（n是正整数），记为${\textstyle M_{n}}$；如果梅森数是素数就称梅森素数（英语：Mersenne prime）。

梅森预测表：n≤263

P : Mn是梅森素数 — : Mn是梅森合数 青色：显示正确 粉红色：显示错误
n	2	3	5	7	11	13	17	19
Mn	P	P	P	P	—	P	P	P
n	23	29	31	37	41	43	47	53
Mn	—	—	P	—	—	—	—	—
n	59	61	67	71	73	79	83	89
Mn	—	P	—	—	—	—	—	P
n	97	101	103	107	109	113	127	131
Mn	—	—	—	P	—	—	P	—
n	137	139	149	151	157	163	167	173
Mn	—	—	—	—	—	—	—	—
n	179	181	191	193	197	199	211	223
Mn	—	—	—	—	—	—	—	—
n	227	229	233	239	241	251	257	263
Mn	—	—	—	—	—	—	—	—

梅森数是根据17世纪法国数学家马兰·梅森的名字命名，他列出了n≤257的梅森素数，不过他错误包括了不是梅森素数的M₆₇和M₂₅₇，而遗漏了M₆₁、M₈₉和M₁₀₇。

n为合数时，${\textstyle M_{n}}$一定为合数（当a整除b时，${\textstyle M_{a}}$一定整除${\textstyle M_{b}}$，反之亦然）。但n为素数时，${\textstyle M_{n}}$不一定皆为素数，如${\textstyle M_{2}=2^{2}-1=3}$和${\textstyle M_{3}=2^{3}-1=7}$是素数，但${\textstyle M_{11}=2^{11}-1=2047=23\times 89}$不是素数。

截至2018年12月已知51个梅森素数，最大的是2^82589933－1。从1997年至今，所有新的梅森素数都由互联网梅森素数大搜索（GIMPS）分布式计算项目发现。

相关命题和定理

梅森数和梅森素数的性质

• $M_{n}=\sum _{i=0}^{n}{n \choose i}-1=\sum _{i=0}^{n-1}2^{i}$。

• q≡3mod4为素数。则2q＋1是素数的充分必要条件是2q＋1整除M_q ，因此对于这些素数q（除了3），M_q不可能会是质数，前几个这样的素数q为11、23、83、131、179、191、239、251、359、419、431、443、491、659、683、719、743、911、1019、1031、1103、1223、1439、1451、1499、… （OEIS数列A002515）

• 拉马努金－南哥尔方程（Ramanujan–Nagell Equation）：M_q＝6＋x²。当q为3、5和7时，M_q为梅森素数，方程有整数解；q为合数4和15时，方程亦有整数解；q为其它自然数时，方程没有整数解。

• 如果p是奇素数，任何能整除2^p − 1的素数q都一定是2p的倍数加1，如2¹¹ − 1＝23×89，而23＝1＋2×11，89＝1＋8×11。

• 如果p是奇素数，任何能整除2^p − 1的素数q都一定与${\textstyle \pm 1{\pmod {8}}}$同余。

梅森数和梅森素数的关系

下面的命题关注什么梅森数是梅森素数。

• 由$2^{ab}-1=(2^{a}-1)\times \sum _{i=0}^{b-1}2^{ia}$知：“q是素数”是“M_q是素数”的必要条件，但不是充分条件。M₁₁＝2¹¹ − 1＝23×89是最小的反例。
• 对M_q（q是素数）有：
  • 若a是M_q的因数，则a有如下性质：
    • a ≡ 1 mod 2q
    • a ≡ ±1 mod 8
  • 形如6k＋1的数有欧拉理论表明：当且仅当有数对（x，y）使M_q＝（2x）²＋3（3y）²，M_q是素数，其中q≥5。
  • 最近，Bas jansen研究了等式M_q＝x²＋dy²（0≤d≤48），得出了d＝3时的新证明方法。
  • Reix发现q＞3时，M_q可写成M_q＝（8x）²－（3qy）²＝（1＋Sq）²－（Dq）²；显然，若有数对（x，y），M_q就是素数。

检验梅森素数

• 卢卡斯－莱默检验法是现在已知的检测梅森数素数的最好的方法。
  • 该方法由爱德华·卢卡斯于1878年发现，并由德里克·亨利·莱默于1930年代改进，因此得名。
  • 该方法基于循环数列的计算，其原理是：

M_n为素数当且仅当M_n整除S_n-2（S₀＝4，S_k＝S²_k−1 − 2，k＞0），此数列为4、14、194、37634、1416317954、2005956546822746114、4023861667741036022825635656102100994、…（OEIS数列A003010）

与完全数的关系

• 梅森素数与偶完全数有一一对应的关系，称为欧几里得－欧拉定理。
  • 前4世纪，欧几里得（Euclid）证明如果M是梅森素数，则${\textstyle {\frac {M(M+1)}{2}}}$是完全数。
  • 18世纪，欧拉（Euler）证明所有偶完全数都有这种形式。

相关问题和猜想

• 梅森素数是否有无限个
• 梅森素数如何分布

寻找梅森素数

• 头四个梅森素数M₂、M₃、M₅、M₇在古代已知。
• 第五个梅森素数M₁₃在1461年之前发现；
• M₁₇和M₁₉两数随后在1588年由Cataldi发现。
• 17世纪法国数学家马兰·梅森列出了他认为的幂小于等于257的梅森素数，其中错误包括了不是素数的M₆₇和M₂₅₇，遗漏了M₆₁、M₈₉和M₁₀₇。这也是“梅森素数”一名的由来。
• 一个多世纪后的1750年，才由欧拉证实M₃₁是第8个梅森素数。
• 下个发现的梅森素数是由卢卡斯在1876年证明的M₁₂₇；
• 1883年，Pervushin证实M₆₁。
• M₈₉和M₁₀₇在20世纪早期由Powers分别在1911年和1914年发现。
• 发明电子计算机改革了梅森素数的寻找过程。第一项成功例子是证明M₅₂₁，它由莱默指导，用拉斐尔·米切尔·罗宾逊教授编写的软件，利用坐落在洛杉矶加利福尼亚大学的数据分析协会的，属于美国国家标准局的西部自动计算机（SWAC）于1952年1月30日晚上10:00获得，并且在随后不到两小时发现下个梅森素数M₆₀₇。在随后的几个月里，使用同样的程序发现了另外三个梅森素数M₁₂₇₉、M₂₂₀₃和M₂₂₈₁。
• 素数P值增大，搜寻梅森素数MP的过程都艰辛无比，但各国科学家及业馀研究者仍乐此不疲，激烈竞争；1979年2月23日，当美国克雷研究公司的计算机专家史洛温斯基和纳尔逊宣布找到第26个梅森素数M₂₃₂₀₉时才知诺尔在两星期前已得到这结果。
• 为此，史洛温斯基潜心发愤，花了一个半月用CRAY－1型计算机找到新梅森素数M₄₄₄₉₇，这纪录成了当时不少美国报纸的头版新闻。

• 他之后乘胜前进，使用改进了的CRAY－XMP型计算机在1983年至1985年间找到3个梅森素数M₈₆₂₄₃、M₁₃₂₀₄₉和M₂₁₆₀₉₁，但未能确定M₈₆₂₄₃和M₂₁₆₀₉₁之间是否有异于M₁₃₂₀₄₉的梅森素数。而到了1988年，科尔魁特和韦尔什使用NEC－FX2型超高速并行计算机果然捉到“漏网之鱼”M₁₁₀₅₀₃。

• 沉寂4年后，1992年3月25日，英国原子能技术权威机构哈威尔实验室有研究小组宣布找到梅森素数M₇₅₆₈₃₉。

• 1994年1月14日，史洛温斯基和盖奇为其公司再次夺回发现“已知最大质数”的桂冠——M₈₅₉₄₃₃；而下个梅森素数M_1257787仍是他们的成果，用CRAY－794超级计算机在1996年找到。

• 史洛温斯基发现7个梅森素数，获美誉“素数大王”。

• 到2018年12月已知51个梅森素数；现在已知最大的素数是梅森素数M_82589933，像前几个一样都是由因特网梅森素数大搜索（GIMPS）分布式计算项目发现。
• 2010年7月11日GIMPS确认M_2099万6011是第40个梅森素数。
• 2011年12月1日GIMPS确认M_2403万6583是第41个梅森素数。
• 2012年12月20日GIMPS确认M_2596万4951是第42个梅森素数。
• 2013年1月25日GIMPS发现M_5788万5161
• 2014年2月23日GIMPS确认M_3040万2457是第43个梅森素数。
• 2014年11月8日GIMPS确认M_3258万2657是第44个梅森素数。
• 2016年1月7日GIMPS发现M_7420万7281
• 2018年1月3日GIMPS发现的M_7723万2917有23249425位数。
• 2018年12月7日GIMPS的M_8258万9933有24862048位数。

梅森素数列表

  古代知道的梅森素数

  以试除法发现的梅森素数

  梅森遗漏的梅森素数

  GIMPS发现的梅森素数

  拉斐尔·米切尔·罗宾逊发现的梅森质数

  亚历山大·赫维兹发现的梅森质数

  Donald B. Gillies发现的梅森质数

  Walt Colquitt和Luke Welsh发现的梅森质数

下表列出所有已知的梅森素数： A000668

序	n	Mn	Mn的位数	发现日期	发现者	算法
1	2	3	1	公元前5世纪	古希腊数学家
2	3	7	1	公元前5世纪	古希腊数学家
3	5	31	2	公元前3世纪	古希腊数学家
4	7	127	3	公元前3世纪	古希腊数学家
5	13	8191	4	1456年	无名氏	试除法
6	17	131071	6	1588年	彼得罗·卡塔尔迪	试除法
7	19	524287	6	1588年	彼得罗·卡塔尔迪	试除法
8	31	2147483647	10	1772年	莱昂哈德·欧拉	优化的试除法
9	61	2305843009213693951	19	1883年	伊万·波佛辛	卢卡斯数列
10	89	618970019642690137449562111	27	1911年	拉尔夫·欧内斯特·鲍尔斯	卢卡斯数列
11	107	162259276829213363391578010288127	33	1914年	拉尔夫·欧内斯特·鲍尔斯	卢卡斯数列
12	127	170141183460469231731687303715884105727	39	1876年	爱德华·卢卡斯	卢卡斯数列
13	521	686479766013…291115057151	157	1952年1月30日	拉斐尔·米切尔·罗宾逊	卢卡斯－莱默检验法
14	607	531137992816…219031728127	183	1952年1月30日	拉斐尔·米切尔·罗宾逊	卢卡斯－莱默检验法
15	1279	104079321946…703168729087	386	1952年6月25日	拉斐尔·米切尔·罗宾逊	卢卡斯－莱默检验法
16	2203	147597991521…686697771007	664	1952年10月7日	拉斐尔·米切尔·罗宾逊	卢卡斯－莱默检验法
17	2281	446087557183…418132836351	687	1952年10月9日	拉斐尔·米切尔·罗宾逊	卢卡斯－莱默检验法
18	3217	259117086013…362909315071	969	1957年9月8日	Hans Riesel	卢卡斯－莱默检验法
19	4253	190797007524…815350484991	1281	1961年11月3日	亚历山大·赫维兹	卢卡斯－莱默检验法
20	4423	285542542228…902608580607	1332	1961年11月3日	亚历山大·赫维兹	卢卡斯－莱默检验法
21	9689	478220278805…826225754111	2917	1963年5月11日	Donald B. Gillies	卢卡斯－莱默检验法
22	9941	346088282490…883789463551	2993	1963年5月16日	Donald B. Gillies	卢卡斯－莱默检验法
23	1万1213	281411201369…087696392191	3376	1963年6月2日	Donald B. Gillies	卢卡斯－莱默检验法
24	1万9937	431542479738…030968041471	6002	1971年3月4日	布莱恩特·塔克曼	卢卡斯－莱默检验法
25	2万1701	448679166119…353511882751	6533	1978年10月30日	Landon Curt Noll & Laura Nickel	卢卡斯－莱默检验法
26	2万3209	402874115778…523779264511	6987	1979年2月9日	Landon Curt Noll	卢卡斯－莱默检验法
27	4万4497	854509824303…961011228671	1万3395	1979年4月8日	Harry Nelson & David Slowinski	卢卡斯－莱默检验法
28	8万6243	536927995502…209433438207	2万5962	1982年9月25日	David Slowinski	卢卡斯－莱默检验法
29	11万0503	521928313341…083465515007	3万3265	1988年1月28日	Walt Colquitt & Luke Welsh	卢卡斯－莱默检验法
30	13万2049	512740276269…455730061311	3万9751	1983年9月20日	David Slowinski	卢卡斯－莱默检验法
31	21万6091	746093103064…103815528447	6万5050	1985年9月6日	David Slowinski	卢卡斯－莱默检验法
32	75万6839	174135906820…328544677887	22万7832	1992年2月19日	David Slowinski & Paul Gage	卢卡斯－莱默检验法
33	85万9433	129498125604…243500142591	25万8716	1994年1月10日	David Slowinski & Paul Gage	卢卡斯－莱默检验法
34	125万7787	412245773621…976089366527	37万8632	1996年9月3日	David Slowinski & Paul Gage	卢卡斯－莱默检验法
35	139万8269	814717564412…868451315711	42万0921	1996年11月13日	GIMPS／Joel Armengaud	卢卡斯－莱默检验法
36	297万6221	623340076248…743729201151	89万5932	1997年8月24日	GIMPS／Gordon Spence	卢卡斯－莱默检验法
37	302万1377	127411683030…973024694271	90万9526	1998年1月27日	GIMPS／Roland Clarkson	卢卡斯－莱默检验法
38	697万2593	437075744127…142924193791	209万8960	1999年6月1日	GIMPS／Nayan Hajratwala	卢卡斯－莱默检验法
39	1346万6917	924947738006…470256259071	405万3946	2001年11月14日	GIMPS／Michael Cameron	卢卡斯－莱默检验法
40	2099万6011	125976895450…762855682047	632万0430	2003年11月17日	GIMPS／Michael Shafer	卢卡斯－莱默检验法
41	2403万6583	299410429404…882733969407	723万5733	2004年5月15日	GIMPS／Josh Findley	卢卡斯－莱默检验法
42	2596万4951	122164630061…280577077247	781万6230	2005年2月18日	GIMPS／Martin Nowak	卢卡斯－莱默检验法
43	3040万2457	315416475618…411652943871	915万2052	2005年12月15日	GIMPS／Curtis Cooper及Steven Boone	卢卡斯－莱默检验法
44	3258万2657	124575026015…154053967871	980万8358	2006年9月4日	GIMPS／Curtis Cooper及Steven Boone	卢卡斯－莱默检验法
45	3715万6667	202254406890…022308220927	1118万5272	2008年9月6日	GIMPS／Hans-Michael Elvenich	卢卡斯－莱默检验法
46	4264万3801	169873516452…765562314751	1283万7064	2009年4月12日	GIMPS／Odd M. Strindmo	卢卡斯－莱默检验法
47	4311万2609	316470269330…166697152511	1297万8189	2008年8月23日	GIMPS／Edson Smith	卢卡斯－莱默检验法
48	5788万5161	581887266232…071724285951	1742万5170	2013年1月25日	GIMPS／Curtis Cooper	卢卡斯－莱默检验法
49*	7420万7281	300376418084…391086436351	2233万8618	2015年9月17日	GIMPS／Curtis Cooper	卢卡斯－莱默检验法
50*	7723万2917	467333183359…069762179071	2324万9425	2017年12月26日	GIMPS／Jon Pace	卢卡斯－莱默检验法
51*	8258万9933	148894445742…325217902591	2486万2048	2018年12月7日	GIMPS／Patrick Laroche	卢卡斯－莱默检验法

注：现在还不知道第48个梅森素数（M_57885161）和第51个（M_82589933）间是否还有未知梅森素数，其序号用^*标出，如有会通知递补。

外部链接

• （英文）Great Internet Mersenne Prime Search （页面存档备份，存于互联网档案馆） GIMPS计划
• （英文）Mersenne Primes: History, Theorems and Lists （页面存档备份，存于互联网档案馆） 梅森素数：历史，定理，以及梅森素数列表