梅森素数
此条目需要补充更多来源。 (2013年3月17日) |
梅森数是形如2n-1的数(n是正整数),记为;如果梅森数是素数就称梅森素数(英语:Mersenne prime)。
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的梅森素数,不过他错误包括了不是梅森素数的M67和M257,而遗漏了M61、M89和M107。
n为合数时,一定为合数(当a整除b时,一定整除,反之亦然)。但n为素数时,不一定皆为素数,如和是素数,但不是素数。
截至2018年12月已知51个梅森素数,最大的是282589933-1[1]。从1997年至今,所有新的梅森素数都由互联网梅森素数大搜索(GIMPS)分布式计算项目发现。
相关命题和定理
编辑梅森数和梅森素数的性质
编辑- 。
- q≡3mod4为素数。则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都一定是2p的倍数加1,如211 − 1=23×89,而23=1+2×11,89=1+8×11。
- 如果p是奇素数,任何能整除2p − 1的素数q都一定与 同余。
梅森数和梅森素数的关系
编辑下面的命题关注什么梅森数是梅森素数。
- 由 知:“q是素数”是“Mq是素数”的必要条件,但不是充分条件。M11=211 − 1=23×89是最小的反例。
- 对Mq(q是素数)有:
- 若a是Mq的因数,则a有如下性质:
- a ≡ 1 mod 2q
- a ≡ ±1 mod 8
- 形如6k+1的数有欧拉理论表明:当且仅当有数对(x,y)使Mq=(2x)2+3(3y)2,Mq是素数,其中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就是素数。
- 若a是Mq的因数,则a有如下性质:
检验梅森素数
编辑- Mn为素数当且仅当Mn整除Sn-2(S0=4,Sk=S2k−1 − 2,k>0),此数列为4、14、194、37634、1416317954、2005956546822746114、4023861667741036022825635656102100994、…(OEIS数列A003010)
与完全数的关系
编辑相关问题和猜想
编辑- 梅森素数是否有无限个
- 梅森素数如何分布
寻找梅森素数
编辑- 头四个梅森素数M2、M3、M5、M7在古代已知。
- 第五个梅森素数M13在1461年之前发现;
- M17和M19两数随后在1588年由Cataldi发现。
- 17世纪法国数学家马兰·梅森列出了他认为的幂小于等于257的梅森素数,其中错误包括了不是素数的M67和M257,遗漏了M61、M89和M107。这也是“梅森素数”一名的由来。
- 一个多世纪后的1750年,才由欧拉证实M31是第8个梅森素数。
- 下个发现的梅森素数是由卢卡斯在1876年证明的M127;
- 1883年,Pervushin证实M61。
- M89和M107在20世纪早期由Powers分别在1911年和1914年发现。
- 发明电子计算机改革了梅森素数的寻找过程。第一项成功例子是证明M521,它由莱默指导,用拉斐尔·米切尔·罗宾逊教授编写的软件,利用坐落在洛杉矶加利福尼亚大学的数据分析协会的,属于美国国家标准局的西部自动计算机(SWAC)于1952年1月30日晚上10:00获得,并且在随后不到两小时发现下个梅森素数M607。在随后的几个月里,使用同样的程序发现了另外三个梅森素数M1279、M2203和M2281。
- 素数P值增大,搜寻梅森素数MP的过程都艰辛无比,但各国科学家及业余研究者仍乐此不疲,激烈竞争;1979年2月23日,当美国克雷研究公司的计算机专家史洛温斯基和纳尔逊宣布找到第26个梅森素数M23209时才知诺尔在两星期前已得到这结果。
- 为此,史洛温斯基潜心发愤,花了一个半月用CRAY-1型计算机找到新梅森素数M44497,这纪录成了当时不少美国报纸的头版新闻。
- 他之后乘胜前进,使用改进了的CRAY-XMP型计算机在1983年至1985年间找到3个梅森素数M86243、M132049和M216091,但未能确定M86243和M216091之间是否有异于M132049的梅森素数。而到了1988年,科尔魁特和韦尔什使用NEC-FX2型超高速并行计算机果然捉到“漏网之鱼”M110503。
- 1994年1月14日,史洛温斯基和盖奇为其公司再次夺回发现“已知最大素数”的桂冠——M859433;而下个梅森素数M1257787仍是他们的成果,用CRAY-794超级计算机在1996年找到。
- 史洛温斯基发现7个梅森素数,获美誉“素数大王”。
- 到2018年12月已知51个梅森素数;现在已知最大的素数是梅森素数M82589933,像前几个一样都是由因特网梅森素数大搜索(GIMPS)分布式计算项目发现。
- 2010年7月11日GIMPS确认M2099万6011是第40个梅森素数。[2]
- 2011年12月1日GIMPS确认M2403万6583是第41个梅森素数。[2]
- 2012年12月20日GIMPS确认M2596万4951是第42个梅森素数。[2]
- 2013年1月25日GIMPS发现M5788万5161[2]
- 2014年2月23日GIMPS确认M3040万2457是第43个梅森素数。[2]
- 2014年11月8日GIMPS确认M3258万2657是第44个梅森素数。[2]
- 2016年1月7日GIMPS发现M7420万7281[2]
- 2018年1月3日GIMPS发现的M7723万2917有23249425位数[3]。
- 2018年12月7日GIMPS的M8258万9933有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 | 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日[注 1] | 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日[注 2] | 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个梅森素数(M57885161)和第51个(M82589933)间是否还有未知梅森素数,其序号用*标出,如有会通知递补。
外部链接
编辑- (英文)Great Internet Mersenne Prime Search (页面存档备份,存于互联网档案馆) GIMPS计划
- (英文)Mersenne Primes: History, Theorems and Lists (页面存档备份,存于互联网档案馆) 梅森素数:历史,定理,以及梅森素数列表
参考
编辑- ^ 1.0 1.1 Mersenne Prime Discovery - 2^82589933-1 is Prime!. www.mersenne.org. [2018-12-24]. (原始内容存档于2018-12-22).
- ^ 2.0 2.1 2.2 2.3 2.4 2.5 2.6 GIMPS Milestones. [2012-03-03]. (原始内容存档于2016-09-03).
- ^ GIMPS Project Discovers Largest Known Prime Number: 277,232,917-1. Mersenne Research, Inc. 2018年1月3日 [2018年1月14日]. (原始内容存档于2018年1月3日).