03 完美的和不那麽完美的數 Perfect and Not So Perfect Numbers

數的完美性

對於取值小的數，我們通常能輕易找到特殊的性質來刻畫它們，比如，3是唯一等於之前所有數之和的數，而2是僅有的偶素數(這使得它成為最怪異的素數)。6這個數有個獨一無二的性質，它既是所有小於自身的因數的和，也是它們的乘積：6=1+2+3=1×2×3。

畢達哥拉斯學派(Pythagoreans)將6這樣的數稱作完美的[1](perfect)，意思是這個數是其所有真因數之和。對於一個數，我們把嚴格小於這個數本身的因數叫作它的真因數。這種完美性著實非常罕見。前5個完美數是6， 28， 496， 8128和33 550 336。對於這些偶的完美數我們已經了解了很多，然而直至今日，依然沒有人能回答古代人提出的基本問題，即是否有無窮多個這類特殊的數。另外，沒有人找到過一個奇的完美數，也沒有證明其不存在。任何奇完美數必然極其地大，並且由於奇完美性，這個數必須滿足一長串特殊的性質。但是，所有這些限製條件還不足以排除這樣一個數存在的可能——可以想象，這些特殊性質會引導我們去搜尋還未曾現身的第一個奇完美數，它可能隻是在等著被發現。

歐幾裏得早就發現，偶完美數與一列非常特殊的素數有緊密的聯係。它們被稱為梅森素數(Mersenne primes)，是以17世紀的法國教士馬蘭·梅森(Marin Mersenne)命名的。

梅森數(Mersenne number)是形如2p-1的數，這裏的p是一個素數。舉個例子，如果你取前四個素數2，3，5和7，那麽可以看出前四個梅森數是：3，7，31和127。讀者朋友可以很快驗證它們都是素數。如果p非素，比方說p=ab，那麽m=2p-1當然也不是素數，因為可以驗證在這種情況下m含有因數2a-1。倘若p為素，則對應的梅森數常常是素數，至少在我們看來是這樣的。

早在公元前300年，歐幾裏得就闡釋過：一旦你有一個素的梅森數，那麽就存在一個與之對應的完美數，即P=2p-1(2p-1)。讀者朋友可以迅速驗證，前四個梅森素數確實給出上麵所說的前四個完美數。例如，用第三個素數5作為種子，我們得到完美數P=24(25-1)=16×31=496，即前述列表裏第三個完美數。P的因數是直到2p-1的2的各次冪，以及這些數乘上素數2p-1。現在剩下要做的就隻是一項練習了：將所謂的幾何數列(geometric series，將在第5章中解釋)求和，以便檢查P的真因數之和確實是P。

在18世紀，偉大的瑞士數學家萊昂哈德·歐拉(Leohard Euler)進一步地證明了上述論斷的逆命題，即每一個偶完美數都屬於這一類型。這樣，歐幾裏得和歐拉共同建立了一個梅森素數和偶完美數之間的一一對應關係。可是自然地，下一個問題出現了：所有的梅森數都是素數嗎？很遺憾，並非如此。失敗僅咫尺之遙，因為第五個梅森數等於211-1=2047=23×89。的確，我們甚至不知道梅森素數的數列是否會終結——也許最終，在某個點之後所有的梅森數都是合數。

盡管如此，梅森數依然是素數的天然候選，因為可以證明，一個梅森數m的任何真因數——假如存在的話——擁有2kp+1這樣的特定形式。比如，當p=11，借助這個結論，我們隻需檢驗被形如22k+1的素數除的情況。這兩個素因數23和89，分別對應於值k=1和k=4。這個關於梅森數因數的事實還帶來一個意外之喜，它提供第二種方法，使我們看出一定存在無窮多素數。因為它表明，2p-1的最小素因數大於p，因而p不可能是最大的素數。由於這適用於任意素數p，我們可以推斷不存在最大的素數，於是素數數列可以永遠延續下去。

不那麽完美的數

傳統上人們對數的認識往往集中在單個數上，這些數被認為有特殊的甚至是奇妙的性質，就比如說完美數。不過，220和284是一對擁有類似特征的數。它們是第一對相親數[3](amicable pair)，意思是每個數的真因數之和等於另一個——這是推廣到數對的一種完美性。法國著名的業餘數學家皮埃爾·德·費馬(Pierre de Fermat)找到了其他的相親數，如17 296和18 416，而歐拉更是發現了好幾十對。出人意料的是，他們都漏掉了一對小數，1184和1210，這是由16歲的尼可羅·帕格尼尼(Nicol吀 Paganini)在1866年發現的。當然，我們還可以走得比數對更遠一些，去尋找完美的三元數組、四元數組等。更長的循環比較罕見，但仍會出現。

