Mersenne Primes:历史,定理和名单

内容:

  1. 早期历史
  2. 完美的数字和一些定理
  3. 已知梅森质数表
  4. Lucas-Lehmer测试和最近的历史
  5. 猜想和未解决的问题
  6. 也可以看看下一个较大的mersenne素数在哪里?Mersenne启发定

1.早期的历史

许多早期作家都觉得表格2的数量N-1是素质的全部素瓜N但是,在1536年,Hudalricus Regius表明了211.-1 = 2047不是质数(它是2389)。到1603年Pietro Cataldi是否正确验证了217.-1和219.-1都是素数,但后来陈述了2N-1也是23,29,31和37的素质。1640年费玛表明加泰达尔错了23和37;然后欧拉在1738年显示,目录也是错误的29。一段时间之后欧拉显示Cataldi的断言约31是正确的。

输入法国僧侣Marin Mersenne.(1588-1648)。Mersenne在他的序言中陈述Cogitata Physica-Mathematica(1644)数字2N-1是素质的

N= 2,3,5,7,13,17,19,31 67 127 257

并且是所有其他正整数的复合材料N<257. Mersenne的(不正确)猜想只比regius略好,但仍然拿到这些数字的名字。

定义:当2N-1是质数,也就是a梅森素数

梅森的同辈显然不可能测试所有这些数字(事实上他也承认了这一点),但他们也无法测试这些数字。直到100多年后的1750年,欧拉才验证了梅森尼和雷吉斯名单上的下一个数字:231.1是素数。又过了一个世纪,1876年,卢卡斯验证2127.-1也是质数。7年后,perouchine展示了261.-1是素数,所以Mersenne错过了这一点。在1900年代初的权力中表明,Mersenne也错过了素数289-1和2107.1。最后,在1947年梅森的射程范围内,N<258,已完全检查,并确定正确的列表是:

N= 2,3,5,7,13,17,19,31,61,89,107和127。

看到已知梅森表下面的质数。

2.完美的数字和一些定理

许多古代文化都关注了一个数字与其除数的关系,往往提供神秘的解释。在这里,我们仅关注一种这种关系:

定义:积极的整数N被称为完美的数字如果它等于其所有正除法的总和,请不包括N本身。

例如,6是第一个完美的数字,因为6 = 1 + 2 + 3。接下来是28 = 1 + 2 + 4 + 7 + 14。接下来的两个是496和8128.这四个都在基督的时候都知道。以以下部分因素形式查看这些数字:

23,47,1631日,64年127。

你是否注意到它们都有相同的表格2N-1(2N-1)(对于N分别= 2,3,5和7)?并且在每种情况下2N-1是一个mersenne素数吗?事实上,很容易显示以下定理:

定理一: K.如果且仅当它具有2表格2,这是一个偶然的数字N-1(2N-1)和2N-1是素数。[证明。]
定理二:如果是2.N-1是质数,那么也是质数N。[证明。]

所以寻找梅森数也是在寻找偶数完全数!

您也可能注意到上面列出的完美数字(6,28,496,8128)所有以数字6或数字8结束 - 这也很容易证明(但不,它们不继续交替6,8,6,8,......)。如果您喜欢该数字模式,请查看二进制文件中的前四个完美数字:

110.
11100.
111110000
1111111000000

(二进制数字图案是定理的结果。)它是未知是否存在奇怪的数字,但如果有一个很大!这可能是所有数学中最古老的未解决问题。

当检查梅森数是否为素数时,我们通常首先寻找任何小的因数。下面的欧拉和费马定理在这方面是非常有用的。

定理三:P.问:是奇怪的素数。如果问:划分M.P.= 2P.1,那么问:= +/-1 (mod 8)和问:= 2kp.+ 1

对于一些整数K.[证明]。最后,我们为您提供以下内容:

定理四:P.= 3(mod 4)是素数。2P.当且仅当2时+1也是质数P.+1划分M.P.。[证明]。
定理五:如果将任何均匀的数字(6)的数字总和,则总结结果编号的数字,并重复此过程,直到您获得一个数字,该数字将是一个。[证明。]

3.已知的Mersenne Primes表

