镶嵌在数的拼图中的素数

我们怎样才能确定素数不会越来越稀少，最终逐渐消失殆尽呢？你可能会认为由于有无穷多自然数，而每一个都可以被分解为素数的乘积（这一点我们一会儿仔细解释），那么必然得有无穷多个素数才能承担这一工作。虽然这个结论是正确的，但它并不能从上述观察中得出。这是因为如果我们从有限个素数开始，仅使用这些给定的素因数，我们就能制造出无穷多不同的数。确实如此，任何单个素数都有无穷多个幂次。比如，素数2的幂分别为2，4，8，16，32，64，…因而完全可以设想：只有有限多的素数，每个数都是那些素数的幂的乘积。更糟的是，我们能构造出一个给定数的任意长度的幂数列，或它的任意多倍数列，却没法用同样的手段构造出一个由不同素数组成的无穷数列。对于素数，我们还是得去搜寻，到底怎么才能确定它们不会绝迹？

在这一章结束的时候，我们便会对这一点确定无疑了。首先，请你注意素数的一个值得一提的简单“规律”——除了2和3以外的每一个素数，都与一个6的倍数相邻。换句话说，在这两个数之后的每一个素数，都是像6n±1这样的形式，这里n是某个确定的数。（记住6n是6×n的缩写，符号“±”的意思是加或减。）原因很好理解，每个数都一定可以写成以下6种形式中的一种：6n，6n±1，6n±2，6n＋3，因为没有数与6的某个倍数距离超过3。例如，17=(6×3)-1，28=(6×5)-2，57=(6×9)-3。事实上，这6个形式的数是循环出现的，这意味着当你写下任意6个连续的数，6种形式每个都会出现且仅出现1次。在这之后它们会一遍又一遍地循环出现，并且出现的顺序总是相同的。很显然6n和6n±2形式的数都是偶数。而任何形如6n＋3的数都可以被3整除。因此，除了2和3，只有形如6n±1的数可能是素数。如果6n±1两者都是素数，这种情况恰好对应于孪生素数：比如(6×18)±1给出一对数107和109，我们在第1章中提到过它们。你可能会猜测每对6n±1中至少有1个是素数——这对于100以下的素数来说的确是对的，但往后不远就存在着第一个例外：(6×20)-1=119=7×17，(6×20)＋1=121=11×11。当n=20时，这两个数都不是素数。

素数之所以重要，主要是因为每个数都可以写成一系列素数的乘积，并且这么做的方法本质上只有一种。为了找到这个特别的分解，我们只须用某种方法分解这个给定的数，接着继续分解在因数中出现的合数，直到这样的分解不能再继续为止。比如，我们可以说120=2×60，接着继续将合数因数60分解：

120=2×60=2×(2×30)=2×2×(2×15)

=2×2×2×3×5。

我们说120的素因数分解（prime factorization）为23×3×5，当然我们也可以用另一种途径得到这个结论。比如：

120=12×10=(3×4)×(2×5)

=[3×(2×2)]×(2×5)。

但如果将素因数从小到大重新排列，我们依然得到了与之前相同的结果：120=22×3×5。

至少在上面这个例子中分解的唯一性是真的。你可能或多或少已经熟悉数的这一性质，但是如何保证这个结论适用于每一个数？任何数都可以分解为素数的乘积，这已经足够清楚了。但是，一般来说有不止一种办法可以完成这个任务。那么我们如何确定这个过程总能给出相同的最终结果呢？这是一个重要的问题，因此我将花上一点儿时间概述一下推理的过程，从而使我们能绝对信赖这个结论的正确性。这个结果来自素数的一个特殊性质，我们叫它欧几里得性质（Euclidean property）：假设有一个由两个或更多数相乘得到的积，如果一个素数是该乘积的一个因数，那么它也是构成这个乘积的某个因数的因数。比如，7是8×35=280（也可以看作乘积280=7×40）的一个因数，同时我们注意到7也是35的一个因数。这个性质刻画了素数的特征，因为没有合数能够保证同样的结论成立。例如，我们可以看出6是8×15=120（也可以看作120=6×20）的一个因数，6却不是8或15的因数。