我們可以從任何數出發，找到它真因數之和，接著繼續重複這一過程，從而得到所謂的真因數和數列(aliquot sequence)。結果通常是令人失望的，因為我們一般會得到一條迅速抵達1的鏈，然後這個過程就終止了。舉例說，即便是從一個看起來很有希望的數開始，比如12，鏈條還是很短：

12→(1+2+3+4+6)=16→(1+2+4+8)=15

→(1+3+5)=9→(1+3)=4→(1+2)=3→1.

困難在於，一旦你碰上一個素數，就結束了。完美數當然是例外，它們都會給我們一個循環，而相親數則給我們一個雙循環：220→284→220→…。

能產生超過兩個元素的循環的數叫作多親的(sociable)，相關研究直到20世紀才開始，因為那之前它們從沒有被人發現過。甚至今天，還沒有生成三元環的多親數被找到，雖然現在已經知道了120個四元環數鏈。最早的一些例子是由P·普萊(P. Poulet)在1918年找到的。第一個是一個五元環數鏈：

12 496→14 288→15 472

→14 536→14 264→12 496.

普萊的第二個例子令人驚歎，時至今日還沒發現其他能與之比肩的數鏈：從14 316開始，我們得到一個長度為28的循環。所有其他已知的循環長度均小於10。到今天，關於相親數和多親數，還沒有像歐幾裏得和歐拉關於完美數那樣漂亮的定理。不過，由於現代強大的計算能力，這類問題經曆了一次由數值實驗推動的複興，人們也得出了一些新的結論。

根據一個數的真因數之和是小於、等於，還是大於這個數本身，我們可以將所有數劃分為三類：虧的(deficient)、完美的(perfect)和盈的(abundant)。比如，就像我們已經看到的，12是一個盈數，18和24也是，因為它們的真因數之和分別為21和36。

在整數中進行初步的搜索，你可能由此猜測盈數也就是6的倍數而已。當然，任何大於6的形如6n的數都是盈的，因為6n的因數一定包含1， 2，3以及n， 2n， 3n，這些加起來大於原來的數6n。但是，這一觀察也可以被推廣到不僅限於6的倍數，因為我們可以將同樣的推理應用於任何完美數k。nk的因數將含有1，以及完美數k的所有因數乘上n所得出的數，於是nk的所有真因數加起來至少會得1+nk。所以，任何完美數的倍數都是盈的。例如，28是完美的，因而2×28 = 56， 3×28 = 84等都是盈的。

因此我們看到，完美數的倍數是盈數，同樣的道理，盈數的倍數也一樣。發現了這一點之後，你或許仍然會猜測，所有的盈數隻是完美數的倍數。然而，你不用看太遠，就會找到這個猜想的第一個例外，70是盈的，但它的因數沒有一個是完美的。70是第一個所謂的奇異數(weird number)，不過不是因為上述原因(這個名字的源頭下麵會解釋)。

有了這些發現，你可能還會認為，因為似乎不存在奇完美數，所以很可能也不存在奇盈數。換句話說，進一步的猜想可能變成了所有奇數都是虧的。倘若計算前幾百個奇數的真因數和，似乎可以確證這一理論，但是這個說法最終還是被發現是錯的。檢驗一下945，它的真因數和為975。現在，洪水的閘門被打開了，因為一個盈數的任意倍數都是盈的，所以945的奇數倍立刻給我們提供了無窮多奇盈數。

比起不假思索地逐個檢驗奇數，要是我們再精明一點的話，可能會更快地發現這個反例。要想一個數有很大的真因數和，它需要很多因數，其中還要包含大因數，這些大因數又是由小因數配對在一起產生的。於是我們可以通過將小素數乘起來構造具有大真因數和的數。如果我們隻關心奇數，那麽我們應該看由前幾個素數——3，5，7等——構成的乘積。這個粗略的準則會很快使你檢驗到33×5×7=945，於是你也就在奇數中找到了盈性。

有時我們會發現，具有某些性質的數裏，最小的也有很大的值，這種情況並不少見。尤其是當想找的數需要有某種因數結構，這種結構是由你想要的性質決定的。於是那個最小的數可能極其大，不過如果我們在求解過程中利用給定的性質的話，它並不一定很難找到。這種數謎的一個例子是找到一個數，它既是一個立方數的5倍，又是一個五次方數的3倍。答案是

7 119 140 625=5×11253=3×755.

