1700997048
1700997049
延伸阅读
1700997050
1700997051
在有的数字系统中，并不是所有的数字都有唯一的质因数分解结果。例如，火星人长了两个脑袋，因此他们只使用偶数：
1700997052
1700997053
2，4，6，8，10，12，14，16，18，20，22，24，26，28，30…
1700997054
1700997055
在火星人的数字系统中，6和10被视为质数，因为它们不能分解成更小的偶数。在这种数字系统中，质数和合数严格地交替出现。4的所有倍数都是合数（因为4k= 2×2k），其他的所有偶数（包括6、10、14、18等）都是质数，因为它们无法分解成两个更小的偶数。但是，我们来看180这个数字：
1700997056
1700997057
6×30 = 180 = 10×18
1700997058
1700997059
在火星人的数字系统中，180有两种不同的质因数分解结果，这证明火星数字系统中的质因数分解不具有唯一性。
1700997060
1700997061
1700997062
1700997063
1700997064
1~100中有25个质数，101~200中有21个质数，210~300中有16个质数。随着数字越来越大，质数出现的频率越来越低。（但是，这种减少的趋势无法预测。例如，在301~400和401~500中，分别有16和17个质数，而1 000 001~1 000 100中只有6个质数。）这是有道理的，因为大数有多个约数的可能性更大。
1700997065
1700997066
我们可以证明，有时候连续100个数字之中也没有一个质数。如果愿意花时间寻找，你甚至可以发现连续1 000或者100万个数字中也没有一个质数。你不相信的话，我可以立刻为你提供连续99个合数（尽管在这之前就已经出现过同类现象了）。观察下面这99个连续数字。
1700997067
1700997068
100! + 2，100! + 3，100! + 4，…，100! + 100
1700997069
1700997070
因为100! = 100×99×98×…×3×2×1，所以它肯定可以被2~100的所有数字整除。接下来，我们以100! + 53为例。由于53是100!的约数，因此它肯定也是100! + 53的约数。同理可证，对于所有的2 ≤k≤ 100，100! +k都必然是k的倍数，也就是说，它们都是合数。
1700997071
1700997072
延伸阅读
1700997073
1700997074
注意，我们在上述证明过程中根本没有提到100! + 1是不是质数的问题，但我们其实是可以做出判断的。在这里，我们要应用一个非常棒的定理——“威尔逊定理”（Wilson’s theorem）。这条定理指出，当且仅当 (n－1)! + 1是n的倍数时，n为质数。用几个比较小的数字加以检验，就会发现确实如此。1! + 1 = 2是2的倍数，2! + 1 = 3是3的倍数，3! + 1 = 7不是4的倍数，4! + 1 = 25是5的倍数，5! + 1 = 121不是6的倍数，6! + 1 = 721是7的倍数，等等。由于101是质数，根据威尔逊定理，100! + 1是101的倍数，因此它是合数。也就是说，从100!至100! + 100的101个连续数字都是合数。
1700997075
1700997076
既然随着数字越来越大，质数的出现频率越来越低，人们自然会想，当数字大到一定程度时，会不会就没有质数了呢？两千多年前，欧几里得告诉我们并非如此。但不能因为他是欧几里得我们就相信他的话，我们还是尽情享受证明的乐趣吧。
1700997077
1700997078
定理：质数有无穷多个。
1700997079
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