梅森素数

梅森数是指形如$2^{n}-1$的数，记为$M_{n}$；如果一个梅森数是素数那么它称为梅森素数。

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

当n为合数时，$M_{n}$一定为合数。但当n为素数时，$M_{n}$不一定皆為素数，比如$M_{2}=2^{2}-1=3$和$M_{3}=2^{3}-1=7$是素数，但$M_{11}=2^{11}-1=2047=23\times 89$卻不是素数。

截至2016年1月，已知的梅森素数共有49个。已知最大的梅森素数是$2^{74207281}-1$。从1997年至今，所有新的梅森素数都是由互联网梅森素数大搜索（GIMPS）分布式计算项目发现的。

相关命题和定理

梅森数和梅森素数的性质

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

• q ≡ 3 mod 4为素数。则 2q+1是素数 的充分必要条件是 2q+1整除M_q 。

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

• 如果p是奇素数，那么任何能整除2^p − 1的素数q都一定是1加上一个2p的倍数。例如，2¹¹ − 1 = 23×89，而23 = 1 + 2×11，89 = 1 + 8×11。

• 如果p是奇素数，那么任何能整除$2^{p}-1$的素数q都一定与$\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
  • 欧拉的一个关于形如1+6k的数的理论表明：M_q是素数当且仅当存在数对（x,y）使得M_q = (2x)² + 3(3y)²，其中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世纪，欧几里得（Euclid）证明如果M是梅森素数，那么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₅₂₁的证明，它是在莱默指导下，使用R.M. Robinson教授编写的软件，利用坐落在洛杉矶加利福尼亚大学的数据分析协会的，属于美国国家标准局的西部自动计算机（SWAC）于1952年1月30日晚上10:00获得。并且在随后不到两小时，下一个梅森素数M₆₀₇被发现。在随后的几个月裡，使用同样的程序发现了另外三个梅森素数M₁₂₇₉、M₂₂₀₃和M₂₂₈₁。
• 到2016年1月，我们知道了49个梅森素数；现在已知最大的素数是梅森素数M_74,207,281。像前几个一样，都是由因特网梅森素数大搜索（GIMPS）分布式计算项目发现的。
• 2010年7月11日GIMPS项目確認M_20,996,011是第40個梅森素数。
• 2011年12月1日GIMPS项目确认M_24,036,583是第41个梅森素数。
• 2012年12月20日GIMPS项目确认M_25,964,951是第42个梅森素数。
• 2013年1月25日GIMPS项目发现M_57,885,161
• 2014年2月23日GIMPS项目确认M_30,402,457是第43个梅森素数。
• 2014年11月8日GIMPS项目确认M_32,582,657是第44个梅森素数。
• 2016年1月7日GIMPS項目發現M_74,207,281

梅森素数列表