不過，並不難看出，為什麽最小的答案都有數十億這麽大的值。任何解n都得是3r5sm這樣的形式，r和s是正冪次，剩下的素因數被歸總在整數m裏，m不能被3或5整除。如果我們首先關注r的可能取值，可以觀察到，由於n是一個立方數的5倍，指數(exponent)r一定是3的倍數。同時由於n是一個五次方的3倍，數r-1必為5的倍數。同時滿足這兩個條件的最小r是r=6。同樣的，指數s一定是5的倍數，而s-1必須是3的倍數，最小的可行的s是s = 10。為了讓n越小越好，我們取m=1，因此n=36×510=3(3×52)5=3×755，於是n確實是一個五次方的3倍。同時n=5(32×53)3=5×11253，所以n也是一個立方數的5倍。

一個更極端的例子是著名的牛群問題(Cattle Problem)，它是由古代最偉大的數學家阿基米德(Archimedes)提出的。但直到19世紀這個問題才被解決。要滿足最初的44行詩中提出的所有限製條件，最小的牛群數量是一個超過200 000位的數!

上麵這些討論給了我們一條警示，那就是隻有我們進入非常大的數的領域，數才會展示出它們全部的多樣性。出於這個原因，僅僅是不存在少於300位的奇完美數這個事實，並不能說明它們“很可能”不存在。當然，假如真有一個出現了，這個領域內第一流的專家們也會大吃一驚。

讓我們再次回到真因數和數列的一般行為這個話題上。我們還可以提出一些簡單的問題，卻仍然沒有人回答得了。真因數和數列可能的情形有哪些？如果這個數列遇上一個素數，那麽在這之後它將立即終止於1，其實它也不會以任何其他方式終止。如果這沒有終止，這個數列可能是循環的，從而代表了一組多親數。但是，還有另外一種與之相關的可能性，我們可以通過計算95的真因數和來揭示：

95=5×19→(1+5+19)=25

=5×5→(1+5)=6→6→6→….

在這個例子裏，雖然95本身不是一個多親數，但它的真因數和數列最終碰到一個多親數(更準確地說是完美數6)，接著進入了一個循環。

可以設想，還存在一種可能性：一個數的真因數和數列永不遇見一個素數或多親數。此時，這個數列必然是一個由不同數組成的無窮數列，其中沒有一個是素的或多親的。這可能嗎？令人吃驚的是，沒人知道。更驚人的是，存在一些小的數，它們的真因數和數列竟然還是未知的(因此它們可能擁有此類無窮真因數和數列)。這些謎一樣的數中的第一個是276，它的真因數和數列由以下的數開始：

276→396→696→1104→1872→3770

→3790→3050→2716→2772→….

但是沒有人確切地知道它最後會變成什麽樣。

這與前麵列出的276的真因數和數列的第二項相等。

對於與真因數和函數具有某種關係的數n，隻需要通過給它們起個名字，我們便可以引入無窮多類的數。就像之前提到的，當a(n)=n時n是完美的，當a(n)＞n時n是盈的。一個半完美數(semiperfect number)n是等於自己部分真因數(小於n)之和的數，因而由定義可以推出，所有半完美數不是完美的就是盈的。比如，18是半完美的，因為18=3+6+9。當一個數是盈數但不是半完美的，它被稱作奇異的(weird)，最小的奇異數是70。

你可能會認為，這個話題變得過於瑣碎了——將名稱冠予任意定義的數的類型，這舉動確實不能讓數字變得有意思，我們應該懂得在什麽地方收手。話雖如此，要注意處理這些新問題背後的策略，還是歐幾裏得和歐拉展示給我們的關於完美數的那一套。回憶一下，歐幾裏得證明的是如果一個梅森數是素數，那麽另一個數就是偶的且是完美的。歐拉則證明了反過程，所有偶完美數都是由這一途徑產生的。在公元9世紀，波斯數學家塔比特·伊本·庫拉(Thabit ibn Qurra)對於任意數n引入了一個三元數組，如果數組裏的數都是素數，就可以構造一對相親數。塔比特的構造方法在18世紀被歐拉進一步推廣，但即便這個加強版公式似乎也隻能產生一部分相親數對，還有很多相親數不能由這個構造產生。(現在已知差不多1200萬對相親數。)到了現代，克拉維茨(Kravitz)給出了奇異數的一種基於素數的構造方法。這個公式成功找到了一個很大的有五十多位的奇異數。

本章和前一章是為了通過各種各樣的實例，讓讀者朋友熟悉自然數的因數和因數分解。自然數也叫作正整數(positive integers)。這將幫助你為下一章做好準備，你將了解那些思想如何被應用於當代密碼學(cryptography)——關於秘密的科學。

[1]　又稱完全數或完備數。

[2]　2018年12月21日，已知的最大素數已更新為282 589 933-1。有興趣的讀者可以參閱GIMPS項目官方網站 https://www.mersenne.org/。

[3]　又稱親和數、友愛數、友好數。

[4]　素數冪即單一素數的正整數次方。