|
质数是只有1和它本身两个约数的数字。比如5就是质数，因为5只有1和5两个约数，而4就不是质数，因为4的约数除了1和4，还有2，这样的数字称为合数。 数学中有一个专门的分支：数论，专门研究最简单的数字——自然数的性质。在数论中，质数是最引人入胜的风景， 有许许多多关于质数的猜想，例如以前介绍过的哥德巴赫猜想、费马数猜想等等，有些经过了数百年的时间才被人证明，有些直到现在还没有被证明。正因为质数如此迷人和复杂，目前人们还没有完全掌握质数的规律，所以人们才把质数作为密码学的基础。 那么，质数到底有多少个呢？它的分布有什么规律吗？人们对质数的研究已经有了哪些成果呢？ 质数有多少个？我们很容易通过计算写出前几个质数，它们是： 2、3、5、7、11、13、17、19、23、29、31、37… 那么，如果我们就这样写下去，能够把质数都写穷尽吗？如果质数可以穷尽，那么关于质数的许多猜想就变得容易了许多。遗憾的是，在古希腊时代，人们就已经认识到质数有无穷多个了，这要归功于数学家、几何学的创立者欧几里得。 欧几里得通过反证法证明了质数有无穷多个。所谓反证法，就是假设一个命题不成立，再通过演绎的方法推理出两个相互矛盾的结论，从而证明该命题。欧几里得的思路是： 假设质数的个数是有限个，分别是2、3、5、7、….、p,其中p是最大的质数，那么可以令数字q等于所有质数的乘积与1的和，即 这个数字q是质数还是合数呢？ （1）如果这个数字q是质数，那么q是一个比p大的质数，与p是最大的质数矛盾，所以q不是质数。 （2）如果这个数字q是合数，那么它必然有除了1和它本身以外其他的约数，或者说它可以进行质因数分解，也就是把它写作一堆质数的乘积： 这里的m都是质数，叫做q的质因子。由于所有的质数都被我们找到了，因此每一个m只能在2、3、5、7、…、p中取值。 可是，根据q的计算方法可知： 也就是说q-1是2、3、5、7、…、p这些质数的整数倍，q除以2、3、5、7、…、p中的任何一个数字都会有余数1，因此q不可能有任何一个质数因子，这与q是合数矛盾，q不可能是合数。 所以，q既不是质数也不是合数，二者发生了矛盾。矛盾的起源在于我们假设质数是有限个，所以质数不可能是有限个，质数有无穷多个，真是一个漂亮的证法！ 如何寻找质数？虽然质数有无穷多个，但是人们依然希望知道如何快速判断一个数是质数还是合数。古希腊的埃拉托色尼（我们之前谈到过，就是那个测量出地球半径的人）给出了一种制作质数表的方法：筛选法。 他的思路是：要找到一个小于某自然数n的全部质数，只需要按照下面的方式： 1. 找到这个数字的平方根m=√m 2. 找到不大于m的所有质数。 3. 在一张自然数表上划掉所有质数的整数倍（质数本身不划掉） 4. 把1划掉。 5. 没有划掉的数字就是质数。 例如，我们要找到100以内的所有质数，只需要按照下面的步骤进行： 1. 计算100的平方根，是10。 2. 10以内的质数有2、3、5、7 3. 划掉2、3、5、7的整数倍。首先划掉2的倍数，如4、6、8…、98、100，然后划掉3的倍数，如6、9、12、15、…、99， 重复的就不需要再划掉了。然后划掉5的倍数，7的倍数。 4. 最后划掉1。 5. 表中余下的数字就是质数。 这个方法的依据是：如果一个数字是合数，那么它最小的质因子不会超过它的平方根。对于这个问题的证明我们依然可以使用反证法：如果所有质因子都大于它的平方根，两个质因子相乘就会比它大了。 质数分布有规律吗？人们虽然可以通过这种方法获得质数表，但是数字一旦大起来，判断是不是质数就非常困难，人们只能使用已知的质数因子一个个去除，去尝试。例如费马数 它有一个1187位的因子，还没有判断出来是不是质数。 长久以来，人们一直希望发现质数的分布规律，最好能通过一个公式算出质数，或者能通过前面的质数计算出后一个质数。 第一个获得突破的人是瑞士数学家欧拉。 欧拉在研究级数求和的问题中，得到了一个著名的公式：欧拉乘积定理。 这个公式并不难理解：左边的Σ表示求和，即把全体自然数n的s次幂的倒数求和。右边的Π表示乘积，而数字p是质数。如果我们把它展开成更加好认的形式，就是：
这是多么美妙的式子！虽然自然数和质数都是无穷多个，但是全体的自然数和全体质数之间却有某种微妙的联系。 不仅如此， 欧拉通过对质数的研究，发现了一个近似的规律：小于一个数x的质数个数π(x)大约可以用一个函数计算出来：
lnx是一个对数函数。 欧拉研究出这个内容之后，就去做其他工作了。毕竟欧拉涉猎的内容太广泛。于是，这个内容的接力棒就传到了另外一位数学巨匠高斯手中。 素数定理在欧拉去世的时候，德国的数学巨匠高斯六岁。
他最出名的应该是在小学的时候计算1+2+3+4+…+100的故事，但是他的贡献远远不止与此。高斯在数论、代数、统计、分析、微分几何、大地测量学、地球物理学、力学、静电学、天文学、矩阵理论和光学等方面均有巨大贡献，以高斯的名字命名的定律有110个，他和阿基米德、牛顿、欧拉并称为四大数学家。 高斯小的时候，经常自己一个人研究数字。他经常随意的写出连续1000个数字，并找出中间的质数个数。他发现，开始的数字越大，这连续1000个数字中的质数越少。他用找出的质数个数除以1000，就得到了质数的“密度”。高斯发现这个密度大约可以用算式
计算。这个结果与欧拉得到的结果接近，但又不完全相同。 高斯得到这个结果后，并没有急于发表。因为高斯并不喜欢发表一些不成熟的结论，他向来要求自己的论文严格而优美。这样，这个机会就留给了法国数学家勒让德。
勒让德在1798年提出：小于x的质数个数可以用下面的计算得到：
其中的第一项积分式子称为Li(x)，而c是一个误差项。质数也叫做素数，而且勒让德提出这个问题的时候，并没有严格证明，所以称为素数猜想。 勒让德提出素数猜想的荣誉保留了50年，然而在1849年，高斯在给他人的信中谈到：1792年他就已经提出了这个猜想。人们相信高斯，因为高斯经常这么干。
我们把素数猜想计算的结果Li(x)，质数实际个数π(x)，以及欧拉计算的x/lnx画在一张图中，就会发现Li(x)的结果更加接近实际的素数个数。
质数与黎曼猜想我们之前谈到：质数与黎曼猜想之间有着千丝万缕的联系。1896年，法国科学院举行比赛：征稿证明黎曼定理。两位年轻的数学家阿达马和德·拉·瓦莱布桑获得了这一殊荣。实际上这两位数学家并没有证明黎曼猜想，只是获得了一点进展，但是这一点进展就一举证明了欧拉和勒让德的猜想，把素数猜想变成了素数定理。黎曼猜想的威力可见一斑。 1901年，瑞典数学家科赫证明：如果黎曼猜想被证实，那么素数定理中的误差项c大约是√xln(x)的量级。 然而黎曼猜想到底是对是错？可能我们还需要等待许多年。即便黎曼猜想被证实，人们也只是在质数规律探索的过程中更近了一步，距离真正破解质数的规律，还有很长的路要走。也许质数就是宇宙留给人类的密码。 |
|
|