素数总是拥有以上性质，这一事实可以用被称为欧几里得算法[1]（Euclidean algorithm）的推理来证明。我们将在第4章解释这个算法。如果我们暂且相信这个结果，那么就不难解释为什么不存在一个数拥有两个不同的素因数分解。假设存在拥有两个不同素因数分解的数，那么就存在一个最小的这样的数，让我们用n表示它。n有两种素因数分解。当把n的素因数从小到大排列的时候，这两个分解不相同。我们要证明这是矛盾的，因而假设一定为假。

值得一提的是，如果我们把数1包括在素数里，素因数分解的唯一性将不再成立。这是因为我们可以将1的任意幂次方乘上一个分解式，最后的积保持不变。这表明1和素数们有着本质上的不同。基于此，把1排除在素数的定义之外是正确的。

欧几里得：素数的无穷性

让我们回到这个问题：我们怎么知道素数无穷无尽，没有办法找到最大的素数？如果有人声称101是最大的素数，你即刻便能反驳他，因为你可以证明103没有因数（除了1和103以外），因此103是一个更大的素数。接下来你的朋友可能会承认自己大意了，他应该说103是所有素数中最大的。这时候你还可以指出107也是一个素数，从而再次表明他错了。然而你的朋友可能还是执迷不悟，他搬出你们所知的最大的素数。他甚至可能退一小步，承认自己并不知道最大的素数是多少，却继续说他很确定有这么一个数。

解决这个问题最好的方法是：对于任何假想的有限的素数集合，证明我们都能给出一个不在这个集合中的新的素数。比方说，如果有人号称在某个位置存在一个最大的奇数。你可以反驳说，假如n是奇数，那么n＋2是一个更大的奇数，因而不可能有一个最大的奇数。然而，这个方法对于素数来说可就不那么简单了——给定一串有限的素数，我们没有办法使用这个集合来造出一个素数，并且表明它比集合中所有的数都大。那么，或许真的有一个最大的素数？我们怎么才能知道那位固执的朋友是不对的呢？

欧几里得是知道的。约公元前300年，希腊有个数学家叫亚历山大里亚的欧几里得（Euclid of Alexandria）。他就是一切作为定语使用的词“欧几里得”（Euclidean）本人。从给定一个集合p1，p2，…，pk（其中每个pi表示一个不同的素数），他也没能找到生成一个新的素数的途径，于是他退回一步，找到了一个更加微妙的论证方法。他证明了在某个给定的数的范围内，总是存在一个或更多的新素数（但他的论据并不足以让我们在那个范围内精确地定位素数）。

他的证明如下：设p1，p2，…，pk为前k个素数。考虑比所有这些素数的积还大1的数n，即n=p1p2…pk＋1。n要么是一个素数，要么可以被一个小于它自身的素数整除。如果是后一种情况，这个素因数不可能是p1，p2，…，pk中的任意一个。因为假设p是p1，p2，…，pk中任意一个数，将n除以p会有余数1。于是可推知n的任何素因数都会是一个新的素数，并且比p1，p2，…，pk里面所有的素数都大，但不超过n自己。特别是，由此可知不存在任何包含所有素数的有限的列表，因而素数数列会不断延续下去，永不终结。欧几里得关于素数无穷性的证明是永恒不朽的，是数学中最受敬仰的证明之一。

虽然欧几里得的推理没有确切地说明在哪里能找到下一个素数，但现在我们对素数出现的频率已经有了深入的理解。例如，如果我们任意取两个没有公因数的数，比如a和b，并考虑数列a，a＋b，a＋2b，a＋3b，…，德国数学家约翰·狄利克雷（Johann Dirichlet，1805——1859）证明这样一个数列包含无穷多个素数。（当然，如果a和b有公因数——比方说d，这就没有希望成立了。因为如此一来，列表里每一个成员都是d的倍数，因而不是素数。）当a=1，b=2时，我们得到由奇数组成的数列。由欧几里得的证明，我们知道它包含无穷多素数。实际上，通过对欧几里得的方法进行一些十分简单的改进，还可以证明其他一些特殊情况，比方说以下形式的数列：3＋4n，5＋6n，5＋8n（n依次取1，2，3，…），它们各自都含有无穷多素数。但是，要证明狄利克雷的一般结论就非常难了。

