梅森素数

梅森数是指形如的数,记为;如果一个梅森数是素数那么它称为梅森素数(英语:Mersenne prime)。

梅森数是根据17世纪法国数学家马兰·梅森Marin Mersenne)的名字命名的,他列出了n ≤ 257的梅森素数,不过他错误地包括了不是梅森素数的M67M257,而遗漏了M61M89M107

n合数时,一定为合数(因为当a整除b时,一定整除,反之亦然)。但当n为素数时,不一定皆为素数,比如是素数,但却不是素数。

截至2018年12月,已知的梅森素数共有51个。已知最大的梅森素数是[1]。从1997年至今,所有新的梅森素数都是由互联网梅森素数大搜索(GIMPS)分布式计算项目发现的。

相关命题和定理

梅森数和梅森素数的性质

  •  
  • q ≡ 3 mod 4为素数。则 2q+1是素数充分必要条件2q+1整除Mq ,因此对于这些素数q(除了3),Mq不可能会是素数,前几个这样的素数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):Mq = 6+x2。当q为3、5和7时,Mq为梅森素数,方程有整数解;q为合数4和15时,方程亦有整数解;q为其它自然数时,方程没有整数解。
  • 如果p是奇素数,那么任何能整除2p − 1的素数q都一定是1加上一个2p的倍数。例如,211 − 1 = 23×89,而23 = 1 + 2×11,89 = 1 + 8×11。
  • 如果p是奇素数,那么任何能整除 的素数q都一定与 同余。

梅森数和梅森素数的关系

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

  •  知:q素数Mq素数必要条件。但这不是充分的。M11 = 211 − 1 = 23 × 89是个反例
  • Mq(q是素数)有:
    • aMq的因数,则a有如下性质:
      • a ≡ 1 mod 2q
      • a ≡ ±1 mod 8
    • 欧拉的一个关于形如1+6k的数的理论表明:Mq是素数当且仅当存在数对(x,y)使得Mq = (2x)2 + 3(3y)2,其中q ≥ 5。
    • 最近,Bas jansen研究了等式Mq = x2 + dy2(0≤d≤48),得出了一个对于d=3情况下的新的证明方法。
    • Reix发现q > 3时,Mq可以写成:Mq = (8x)2 - (3qy)2 = (1+Sq)2 - (Dq)2。显然,若存在一个数对(x,y),那么Mq是素数。

梅森数的素数检验