让m(P.)= 2P.-1和p(P.)= 2P.-1(2P.-1)。所有已知素质的列表P.为米(P.)是Mersenne素数(因此P(P.)是一个完美的数字)如下:

## P.
(指数)
数字
在M.P.
数字
在P.P.
发现者 笔记
1 2 1 1 ---- ----
2 3. 1 2 ---- ----
3. 5. 2 3. ---- ----
4. 7. 3. 4. ---- ----
5. 13. 4. 8. 1456. 匿名
6. 17. 6. 10. 1588 Cataldi
7. 19. 6. 12. 1588 Cataldi
8. 31. 10. 19. 1772 欧拉
9. 61. 19. 37. 1883 Pervushin
10. 89 27. 54. 1911年 权力
11. 107. 33. 65. 1914年 权力 请注意
12. 127. 39. 77 1876 卢卡斯
13. 521. 157. 314. 1952年 罗宾逊
14. 607. 183 366. 1952年 罗宾逊
15. 1279. 386. 770. 1952年 罗宾逊
16. 2203. 664. 1327 1952年 罗宾逊
17. 2281 687. 1373 1952年 罗宾逊
18. 3217. 969. 1937年 1957年 莱斯梅尔
19. 4253 1281. 2561 1961 赫尔维茨
20. 4423 1332 2663 1961 赫尔维茨
21. 9689 2917. 5834 1963 吉利斯
22. 9941 2993 5985 1963 吉利斯
23. 11213. 3376. 6751. 1963 吉利斯
24. 19937 6002 12003 1971 塔克曼 [Tuckerman71]
25. 21701 6533 13066 1978 诺尔和镍 [NN80.]
26. 23209. 6987 13973 1979 诺尔
27. 44497 13395 26790 1979 尼尔森&Sloctinski. [Slocinski79.]
28. 86243. 25962 51924 1982 Sloctinski. [Ewing83]
29. 110503 33265 66530. 1988 科尔奎特和威尔士 [CW91.]
30. 132049. 39751 79502 1983 Sloctinski.
31. 216091 65050. 130100 1985 Sloctinski.
32. 756839. 227832 455663 1992 Slocisski&等等。 网页
33. 859433 258716. 517430 1994 Slowinski &计
34. 1257787 378632 757263 1996 Slowinski &计 (网页)
35. 1398269. 420921 841842 1996 armengaud.Woltman
等等。gimp
(网页)
36. 2976221 895932 1791864 1997 威盛Woltman,
等等。(GIMPS)
(网页)
37. 3021377. 909526 1819050 1998 克拉克森Woltman,kurowski.
等等。(GIMPS,Primenet.
(网页)
38. 6972593 2098960 4197919. 1999 Hajratwala、Woltman Kurowski
等人(GIMPS, PrimeNet)
(网页)
39. 13466917. 4053946 8107892. 2001年 卡梅伦、Woltman Kurowski
等人(GIMPS, PrimeNet)
(网页)
40 20996011. 6320430 12640858. 2003年 谢福音、Woltman Kurowski
等人(GIMPS, PrimeNet)
(网页)
41. 24036583
7235733
14471465
2004年 Findley.、Woltman Kurowski
等人(GIMPS, PrimeNet)
(网页)
42. 25964951.
7816230
15632458
2005年 诺瓦克、Woltman Kurowski
等人(GIMPS, PrimeNet)
(网页)
43. 30402457.
9152052
18304103
2005年 库珀布恩、Woltman Kurowski
等人(GIMPS, PrimeNet)
(网页)
44. 32582657. 9808358 19616714 2006年 Cooper,Boone,Woltman,Kurowski
等人(GIMPS, PrimeNet)
(网页)
45. 37156667. 11185272 22370543 2008年 Elvenich、Woltman Kurowski
等人(GIMPS, PrimeNet)
(网页)
46. 42643801 12837064 25674127 2009年 Strindmo、Woltman Kurowski
等人(GIMPS, PrimeNet)
(网页)
47. 43112609. 12978189. 25956377 2008年 史密斯Woltman Kurowski
等人(GIMPS, PrimeNet)
(网页)
48? 57885161 17425170 34850339 2013年 Cooper,Woltman,Kurowski
等人(GIMPS, PrimeNet)
(网页)
49? 74207281 22338618 44677235. 2016年 Cooper,Woltman(Prime95),Kurowski&Blosser(PrimeNet),Gimps等。 (网页)
50? 77232917 23249425. 46498850. 2017年 PACE,Woltman(Prime95),Kurowski&Blosser(PrimeNet),Gimps等。 (网页)
51? 82589933. 24862048 49724095 2018年 Laroche, Woltman (prime95), bloser (PrimeNet), GIMPS等。 (网页)

我们用问号代替最后一个梅森质数的数字,因为在GIMPS完成一次又一次的检查之前,我们无法知道这些质数之间是否还有其他的梅森质数。看到GIMPS状态页面想要查询更多的信息。并非所有较小的指数都已过测试。

4.Lucas-Lehmer测试和最近的历史

Mersenne Primes(因此甚至完美的数字),可使用以下定理找到:

Lucas-Lehmer测试:为了P.一个奇怪的素数,mersenne号码2P.-1是质数当且仅当2P.-1划分(P.-1)其中s(N+1)= s(N2-2,和s(1)= 4. [证明。]

(取决于,也可以从S(1)= 10和某些其他值开始P.)。在伪代码中,这个测试是:

lucas_lehmer_test(p):s:= 4;因为我从3到p do s:= s2-2 mod 2.P.-1;如果s == 0那么2P.-1是素质2P.-1是复合材料;

该测试的理论是发起的卢卡斯在19世纪70年代后期被Lehmer制作成这个简单的测试。序列(N)计算Modulo 2P.-1以节省时间。该测试是二元计算机的理想选择,因为划分为2P.-1(在二进制中)可以使用旋转和加法完成。(看关于证明质数的那几页有关证明数字的更多信息是素数。)

1811年彼得巴洛他在《数论》中写道30.(231.1)“是将被发现的最大(完全数);因为它们只是好奇,并没有用处,所以没有人会试图找到一个比它们更高的。”我想知道他会如何评价第一次攀登珠穆朗玛峰的尝试,跑得更快的尝试,或者跳得更远的尝试——其他一些让人好奇但毫无用处的任务。显然,在19世纪晚期,没有人知道现代计算机的威力。关于50年后的机器,我们能知道些什么?(见也“为什么找到大素数?”

U-illinois邮票“class=在伊利诺伊大学发现23岁的Mersenne Prime之后,数学系很自豪地为他们的部门主席Bateman博士,他们的邮资仪表变为邮票“211213.-1是质数”。这种方法一直使用到1976年四色定理被证明。(1985年,贝特曼博士打印了几份早期印迹的副本——左边的图像就是其中之一。)

第25个和第26个梅森质数是由高中生劳拉·尼克尔和Landon Curt Noll.,虽然他们对所涉及的数学知识很少了解,但在当地大学的大型机(CSUH的CDC 174)上使用了卢卡斯的简单测试,找到了接下来的两个素数。他们发现了第一个素质的国家电视新闻和纽约时报的首页。他们在找到第一个素质后他们的单独方式走了,但是NOLL让程序运行以找到第二个 - 所以索尔要求完全所有权。罗马在以后搜索,虽然他从未找到过另一个Mersenne Prime,但他是一个持有最大的非Mersenne素数的团队之一。他目前适用于Silicon Graphics。

Sloctinski.他已经说服了世界各地的许多Cray实验室在业余时间(否则这些时间就会浪费掉)运行这个版本的Lucas测试。他不得不推迟宣布他的一个重要记录,直到他得到许可开始寻找它。斯Slowinski对记录质数的搜索“不像你想象的那么有组织”(他自己的话),因为他没有系统地进行搜索。事实上,看看梅森尼斯的表你会发现他错过了29质数但找到了30和31质数。Colquitt & Welsh努力填补空白,找到了29号。

进入乔治Woltman,一个优秀的程序员和组织者。从1995年底开始,他收集了不同的数据库并将它们组合成一个。然后他放置了这个数据库,一个免费的高度优化的程序,以便在网上搜索Mersennes。这开始了gimp(伟大的互联网Mersenne Prime Search):现在发现了最大的已知Mersennes,已经扫描了以前的纪录素质之间未探索的所有区域,结合了数十名专家和数千名业余的努力,并提供了哪些优惠自由软件对于大多数计算机平台。

在1997年末斯科特Kurowski(和其他人)Primenet.自动化的范围和报告GIMPS的结果,现在几乎任何人都可以加入此搜索!

5.猜想和未解决的问题

有一个奇怪的数字吗?
我们知道所有的偶数完全数都是梅森素数乘以2的幂(上面的定理),但奇怪的完美数字呢?如果有一个,那么它是一个完美的平方时间,是单个素数的奇怪力量;它是可分割的至少八个素数,并且至少有75个主要因素(不一定是不同的[HARE2006]、[HARE2005.]、[是2003.),至少有9个不同的[nielsen2006.];它至少有300位十进制数字[BCR91.];它有一个大部分的10个20.[Cohen87]。有关更多信息,请参阅[Ribenboim95]或[圭亚那]。
有无限多个梅森质数吗?
同等地我们可以问:无数是非常完美的数字吗?答案是大概是的(因为调和级数是发散的)。
无限的Mersenne复合材料吗?
欧拉显示:
定理:如果K.> 1,P.= 4K.+3是素数,然后2P.+1是素质,如果只有2P.= 1(mod 2P.+1)。
因此,如果P.= 4K.+ 3和2P.+1是质数,那么梅森数2P.-1是复合物(据猜测似乎有无限的许多素数对P.,2P.+1)。
新的梅森猜想
贝特曼、塞尔弗里奇和瓦格斯塔夫曾推测[BSW89.] 以下。
P.是任何奇怪的自然数。如果以下两个条件保持,那么第三条件也是如此:
  1. P.= 2K.+ / - 1或P.= 4K.+/- 3.
  2. 2P.-1是素数(显然是梅森素数)
  3. (2P.+1)/3是质数。
注意这个猜想是如何与前一个猜想中的定理相联系的。请浏览我们的网页新的梅森猜想用于状态信息。
每个mersenne号码2P.-1平方免费?
这在一个公开问题(我们不知道答案)的类别中,而不是猜想(我们猜这是真的)的范畴[圭亚那第A3节]。这是简单的展示如果是素质的平方P.然后划分mersenneP.是A.Wieferich '这些都很罕见!只有两个人在4,000,000,000,000以下是众所周知的,并且这些被这些平方划分了Mersenne。
让C0.= 2,然后让c1= 2C0.1, C2= 2C11, C3.= 2C2-1,......这些所有的素数吗?
根据迪克森的说法[迪克森v1p22]加泰罗尼亚州于1876年回复卢卡斯陈述2127.1 (C4.)是这个序列的素数。这些数字很快成长:
C0.= 2 (主要的)
C1= 3 (主要的)
C2= 7. (主要的)
C3.= 127. (主要的)
C4.= 170141183460469231731687303715884105727 (主要的)
C5.> 10.5121759971936968187500605468187500605468187500605462505006054625051616349 (是C.5.'吗?)
这似乎很不可能5.(或许多较大的术语)将是素质的,所以这毫无疑问是男人的另一个例子强小数定律。请注意,如果该序列中甚至有一个综合术语,那么定理一体下面所有的项都是合数。(Landon Curt Noll.告诉我他已经使用了他的计划Calc.验证c5.没有低于5 * 10的主要除数51.)。
有更多的双人龄素吗?
另一个常见的早期误解是如果N= MP.是素数,那么也是N;让我们称这个数字mmP.(一个“双人民币”)。事实上,前四个这样的数量中的每一个都是素数:
毫米2= 23.1 = 7,
毫米3.= 27.-1 = 127,
毫米5.= 231.-1 = 2147483647,
毫米7.= 2127.1 = 170141183460469231731687303715884105727。
但是,接下来的四个(mm13.毫米17.毫米19.和毫米31.)所有已知的因素 - 所以是复合材料。这个序列是否有更多的素数?可能不是,但它仍然是一个开放的问题。托尼福布斯是领先的一个搜索下一个术语的项目:毫米61.,你可能想加入和帮助!通知加泰罗尼亚序列上面是这个的子序列。

从Primepages ©Chris Caldwell。