另一个可以简单陈述的结果是，对于任意给定的数n(n≥2)，至少存在一个素数大于n但小于2n。这在历史上被称为伯特兰猜想[2]（Bertrand's postulate），它可以用非常基本的数学知识来证明，虽然这个证明本身有些取巧。我们可以使用下面列出的素数，对取值不大于4000的n验证这个论断。首先观察到这个列表中位于打头的素数2之后的每个数都小于前一个数的2倍：

2，3，5，7，13，23，43，83，163，317，631，1259，2503，4001。

对于每个不大于4000的n，取上表中不超过n的最大素数p，它的后面一个素数q即位于n〈q〈2n的范围中。这就保证了伯特兰-切比雪夫定理对于不大于4000的所有n都是成立的。例如，当n=100，p=83，那么q=163〈2×100。再使用一条巧妙的论证，这个论证涉及中央二项式系数（central binomial coefficient，将在第5章中介绍），还可以证明这个定理对大于4000的n也是正确的。

然而，我们不用走太远，就又会发现似曾相识却尚未解决的问题。举例来说，没有人知道是不是在两个连续的平方数中间总存在着一个素数。另一个观察是似乎存在足够的素数，从而可以保证每个大于2的偶数n总可以写成两个素数之和（哥德巴赫猜想，Goldbach’s conjecture）。对于n小于1018的情况，这个结论已经被直接验证。自然，我们可能会寄希望于沿着伯特兰-切比雪夫定理的思路找到一个证明。在大于某个给定的整数N时，基于对素数分布的已有知识，我们试图证明：对于任何偶数2n≥N，至少存在一对素数p，q，构成方程p＋q=2n的解。这个途径迄今还没能成功，不过这些思路产生了一些弱一点的结果。比如，1939年之后我们知道了：每个足够大的奇数是至多三个素数的和；每个偶数是不超过300 000个素数的和。但要想完整地证明哥德巴赫猜想，似乎还有很长的路要走。

还有一个简单的结果，颇有一些上面介绍的这类论断的味道。它说的是：存在一个小于40亿的数n，有10种不同的方法，可以将它写成4个不同的立方数之和。已知1729=13＋123=93＋103是最小的能用两种方法写成两个立方数之和的数。不过，要想知道一个数n存在，我们并不一定非要确定它的大小。有时候可以明确地知道一个问题有解，而不是精准地找到一个解。

在这个例子中，我们先指出如果取4个不同的数，它们都不大于一个固定的数m，那么求它们的立方和，结果将小于4m3。同时，倘若m=1000，那么通过简单的计算就可以发现，选4个不同的数求其立方和，所有可能的情况已经超过了4m3×10种。由此可推出存在某个数n≤4m3=4 000 000 000一定可以写成4个立方数的和，且至少有10种不同的写法。具体的计算涉及二项式系数（将在第5章中介绍），但并不困难。

数论中最著名的悬而未决的问题是黎曼猜想[3]（Riemann Hypothesis），要阐述它必须用到复数（complex number）——我们还没有介绍到。在这里提到它，是因为可以通过素因数分解的唯一性，重新表述这个问题的对象，使得新的提法中出现了一个包含所有素数的无穷乘积。借助这个表述我们发现，这个猜想表明，素数整体上的分布符合一条规律，那就是在大范围内，素性的出现是随机的。当然，某个数是否为素数不是一个随机事件。猜想里说的是，就很大的范围而言，素性是随机显现的，没有任何其他的规律或者结构可循。很多数论学家衷心希望，在其有生之年，这条有150年历史的猜想能有个定论。

