公爵的野猫完整版:关于质数

来源:百度文库 编辑:高校问答 时间:2024/03/29 15:55:00
能不能说一些关于质数的东西,质数的规律是什么?

质数的规律

什么是质数?就是在所有比1大的整数中,除了1和它本身以外,不再有别的约数,这种整数叫做质数,质数又叫做素数。这终规只是文字上的解释而已。能不能有一个代数式,规定用字母表示的那个数为规定的任何值时,所代入的代数式的值都是质数呢?
质数的分布是没有规律的,往往让人莫明其妙。如:101、401、601、701都是质数,但上下面的301和901却是合数。
有人做过这样的验算:1^2+1+41=43,2^2+2+41=47,3^2+3+41=53……于是就可以有这样一个公式:设一正数为n,则n^2+n+41的值一定是一个质数。这个式子一直到n=39时,都是成立的。但n=40时,其式子就不成立了,因为40^2+40+41=1681=41*41。
被称为“17世纪最伟大的法国数学家”费尔马,也研究过质数的性质。他发现,设Fn=2^(2^n),则当n分别等于0、1、2、3、4时,Fn分别给出3、5、17、257、65537,都是质数,由于F5太大(F5=14292967297),他没有再往下检测就直接猜测:对于一切自然数,Fn都是质数。但是,就是在F5上出了问题!费尔马死后67年,25岁的瑞士数学家欧拉证明:F5=14292967297=641*6700417,并非质数,而是合数。
更加有趣的是,以后的Fn值,数学家再也没有找到哪个Fn值是质数,全部都是合数。目前由于平方开得较大,因而能够证明的也很少。现在数学家们取得Fn的最大值为:n=1495。这可是个超级天文数字,其位数多达10^10584位,当然它尽管非常之大,但也不是个质数。质数和费尔马开了个大玩笑!
17世纪还有位法国数学家叫梅森,他曾经做过一个猜想:2^p-1代数式,当p是质数时,2^p-1是质数。他验算出了:当p=2、3、5、7、17、19时,所得代数式的值都是质数,后来,欧拉证明p=31时,2^p-1是质数。
还剩下p=67、127、257三个梅森数,由于太大,长期没有人去验证。梅森去世250年后,美国数学家科勒证明,2^67-1=193707721*761838257287,是一个合数。这是第九个梅森数。20世纪,人们先后证明:第10个梅森数是质数,第11个梅森数是合数。质数排列得这样杂乱无章,也给人们寻找质数规律造成了困难。
现在,数学家找到的最大的梅森数是一个有378632位的数:2^1257787-1。数学虽然可以找到很大的质数,但质数的规律还是无法循通。
头五千万个质数

--------------------------------------------------------------------------------

【摘要】不按牌理出牌 数学家也拿他没办法

质数怎样分布?古今中外,不论是专业的数学家或业余的嗜好者,都曾被这问题所深深吸引。

质数是个比1大的自然数,除了自身和1以外,没有其他自然数可以除尽他。质数的分布有两个互相矛盾的特点。下面我会列举一些事实,使你永远相信这两个特点。

第一点,尽管质数的定义极为简单,又是自然数的建构砖石(任何自然数都可表为质因数的幂次的连乘积,且表法唯一),它却是数学家研究的对象中最不驯的一种;质数在自然数中,像杂草似地乱长,似乎除了机会律以外,不遵守其他的规律,没人敢说下一个会从那里冒出来。

第二点更令人惊讶,因?T篕P第一点相反,质数表现出惊人的规律性。也就是说,确有规律限制质数的行为,他们像军人一样绝对服从这些规律。

为了支持第一点,我把100以下的质数和合数写出来(除了2以外,不列偶数):

【浏览原件】

再把1千万加减一百以内的质数列出:在9,999,900与10,000,000之间的质数

9,999,901

9,999,907

9,999,929

9,999,931

9,999,937

9,999,943

9,999,971

9,999,973

9,999,991

在10,000,000与10,000,100之间的质数

10,000,019

10,000,079

你看!没有什麼理由可以说这个数是质数,那个数不是质数。当你看到这些数字时,是否联想到宇宙的奥秘,像天边那闪烁的星星一样神秘不可测?甚至数学家都无法揭开此一奥秘,如果他们能够,他们就不会劳神苦思去计算下一个更大的质数是多少了。(没有人会想去找比前一个平方数更大的平方数,或2的幂次数——通常一个好学生只记到210=1024)。

1876年,Lucas证明2127-1为质数,这纪录维持了75年。这也难怪,因为

2127-1

=1701411834604469231731687303715884105727

直到1951年,电子计算机的新纪元,更大的质数陆续发现(见下表历次记录)。目前的记录是6002位的219937-1,不信的话,你可以去查Guiness世界记录。(编者注:根据合众国际社1978年11月15日报导,这记录已被两个18岁的加州大学学生打破。)

【浏览原件】

质数的规律

