02 永無窮盡的素數 The Unending Sequence of Primes

鑲嵌在數的拚圖中的素數

我們怎樣才能確定素數不會越來越稀少，最終逐漸消失殆盡呢？你可能會認為由於有無窮多自然數，而每一個都可以被分解為素數的乘積(這一點我們一會兒仔細解釋)，那麽必然得有無窮多個素數才能承擔這一工作。雖然這個結論是正確的，但它並不能從上述觀察中得出。這是因為如果我們從有限個素數開始，僅使用這些給定的素因數，我們就能製造出無窮多不同的數。確實如此，任何單個素數都有無窮多個冪次。比如，素數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=23×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)證明這樣一個數列包含無窮多個素數。(當然，如果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，有十種不同的方法，可以將它寫成四個不同的立方數之和。已知1729=13+123=93+103是最小的能用兩種方法寫成兩個立方數之和的數。不過，要想知道一個數n存在，我們並不一定非要確定它的大小。有時候可以明確地知道一個問題有解，而不是精準地找到一個解。

在這個例子中，我們先指出如果取四個不同的數，它們都不大於一個固定的數m，那麽求它們的立方和，結果將小於4m3。同時，倘若m=1000，那麽通過簡單的計算就可以發現，選四個不同的數求其立方和，所有可能的情況已經超過了4m3×10種。由此可推出存在某個數n≤4m3=4 000 000 000一定可以寫成四個立方數的和，且至少有十種不同的寫法。具體的計算涉及二項式係數(將在第5章中介紹)，但並不困難。

數論中最著名的懸而未決的問題是黎曼猜想[3](Riemann Hypothesis)，要闡述它必須用到複數(complex number)——我們還沒有介紹到。在這裏提到它，是因為可以通過素因數分解的唯一性，重新表述這個問題的對象，使得新的提法中出現了一個包含所有素數的無窮乘積。借助這個表述我們發現，這個猜想表明，素數整體上的分布符合一條規律，那就是在大範圍內，素性的出現是隨機的。當然，某個數是否為素數不是一個隨機事件。猜想裏說的是，就很大的範圍而言，素性是隨機顯現的，沒有任何其他的規律或者結構可循。很多數論學家衷心希望，在其有生之年，這條有150年曆史的猜想能有個定論。

素數是一個極其自然的數列，以至於我們會幾乎無法抗拒地去搜尋它們的規律。然而，卻不存在有關素數的真正有用的公式。也就是說，沒有已知的規則能夠生成所有的素數，甚至無法計算出一個完全由不同的素數組成的數列。存在一些形式簡潔的公式，但幾乎沒有實用價值，要計算其中一些的值甚至需要素數相關的知識，因此本質上它們算是作弊。形如n2+n+41的表達式稱作多項式(polynomials)，這一個多項式能夠產生極其大量的素數。例如，讓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)。它的表述使用到了一類叫作階乘(factorial)的數，我們將在第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]　即等差數列。