1700997080
证明：我们反过来假设质数的个数是有限的。既然质数的个数有限，就必然存在最大的质数，我们将这个数字记作P。现在，观察P! + 1这个数字。由于从2到P的所有数字都可以整除P!，因此它们都不可能整除P! + 1。这样一来，P! + 1就必然有一个大于P的约数为质数，而我们假设P是最大的质数，两者是矛盾的！ □
1700997081
1700997082
尽管我们永远也无法找到一个最大的质数，但这并不能阻止数学家和计算机科学家寻找更大质数的努力。在我创作本书的时候，已知的最大质数有17 425 170位数。把这个数字写下来，可以写成大约100本跟本书大小、厚度差不多的书。不过，我们也可以把它表示为：
1700997083
1700997084
257 885 161– 1
1700997085
1700997086
我们之所以能把它以如此简单的形式表达出来，是因为我们可以准确地判断出2n– 1或2n+ 1是不是质数。
1700997087
1700997088
延伸阅读
1700997089
1700997090
根据伟大的数学家皮埃尔·德·费马（Pierre de Fermat）的证明，如果p是奇质数，那么2p–1– 1必然是p的倍数。我们用前几个奇质数来验证一下。取质数3、5、7、11，我们发现： 22– 1 = 3是3的倍数，24– 1 = 15是5的倍数，26– 1 = 63是7的倍数，210–1 = 1 023是11的倍数。对于合数，我们知道，如果n是偶数，那么2n–1–1必然是奇数，不可能是n的倍数。我们再用前几个奇合数9、15和21验证一下，结果发现：28– 1 = 255不是9的倍数，214– 1 = 16 383不是15的倍数，220–1 = 1 048 575不是21的倍数（就连3的倍数都不是）。根据费马的这条定理，如果知道2N–1– 1不是数字N的倍数，那么我们甚至不需要找出N的约数，就可以根据这个属性确定N不是质数！但是，这条定理反过来却不成立。确实有些合数从某些方面来看像质数（这类数字被称为“伪质数”）。最小的伪质数是341 = 11×31，它就具备2340– 1是341的倍数这个属性。伪质数有无穷多个，尽管它们出现的频率比较低，但好在我们已经找到了甄别办法。
1700997091
1700997092
质数有很多应用，尤其在计算机科学领域。在几乎所有加密算法（包括为互联网金融交易保驾护航的公钥加密系统）中，质数都发挥了核心作用。很多加密算法都利用了这样一个事实：我们可以很快地判断出某个数字是否为质数，但我们还没有找到快速分解大数字的方法。例如，如果我随机选取两个1 000位的质数相乘，答案是一个2 000位数，任何人、任何计算机（除非量子计算机被人们成功地制造出来）几乎都不可能根据这个乘积找出原来的两个质数。人们认为，基于人类无法分解大数字这个特点编制而成的密码（例如公钥加密系统）具有很高的安全性。
1700997093
1700997094
几千年来，质数之美一直让人类魂牵梦绕。古希腊人说，如果某个数字等于所有真约数（除自身以外的约数）之和，这个数字就是“完全数”（perfect number）。例如，6的真约数是1、2、3，它们的和正好是6，因此6是一个完全数。第二个完全数是28，它的真约数1、2、4、7、14的和正好是28。接下来的两个完全数是496和8 128。完全数有什么规律呢？不妨考察它们的质因数分解结果。
1700997095
1700997096
6 = 2×3
1700997097
1700997098
28 = 4×7
1700997099
1700997100
496 = 16×31
1700997101
1700997102
8 128 = 64×127
1700997103
1700997104
看出其中的规律了吗？被乘数是2的幂次方，乘数是比被乘数的2倍小1的质数。（因此，在上述算式中我们没有看到8×15或者32×63，因为15和63都不是质数。）我们可以用下面这条定理对这个规律加以概括。
1700997105
1700997106
定理：如果2n–1是质数，那么2n–1×(2n–1)是完全数。
1700997107
1700997108
延伸阅读
1700997109
1700997110
证明：令p= 2n–1，p是质数，我们的目标是证明2n–1p是完全数。2n–1p的真约数有哪些呢？不含p的约数只有1，2，4，8，…，2n–1，它们的和为2n– 1=p。其他约数（不包括2n–1p）则都包含p，这些约数的和为p(1 + 2 + 4 + 8 + … + 2n–2) =p(2n–1– 1)。因此，所有真约数的和为:
1700997111
1700997112
p+p(2n–1– 1) =p［1 + (2n–1– 1)］ = 2n–1p
1700997113
1700997114
证明完毕。 □
1700997115
1700997116
伟大的数学家莱昂哈德·欧拉（Leonhard Euler，1707—1783）证明了所有完全数都是偶数。在我创作本书的时候，人们已经发现了48个完全数，而且全部是偶数。是否存在完全奇数呢？目前，还没有人知道这个问题的答案。有人认为，如果完全奇数真的存在，它们的位数将超过300。不过，还没有人证明完全奇数肯定不存在。
1700997117
1700997118
关于质数，有很多表述简单但却悬而未决的问题。前面已经说过，关于斐波那契数列中的质数是否有无穷多个的问题，现在还没有答案。［已经有人证明斐波那契数列中只有两个完全平方数（1和144）和两个完全立方数（1和8）。］还有一个未解难题被称为“哥德巴赫猜想”（Goldbach’s conjecture），即所有大于2的偶数都是两个质数之和。目前没有人可以证明这个猜想，但是有人证明，如果有反例存在，那么这个数字至少是19位数。［不久前，人们在一个比较相似的问题上取得了突破。2013年，法国数学家哈罗德·贺夫高特（Harald Helfgott）证明了所有大于7的奇数都至多是三个奇质数之和。］最后再介绍一个未解难题。我们把差为2的两个质数定义为“孪生质数”（twin primes）。排在前面的几对孪生质数分别是3和5，5和7，11和13，17和19，29和31，等等。你知道为什么3、5、7是唯一的“质数三胞胎”吗？尽管已经有人证明末位数是1（或者3、7、9）的质数有无穷多个［古斯塔夫·狄利克雷（Gustav Dirichlet）提出的一个命题的特例］，但孪生质数是否有无穷多对的问题仍未找到答案。
1700997119
1700997120
在结束本章之前，我们来看一个有点儿可疑的证明，但是我希望大家能相信这个命题。
1700997121
1700997122
命题：所有正整数都值得关注！
1700997123
1700997124
1700997125
证明：人们一致认为前几个正整数值得关注。例如，1是第一个正整数，2是第一个偶数，3是第一个奇数，4是唯一一个名副其实的数字（它的英文单词“FOUR”正好有4个字母）。我们反过来假设有的正整数不值得关注，那么必然有第一个不值得关注的正整数，我们把它记作N。但是，作为第一个不值得关注的正整数，N必然因此引起关注！因此，不值得我们关注的正整数是不存在的！
1700997126
1700997127
1700997128
1700997129