梅森素数
此條目需要补充更多来源。 (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日).