Mn为素数当且仅当Mn整除Sn-2S0=4,Sk = S 2k − 1 − 2,k > 0),此数列为4, 14, 194, 37634, 1416317954, 2005956546822746114, 4023861667741036022825635656102100994, ... (OEIS数列A003010

与完全数的关系

  • 梅森素数与完全数有一一对应的关系。这个结果称为欧几里得-欧拉定理
    • 前4世纪,欧几里得(Euclid)证明如果M是梅森素数,那么 完全数
    • 18世纪,欧拉(Euler)证明所有的完全数都有这种形式。

相关问题和猜想

  • 是否有无穷多个梅森素数。
  • 梅森素数如何分布。

寻找梅森素数

  • 头四个梅森素数M2M3M5M7在古代就已经知道。
  • 第五个梅森素数M13在1461年之前被发现;
  • 随后的两个(M17M19)在1588年由Cataldi发现。
  • 17世纪法国数学家马兰·梅森列出了他认为的幂小于等于257的梅森素数,其中错误地包括了不是素数的M67M257,遗漏了M61M89M107。这也是“梅森素数”这个名字的由来。
  • 一个多世纪后的1750年,才由欧拉证实M31是第8个梅森素数。
  • 下一个被发现的梅森素数是由卢卡斯在1876年证明的M127
  • 1883年,Pervushin证实M61
  • M89M107是在20世纪早期由Powers分别在1911年和1914年发现的。
  • 电子计算机的发明革命化的改进了梅森素数的寻找。第一个成功的例子是M521的证明,它是在莱默指导下,使用拉斐尔·米切尔·罗宾逊教授编写的软件,利用坐落在洛杉矶加利福尼亚大学数据分析协会的,属于美国国家标准局的西部自动计算机(SWAC)于1952年1月30日晚上10:00获得。并且在随后不到两小时,下一个梅森素数M607被发现。在随后的几个月里,使用同样的程序发现了另外三个梅森素数M1279M2203M2281
  • 随着素数P值的增大,每一个梅森素数MP的产生都艰辛无比;而各国科学家及业余研究者们仍乐此不疲,激烈竞争。1979年2月23日,当美国克雷研究公司计算机专家史洛温斯基纳尔逊宣布他们找到第26个梅森素数M23209时,人们告诉他们:在两个星期前诺尔已得到这一结果。
  • 为此,史洛温斯基潜心发愤,花了一个半月的时间,使用CRAY-1型计算机找到了新的梅森素数M44497。这个记录成了当时不少美国报纸的头版新闻。
  • 之后,这位计算机专家乘胜前进,使用经过改进的CRAY-XMP型计算机在1983年至1985年间找到了3个梅森素数:M86243M132049M216091。但他未能确定M86243M216091之间是否有异于M132049的梅森素数。而到了1988年科尔魁特韦尔什使用NEC-FX2型超高速并行计算机果然捕捉到了一条“漏网之鱼”——M110503
  • 沉寂4年之后,1992年3月25日,英国原子能技术权威机构——哈威尔实验室的一个研究小组宣布他们找到了新的梅森素数M756839
  • 1994年1月14日,史洛温斯基盖奇为其公司再次夺回发现“已知最大素数”的桂冠——这一素数是M859433。而下一个梅森素数M1257787仍是他们的成果。这一素数是使用CRAY-794超级计算机1996年取得的。
  • 史洛温斯基由于发现7个梅森素数,而被人们誉为“素数大王”。
  • 到2018年12月,我们知道了51个梅森素数;现在已知最大的素数是梅森素数M82589933。像前几个一样,都是由因特网梅森素数大搜索(GIMPS)分布式计算项目发现的。
  • 2010年7月11日GIMPS项目确认M20,996,011是第40个梅森素数。[2]
  • 2011年12月1日GIMPS项目确认M24,036,583是第41个梅森素数。[2]
  • 2012年12月20日GIMPS项目确认M25,964,951是第42个梅森素数。[2]
  • 2013年1月25日GIMPS项目发现M57,885,161[2]
  • 2014年2月23日GIMPS项目确认M30,402,457是第43个梅森素数。[2]
  • 2014年11月8日GIMPS项目确认M32,582,657是第44个梅森素数。[2]
  • 2016年1月7日GIMPS项目发现M74,207,281[2]
  • 2018年1月3日GIMPS项目发现的M77232917,共有23249425位数[3]
  • 2018年12月7日GIMPS项目M82589933,共有24862048 位数[1]

梅森素数列表

  梅森遗漏的梅森素数

  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 1,279 104079321946…703168729087 386 1952年6月25日 拉斐尔·米切尔·罗宾逊 卢卡斯-莱默检验法
16 2,203 147597991521…686697771007 664 1952年10月7日 拉斐尔·米切尔·罗宾逊 卢卡斯-莱默检验法
17 2,281 446087557183…418132836351 687 1952年10月9日 拉斐尔·米切尔·罗宾逊 卢卡斯-莱默检验法
18 3,217 259117086013…362909315071 969 1957年9月8日 Hans Riesel 卢卡斯-莱默检验法
19 4,253 190797007524…815350484991 1,281 1961年11月3日 亚历山大·赫维兹 卢卡斯-莱默检验法
20 4,423 285542542228…902608580607 1,332 1961年11月3日 亚历山大·赫维兹 卢卡斯-莱默检验法
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日[注 1] 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日 GIMPSCurtis Cooper 卢卡斯-莱默检验法
49* 74,207,281 300376418084...391086436351 22,338,618 2015年9月17日[注 2] GIMPSCurtis Cooper 卢卡斯-莱默检验法
50* 77,232,917 467333183359...069762179071 23,249,425 2017年12月26日 GIMPS/Jon Pace 卢卡斯-莱默检验法
51* 82,589,933 148894445742...325217902591 24,862,048 2018年12月7日 GIMPS/Patrick Laroche 卢卡斯-莱默检验法

注:现在还不知道在第48个梅森素数(M57885161)和第51个(M82589933)之间是否还存在未知梅森素数,所以在其序号之前用*标出,如果存在,会通知递补。

  1. ^ 2009年4月12日首次有机器发现M42,643,801,但直到6月4日才有人注意到。因此,两者皆可视为发现日期。
  2. ^ 2015年9月17日首次有机器发现M74,207,281,但直到2016年1月7日才有人注意到。因此,两者皆可视为发现日期。GIMPS以后者为正式日期。

外部链接

参考

  1. ^ 1.0 1.1 Mersenne Prime Discovery - 2^82589933-1 is Prime!. www.mersenne.org. [2018-12-24]. (原始内容存档于2018-12-22). 
  2. ^ 2.0 2.1 2.2 2.3 2.4 2.5 2.6 GIMPS Milestones. [2012-03-03]. (原始内容存档于2016-09-03). 
  3. ^ GIMPS Project Discovers Largest Known Prime Number: 277,232,917-1. Mersenne Research, Inc. 2018年1月3日 [2018年1月14日]. (原始内容存档于2018年1月3日).