素数是一个极其自然的数列，以至于我们会无法抗拒地去搜寻它们的规律。然而，不存在有关素数的真正有用的公式。也就是说，没有已知的规则能够生成所有的素数，甚至无法计算出一个完全由不同的素数组成的数列。存在一些形式简洁的公式，但几乎没有实用价值，要计算其中一些的值甚至需要素数相关的知识，因此本质上它们算是作弊。形如n2＋n＋41的表达式称作多项式（polynomial），这一个多项式能够产生极其大量的素数。例如，让n依次取值1，7和20，会分别得出素数43，107和461。确实，输入n=0到n=39，这一表达式的输出都是素数。但当取n=41时，这个多项式就令我们大失所望了，因为结果会有因数41。并且，对于n=40也失败了，因为

402＋40＋41=40 (40＋1)＋41

=40×41＋41=(40＋1)41=412。

可以轻而易举地证明，一般而言没有某个多项式能给出一个素数的公式，即便允许表达式中存在高于2的幂次也不行。

的确有可能设计出仅用一两句话描述的素性检验的方法。但是，想要它们有用，还需要再快捷一点，至少在某些情况下得快于第1章中描述的直接验证方法。一个有名的结论叫作威尔逊定理（Wilson's theorem）。它的表述使用到了一类叫作阶乘（factorials）的数，我们将在第5章里再次与它相见。数n!读作“n的阶乘”，就是所有不大于n的正整数的乘积。比如，5!=5×4×3×2×1=120。威尔逊定理便是一条极其简洁的陈述：当且仅当p是1＋(p-1)!的一个因数时，数p为素数。

证明这个结果不是很困难，实际上，其中的一个证明方向是很明显的：如果p是合数，比如p=ab，那么由于a和b都比p小，它们都会是(p-1)!的因数，因而p也是这个阶乘的一个因数。由此推出，当我们用1＋(p-1)!除以p时，会得到余数1。（a=b的情况需要多考虑一点点。）这很容易让人想起欧几里得对素数无穷性的证明。于是可知，如果p是1＋(p-1)!的一个因数，那么p必为素数。反过来的结论证明起来会难一点：如果p是素数，那么p是1＋(p-1)!的一个因数。但这才是定理真正令人惊讶的方向。读者朋友可以轻松地验证一些特殊情况，比如，素数5确实是 1＋4!=1＋24=25的一个因数。

最后，基于定义，阶乘含有很多因数。我们可以利用这一点证明，不存在仅含素数的算术数列[4]（arithmetic sequence），或者说仅含素数且形如a，a＋b，a＋2b，a＋3b，…的数列。因为可以证明相邻素数的间距可以任意地大，而前述数列相邻元素之差始终固定为b。想要理解这一点，考虑由n个连续整数构成的数列：

(n＋1)!＋2，(n＋1)!＋3，(n＋1)!＋4，…，

(n＋1)!＋n＋1。

这些数每个都是合数，因为第一个可以被2整除（两项都含有因数2），第二个可以被3整除，下一个可以被4整除，以此类推，直到最后一个——含有因数n＋1。因而对于任意给定的n，我们都有一串由n个连续整数组成的数列，其中的每一个数都不是素数。

在下一章中，我们将不再聚焦于具有最少因数的数（素数），而是转向拥有很多因数的数。不过我们会发现，它们和一些非常特殊的素数之间存在着令人惊讶的联系。

[1]　在中国一般称之为辗转相除法。

[2]　该猜想由伯特兰提出，后由切比雪夫证明，故称“伯特兰-切比雪夫定理”。约瑟夫·伯特兰（Joseph Bertrand），法国数学家。巴夫尼提·列波维奇·切比雪夫（Pafnuty Lvovich Chebyshev），俄罗斯数学家。

[3]　格奥尔格·弗雷德里希·波恩哈德·黎曼（Georg Friedrich Bernhard Riemann），德国数学家。

[4]　即等差数列。