更有趣的,还是关於质数的规律。前面已提到过100以下的质数,现在用图表示,其中π(x)表示所有不大於x的质数的个数。

【浏览原件】

就这麼简单的一个图,我们已经可以看出,除了一些小的扰动以外,π(x)大致上增加得很有规律。

若把x值从一百增到五万,则此规律性变得更为明显。见下图:

【浏览原件】

当某种规律自然出现时,科学家就得设法去解释它,质数分布的规律性也不例外。关於质数分布,我们不难找到一个良好的经验规律。请看下表:(这表看来平凡无奇,却代表上千小时的艰苦计算。)

【浏览原件】

注意:x每增10倍,x与π(x)的比就增加约2.3。机警的数学家立刻联想到10取自然对数的近似值是2.3。所以x/π(x)~logx,亦即π(x)~x/logx(用log x表示x的自然对数,~表示当x接近无穷大时,π(x)与x/logx的比趋近於1;如果用≈,则表示接近的程度更好。)

质数定理

这个关系叫做质数定理,是高斯1791年发现的,但直到1896年才得到证明。高斯(1777~1855年,关於高斯与质数定理,请参阅凡异出版社,伟大数学家的一生——高斯)14岁那年收到一本对数的书;次年,研究书上所附的质数表,发现了这个定理。终其一生,高斯一直很注意质数分布,并且花了很多功夫去计算。高斯写信给他学生安克(Encke)说他「时常花费零星的片刻计算1000个连续整数(如18001到19000)中有多少质数」,最后他竟能列出三百万以下的所有质数,并且拿来和他的推测公式比较。

质数定理说π(x)是渐近地,即相对误差趋近於0,等於x/logx。但是如果拿x/logx与π(x)的图形加以比较,则可看出,虽然x/logx反映了π(x)行为的本质,却还不足以说明π(x)的平滑性。

【浏览原件】

所以,我们希望找到更佳的近似函数。如果我们再仔细看看前面那个表,会发现x/π(x)差不多恰为logx-1。经过更小心地计算,并和π(x)的更精密数据相较,乐强何(Legendre)在1808年找到特佳的近似。即

π(x)≈x/(log-1.08366)

另有一种π(x)的近似函数也不错,是高斯与质数定理同时提出的。从经验得知,当x很大时,在x附近出现质数的或然率差不多恰为1/logx。因此,π(x)差不多应为

对数和:Ls(x)=1/log2+1/log3+…+1/logx或实值上相同的

对数积分:【浏览原件】

现在再比较Li(x)与π(x)的图形,把座标轴的尺度取到这麼大时,两者完全重合。

没有必要再把乐强何的近似图形列出来给大家看,因为在0到5万之间,他的近似比Li(x)更加接近π(x)。

【浏览原件】

质数的幂次

再提一个π(x)的近似函数。从黎曼(Riemann)研究质数的结果显示,如果我们在计算质数以外,还计算质数的幂次(质数的平方算半个质数,质数的立方算1/3个质数,依此类推),则一个很大的数x为质数的或然率将更接近1/logx。从此导出

【浏览原件】



【浏览原件】

第二式右边的函数定名为R(x)以纪念黎曼。从下表可以看出它与π(x)有惊人的吻合。

【浏览原件】

R(x)可以表为

【浏览原件】

在这里要强调一点,高斯和乐强何的近似都是由经验归纳而来的,不是由逻辑证明得到的。甚至黎曼函数也是如此,虽然他的R(x)有理论的解释,他从未证明出质数定理。Hadamard以及de la Vall'eePoussin根据黎曼的工作,继续研究,终於在1896年首度完成证明。

孪生质数

关於质数的规律性,我们再来看一些数值的例子。前面说过,在x附近的一个数其为质数的或然率为1/logx。换句话说,假使取一以x为中心,长度为a的区间,这区间长得足以使统计成为有意义,而与x相较,又足够小时,其中质数的个数,应该约为a/logx。例如,在壹亿至壹亿零壹拾伍万之间,预计有8142个质数,因为

150,000/log(100,000,000)=150,000/18.427… ≈8142

根据同样的想法,在x附近的任意两数同时为质数的或然率应约为1/(logx)2。所以如果有人问在x到x+a之间有多少孪生质数(连续两个奇数都是质数,如11,13或59,61),则我们可以预计有a/(logx)2个。事实上,我们可以预计多些,因为n已是质数,使n+2为质数的可能性稍稍加大。(例如n+2必为奇数)。用一个容易的直观的论点,可以得到在〔x,x+a〕中,孪生质数的对数为C.a/(logx)2,此处C=1.3203236316…。

所以在壹亿至壹亿零壹拾伍万之间应有(1.32…).150,000/(18.427)2≈584对孪生质数。下表列出一些同长区间中质数及孪生质数的预测值及真值。由下表可以看出,理论和实际有极佳的吻合。对於孪生质数而言,这种吻合更令人惊讶。因为孪生质数是否为无穷,这问题直到现在尚无定论,遑论他的分布定律了。