下面表中列出了所有已知的梅森素数： 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年	Pietro Cataldi	试除法
7	19	524287	6	1588年	Pietro Cataldi	试除法
8	31	2147483647	10	1772年	莱昂哈德·欧拉	优化的试除法
9	61	2305843009213693951	19	1883年	Ivan Mikheevich Pervushin	卢卡斯数列
10	89	618970019642690137449562111	27	1911年	Ralph Ernest Powers	卢卡斯数列
11	107	162259276829213363391578010288127	33	1914年	Ralph Ernest Powers	卢卡斯数列
12	127	170141183460469231731687303715884105727	39	1876年	爱德华·卢卡斯	卢卡斯数列
13	521	686479766013…291115057151	157	1952年1月30日	Raphael M. Robinson	卢卡斯-莱默检验法
14	607	531137992816…219031728127	183	1952年1月30日	Raphael M. Robinson	卢卡斯-莱默检验法
15	1,279	104079321946…703168729087	386	1952年6月25日	Raphael M. Robinson	卢卡斯-莱默检验法
16	2,203	147597991521…686697771007	664	1952年10月7日	Raphael M. Robinson	卢卡斯-莱默检验法
17	2,281	446087557183…418132836351	687	1952年10月9日	Raphael M. Robinson	卢卡斯-莱默检验法
18	3,217	259117086013…362909315071	969	1957年9月8日	Hans Riesel	卢卡斯-莱默检验法
19	4,253	190797007524…815350484991	1,281	1961年11月3日	Alexander Hurwitz	卢卡斯-莱默检验法
20	4,423	285542542228…902608580607	1,332	1961年11月3日	Alexander Hurwitz	卢卡斯-莱默检验法
21	9,689	478220278805…826225754111	2,917	1963年5月11日	Donald B. Gillies	卢卡斯-莱默检验法
22	9,941	346088282490…883789463551	2,993	1963年5月16日	Donald B. Gillies	卢卡斯-莱默检验法
23	11,213	281411201369…087696392191	3,376	1963年6月2日	Donald B. Gillies	卢卡斯-莱默检验法
24	19,937	431542479738…030968041471	6,002	1971年3月4日	布萊恩特·塔克曼	卢卡斯-莱默检验法
25	21,701	448679166119…353511882751	6,533	1978年10月30日	Landon Curt Noll & Laura Nickel	卢卡斯-莱默检验法
26	23,209	402874115778…523779264511	6,987	1979年2月9日	Landon Curt Noll	卢卡斯-莱默检验法
27	44,497	854509824303…961011228671	13,395	1979年4月8日	Harry Nelson & David Slowinski	卢卡斯-莱默检验法
28	86,243	536927995502…209433438207	25,962	1982年9月25日	David Slowinski	卢卡斯-莱默检验法
29	110,503	521928313341…083465515007	33,265	1988年1月28日	Walt Colquitt & Luke Welsh	卢卡斯-莱默检验法
30	132,049	512740276269…455730061311	39,751	1983年9月20日	David Slowinski	卢卡斯-莱默检验法
31	216,091	746093103064…103815528447	65,050	1985年9月6日	David Slowinski	卢卡斯-莱默检验法
32	756,839	174135906820…328544677887	227,832	1992年2月19日	David Slowinski & Paul Gage	卢卡斯-莱默检验法
33	859,433	129498125604…243500142591	258,716	1994年1月10日	David Slowinski & Paul Gage	卢卡斯-莱默检验法
34	1,257,787	412245773621…976089366527	378,632	1996年9月3日	David Slowinski & Paul Gage	卢卡斯-莱默检验法
35	1,398,269	814717564412…868451315711	420,921	1996年11月13日	GIMPS／Joel Armengaud	卢卡斯-莱默检验法
36	2,976,221	623340076248…743729201151	895,932	1997年8月24日	GIMPS／Gordon Spence	卢卡斯-莱默检验法
37	3,021,377	127411683030…973024694271	909,526	1998年1月27日	GIMPS／Roland Clarkson	卢卡斯-莱默检验法
38	6,972,593	437075744127…142924193791	2,098,960	1999年6月1日	GIMPS／Nayan Hajratwala	卢卡斯-莱默检验法
39	13,466,917	924947738006…470256259071	4,053,946	2001年11月14日	GIMPS／Michael Cameron	卢卡斯-莱默检验法
40	20,996,011	125976895450…762855682047	6,320,430	2003年11月17日	GIMPS／Michael Shafer	卢卡斯-莱默检验法
41	24,036,583	299410429404…882733969407	7,235,733	2004年5月15日	GIMPS／Josh Findley	卢卡斯-莱默检验法
42	25,964,951	122164630061…280577077247	7,816,230	2005年2月18日	GIMPS／Martin Nowak	卢卡斯-莱默检验法
43	30,402,457	315416475618…411652943871	9,152,052	2005年12月15日	GIMPS／Curtis Cooper及Steven Boone	卢卡斯-莱默检验法
44	32,582,657	124575026015…154053967871	9,808,358	2006年9月4日	GIMPS／Curtis Cooper及Steven Boone	卢卡斯-莱默检验法
45*	37,156,667	202254406890…022308220927	11,185,272	2008年9月6日	GIMPS／Hans-Michael Elvenich	卢卡斯-莱默检验法
46*	42,643,801	169873516452…765562314751	12,837,064	2009年4月12日	GIMPS／Odd M. Strindmo	卢卡斯-莱默检验法
47*	43,112,609	316470269330…166697152511	12,978,189	2008年8月23日	GIMPS／Edson Smith	卢卡斯-莱默检验法
48*	57,885,161	581887266232…071724285951	17,425,170	2013年1月25日	GIMPS／Curtis Cooper	卢卡斯-莱默检验法
49*	74,207,281	300376418084...391086436351	22,338,618	2015年9月17日	GIMPS／Curtis Cooper	卢卡斯-莱默检验法

注：现在还不知道在第44个梅森素数（M_32582657）和第49个（M_74207281）之间是否还存在未知梅森素数，所以在其序号之前用^*标出。

外部链接

• （英文）Great Internet Mersenne Prime Search GIMPS計劃
• （英文）Mersenne Primes: History, Theorems and Lists 梅森素数：历史，定理，以及梅森素数列表