【 浏览原件】

质数的距离

关於质数分布的规律性,最后一个例子就是相邻两质数的距离。若有人去查质数表,会注意到有时距离相当大。例如113和127之间无其他质数。令g(x)表x以下,所有相邻质数的最大距离。则g(200)=127-113=14。当然,g(x)增加得极不规则。但是用一个直觉的论点可以得到下列渐近公式,g(x)~(logx)2。从下图可以看出,像g(x)这样极不规则的函数,其行为和预测能符合的程度。

【 浏览原件】

到现在为止,质数的规律性说得较多,不规律性说得很少。而本文标题「头五千万个质数」,我也只提到前几千个而已。所以现在先列一表,比较π(x),乐强何,高斯,黎曼四函数在x小於一千万范围内的差异。因为这四种函数在图上分辨不出差异,如前面所列π(x)与Li的比较图,所以现在这图只表示这三种函数与π(x)的差。我想从这图足以看出,一个有志研究数论的人可能遇到的麻烦有多大。当x很小时(小於一百万),x/logx-1.08366比Li(x)近似π(x),但是五百万以后,Li(x)变得较近似,而且可以证明当x更增加时,Li(x)总是较近似π(x)。

【 浏览原件】

就算我们讨论到一千万,其中也只有60万多个质数。要达到应许的五千万个质数,x必须为十亿。下图表示十亿以内R(x)-π(x)的图形。R(x)-π(x)的振动变得愈来愈大,但即使到十亿这麼大,振动仍在几百以内。

【 浏览原件】

顺便提另一个π(x)的趣事。从图上可以看出,在一千万以内,Li(x)总是大於π(x),10亿以内仍然如此。见下图(此图以对数尺寸绘出)。

【 浏览原件】

上图给我们一个印象,当x继续增加时,Li(x)-π(x)会稳定地无限增加。但是上述推测错了!事实上,立特伍(Littlewood)可以证明有某x值,而π(x)会大於Li(x)。但到目前为止,并未真正找到一个确数,使此事成立,而且恐怕永远不会找到。但是立特伍的证明不可能有误,而且Skewes更证明在【浏览原件】以内就有一个这样的数。英国名数学家Hardy有一次说,这可能是数学上有确定目的的数字中最大的了。总而言之,此例说明了,在质数理论里,仅仅依赖数据就想要导出结论的作法是多麼不智啊!

〔本文节译自“The First 50 million Prime Numbers”,原文刊登在The New Mathematical Intelligencer, Vol. 0, Aug. 1977,为原作者Don Zagier就任德国波昂大学教授的就任演说稿。〕

质数在自然数里的排列是没有规律的.
——此处的规律是说对于无穷序列的不可预知。

数学家在努力的寻找质数公式.
——数学家是在无穷的未知中寻找有限的真理。

难道数学公式不是对规律的阐述吗?
——是的,但是有限的相对真理,不是对于无穷的绝对真理。

上小学的时候,我们就知道所有的自然数可以分为质数(素数)和合数两类,当然还特别规定了“1既不是质数,也不是合数”。100以内的质数,从小到大依次是:2、3、5、7、11、13、17、19、……、83、89、97。不用说了,你一定会背下来。那么质数的个数是不是有限多的呢?
在解决这个问题之前,我们先来看看另一个问题:怎样判断一个已知自然数是不是质数。比如,143是不是质数?

你一定会按照下面这个步骤去判断: 先用最小的质数2去除143,不能整除;再用3去试试,还是不行;再依次用5、7试试,还是不行;11呢?行!143=11×13,所以143不是质数,而是合数。所以,判断一个数是不是质数,只需用比这个数小的所有质数,依次去除它即可,如果都不能整除的话,这个数就一定是质数;相反,只要这个数能够被某一个质数整除,这个数就一定是合数。这种方法所依据的原理是:每一个合数都可以表示成若干个质数的乘积。不用说,这叫做“分解质因数”,也是小学数学的知识。

我们先假设质数的个数是有限多的,那么必然存在一个“最大的质数”,设这个“最大的质数”为N。下面我们找出从1到N之间的所有质数,把它们连乘起来,就是:

2×3×5×7×11×13×……×N
把这个连乘积再加上1,得到一个相当大的数M:

M=2×3×5×7×11×13×……×N+1

那么这个M是质数还是合数呢? 乍一想,不难判断,既然N是最大的质数,而且M>N,那么M就应该是合数。既然M是合数,就可以对M分解质因数。可是试一下就会发现,我们用从1到N之间的任何一个质数去除M,总是余1!这个现实,又表明M一定是质数。

这个自相矛盾的结果,无非说明: 最大的质数是不存在的!如果有一个足够大的质数N,一定可以像上面那样,找到一个比N更大的质数M。既然不存在最大的质数,就可以推知自然数中的质数应该有无限多个。

确实没发现什么规律,不过任何一个正整数,都可表示为一个素数和一个合数相加得到