算術中的基石

德國偉大的數(shù)學家卡爾·弗里德里?！じ咚乖f：'數(shù)學是科學的皇后，而算術是數(shù)學的皇后。'高斯所說的算術這一數(shù)學分支，如今被命名為數(shù)論，即關于正整數(shù)或整數(shù)的研究。十九世紀數(shù)學家克羅內克有一句名言'上帝創(chuàng)造了整數(shù)，其余的一切則是人造的。'

數(shù)論的基本組成部分是質數(shù)。即諸如：2、3、5、7、11、13等不能被1以外的數(shù)整除的整數(shù)。質數(shù)無法被分解為更簡單的元素；它與數(shù)學的關系恰如元素與化學的關系。由100個左右的化學元素可以合成化學家們所研究的上百萬種化合物。歐幾里得證得算術的基本理論為：所有的正整數(shù)要么是質數(shù)，要么能被唯一地分解為一組質數(shù)。

若取小于 300 的質數(shù)，則共有 62 個：

2, 3, 5, 7, 11, 13, 17, 19, 23, 29,31, 37, 41, 43, 47, 53, 59, 61, 67, 7173, 79, 83, 89, 97, 101, 103, 107, 109, 113,127, 131, 137, 139, 149, 151, 157, 163, 167, 173,179, 181, 191, 193, 197, 199, 211, 223, 227, 229,233, 239, 241, 251, 257, 263, 269, 271, 277, 281,283, 293.

小于100的有25個，介于100與200的有21個，介于200與300的有16個。看上去質數(shù)會隨增大而稀少。如果選擇更大的數(shù)，我們會發(fā)現(xiàn)10,000和10,100之間僅有11個質數(shù)，100,000和100,100之間僅有6個。這似乎證明了質數(shù)的數(shù)量隨數(shù)值增大逐漸減少， 那么它們最終會消失嗎？ 我們知道，地球上沒有超過92-鈾的自然存在的元素。那么質數(shù)也適用同理嗎？最大質數(shù)是什么？

不存在最大的質數(shù)

早在古代，就有數(shù)學家開始研究質數(shù)的性質。古希臘人首先證明了質數(shù)的數(shù)量有無窮多，因此實際上不存在一個最大的質數(shù)。 歐幾里得的證明部分是已知的最古老的證明。

他通過假設存在最大的質數(shù)，從而得出矛盾，借用反證法進行證明。 我們給所有質數(shù)以升序編號，則有P1=2, P2=3, P3=5以此類推。假設有n個質數(shù)，記最大質數(shù)為。現(xiàn)取Q為全體質數(shù)乘積加1，有

現(xiàn)在我們可以發(fā)現(xiàn)，Q除以以上任何一個質數(shù)，都有余數(shù)1，所以Q不能被以上的任何質數(shù)整除。但我們知道，任意正整數(shù)要么是質數(shù)，要么能被分解為一組質數(shù)。這就意味著，Q要么是質數(shù)，要么能被比更大的質數(shù)整除。與我們的為最大質數(shù)假設相矛盾，原假設不成立，故不存在最大質數(shù)。

質數(shù)是如何分布的？

我們知道質數(shù)的數(shù)量隨數(shù)值增大而減少，但它們不會逐漸消失。那下一個問題便是，我們能否得知質數(shù)的分布？質數(shù)是否像化學元素排列在元素周期表上那樣符合某種分布？這是整個數(shù)學界的重要問題之一。

質數(shù)之間的間距看上去呈無規(guī)則變化，但正如上文所列呈現(xiàn)出不斷增大的趨勢，。質數(shù)定理表明函數(shù)x/ln(x)所得為小于x的質數(shù)個數(shù)的近似值，其中l(wèi)n(x)為x的自然對數(shù)，我們用π(x)表示小于x的質數(shù)的實際個數(shù)，隨著x的增大，近似值逐漸趨近于實際值。下表為兩個函數(shù)之間的比較：

沒有一個簡單的公式能夠歸納所有的質數(shù)，但歐拉得出了一個具有代表性的公式：

因為對于每個整數(shù)n，函數(shù)值都大于等于40的質數(shù)，輸出的質數(shù)有：

41, 43, 47, 53, 61, 71, 83, 97, 113, 131,151, 173, 197, 223, 251, 281, 313, 347, 383, 421,461, 503, 547, 593, 641, 691, 743, 797, 853, 911,971, 1033, 1097, 1163, 1231, 1301, 1373, 1447, 1523, 1601.

該公式不可避免地在n=41時無法輸出質數(shù)，因為此時不可避免的由下式得出結論來。

此外，歐拉還提出了一個更重要的函數(shù)，即現(xiàn)在我們所知的ζ函數(shù):

歐拉給出了ζ函數(shù)的無窮項積形式

其中的積包含所有的質數(shù)p。從而可知一個明顯的結論：當該函數(shù)表示為無窮項和時，和的通項取所有正整數(shù)，但當該函數(shù)表示為無窮項積時，積的通項只取所有質數(shù)。

歐拉把該函數(shù)定義在s>1時有效。在定義域內，即使和包含無數(shù)項，但總收斂于某個值。然而，當s<=1時，這一系列項的和卻是分散的，從而導致函數(shù)難以定義。比如，取s=-2時有

每一項都在無窮無盡地增大。相比之下，取s=2有

可以求和得

黎曼ζ函數(shù)

波恩哈德·黎曼在1859年發(fā)表了他在數(shù)論方面唯一的論文。論文中黎曼論述了一個函數(shù)，當s>1時，該函數(shù)與歐拉ζ函數(shù)完全相同，但黎曼的函數(shù)能夠定義在全體實數(shù)上。實際上黎曼ζ函數(shù)是定義于復數(shù)s上的，其中 s=a+b i，且 i2=-1。

黎曼證得他的解析連續(xù)ζ函數(shù)與質數(shù)分布有著密切聯(lián)系。他驚人的直覺使得他將連續(xù)復變函數(shù)的性質與質數(shù)那實數(shù)與獨立的性質聯(lián)系在一起。更具體地說，黎曼說明了π(x)與ζ函數(shù)的零點的關系，其中π(x)是比x小的質數(shù)。黎曼發(fā)現(xiàn)當s取實數(shù)時，即便是取負整數(shù)，如s=-2,-4,-6,…ζ函數(shù)均為零，但黎曼同樣發(fā)現(xiàn)了函數(shù)的其它零點都出現(xiàn)s=1/2+bi直線上。其中第一個零點大約在b=14.134725處。黎曼猜測ζ函數(shù)的所有的非實數(shù)零點都在s=1/2+bi上，雖然他尚不能證明這一點。這個猜想很快成為人盡皆知的黎曼猜想，并成為了理解質數(shù)分布的關鍵。最近，由計算機算得至少前1000億個非實數(shù)零點s全都落在黎曼猜想的線上。但是，到目前為止，仍未證得這個猜想沒有例外。

英國的數(shù)論數(shù)學家G.H.哈代在他的書《一個數(shù)學家的自白》中講到，他在20世紀20年代從丹麥跨國南海返航啟程之前留了一張紙條給同事，里面寫著自己已經證明了黎曼猜想，他預料到航行的危險。盡管是一個堅定的、并致力于勸服別人的無神論者，哈代解釋道他寫那張紙條的目的是希望上帝能夠保佑他不會淹死。因為假若他淹死了，就意味著數(shù)學家生前聲稱已證明了，卻在與別人討論證明之前就離世的著名數(shù)學問題有兩個，即費馬大定理與黎曼猜想。費馬大定理早已在數(shù)學界中名聲顯赫。17 世紀法國的律師兼業(yè)余數(shù)學家皮埃爾·德·費馬，也是數(shù)論歷史上的名人之一。他在閱讀關于丟番圖《算術》所著《頁邊筆記》中此命題旁邊寫道：

將一個立方數(shù)分成兩個立方數(shù)之和，或一個四次冪分成兩個四次冪之和，或者一般地將一個高于二次的冪分成兩個同次冪之和，這是不可能的。關于此，我確信我發(fā)現(xiàn)了一種美妙的證法，可惜這里的空白處太小，寫不下。

而在費馬去世之后，數(shù)學家們用了 350 年的努力，才把猜想變成這個定理。

數(shù)學界最難的問題？

自從黎曼發(fā)表論文的150年間都沒有人能證明或證偽他的猜想，但費曼大定理最后在1994年被安德魯·懷爾斯成功證明。黎曼猜想是當今數(shù)學界最著名和最杰出的問題。同時相比于費曼大定理，黎曼猜想有著更深遠的數(shù)學意義。實際上，許多數(shù)學家在假定黎曼猜想正確的基礎上發(fā)展了許多數(shù)學領域。黎曼猜想看上去也比費曼大定理更難解。

所有編碼在ζ函數(shù)中模模糊糊的質數(shù)規(guī)律仍未被清晰地破解。但是黎曼猜想展示了一個關于質數(shù)的更明顯的規(guī)律。1963年，一位在美國專攻原子核項目、曾參與曼哈頓計劃的波蘭數(shù)學家塔尼斯拉夫·烏拉姆在二戰(zhàn)期間的參與了一個會議，他在會議的研討會期間心不在焉地隨手亂畫。畫了一個正方形的網格圖，然后在網格圖的中央標記1，接著以螺旋形往外的方向按遞增順序標記了其他的正整數(shù)。烏拉姆十分驚喜地注意到：當他以這種方式排列整數(shù)時，在網格圖的對角線上整齊地排列著質數(shù)。

這個結果太過出乎預料，以至于質數(shù)螺旋的圖片登在了《科學美國人》雜志1964年3月期的封面，同時雜志中刊載了馬丁·加德納的文章《Mathematical Recreations: The Remarkable Lore of the Prime Number.》。

上圖展示了的螺旋僅包含前100,000個整數(shù)。復合數(shù)表示為黑點，質數(shù)表示為白點。可以在網格圖中清晰地看到大量的白色對角線。即使用除1以外的其他數(shù)作為螺旋的起始點，也會有同樣的現(xiàn)象。沒人能對此提出一個清晰的解釋。但這暗示著有很長一系列的質數(shù)能被函數(shù) f(n)=an2+bn+c生成，其中a、b和c均為整數(shù)。

如果我們把41作為螺旋中央的起始數(shù)，我們將發(fā)現(xiàn)對角線上的數(shù)字恰符合歐拉發(fā)現(xiàn)的公式f(n)=n2-n+41；正如前文所述，對于n取每個正整數(shù)，函數(shù)都有大于40的質數(shù)。

在插圖里，41位于螺旋的中央，其它整數(shù)繞螺旋的逆時針方向排列。方格圖中的復合數(shù)格子標為黃色，質數(shù)格子標為白色。 f(n)=n2-n+41輸出的前15個數(shù)沿方格圖的其中一條對角線排列。

數(shù)字的漩渦

雖然塔尼斯拉夫·烏拉姆因質數(shù)螺旋的發(fā)現(xiàn)而受到普遍的贊譽，但是他可能不是第一發(fā)現(xiàn)人。亞瑟C.克拉克1956年的經典小說《城市與群星》的第六章的開頭是英雄杰賽拉克一邊分析著電腦屏幕里的整數(shù)'漩渦'，一邊看著質數(shù)像珠子一樣近乎整齊地排列在網的交織點。似乎在烏拉姆發(fā)現(xiàn)質數(shù)螺旋的七年前，亞瑟C.克拉克就已經發(fā)現(xiàn)了。

數(shù)學家們出于自己的樂趣而研究質數(shù)的性質。但質數(shù)有其現(xiàn)代科學的應用，尤其在加密領域上。美國政府情報局NSA是理論數(shù)學家在世界上最大的雇主。無論何時你在互聯(lián)網上進行一筆交易，比如信用卡購物，都會使用公鑰加密確保你的交易安全，這就是著名的RSA加密算法，它是由羅納德·李維斯特、阿迪·薩莫爾和倫納德·阿德曼基于精妙的數(shù)論發(fā)明的。

RSA加密算法用的是由兩個很大的質數(shù)相乘得到的數(shù)字密鑰。這個系統(tǒng)的安全性取決于分解大量數(shù)據的難度。使用已知的所有算法去分解大量數(shù)據所需步驟數(shù)隨數(shù)字大小呈指數(shù)級增長。這意味著密碼學家總會領先于計算機一步。若計算機處理器能足夠快地分解用于編碼的128位數(shù)字，我們就可以開始采用512位。然而，如果一個數(shù)學家找到一種新的更高效率的分解算法，我們的編碼交易安全將會遭到威脅。但密碼學家依舊認為當前的算法是安全的，因為盡管許多世紀以來數(shù)學家一直尋求破解的算法，但從未成功過。

去年三位印度數(shù)學家——馬寧德拉·阿格拉沃教授和他的兩位畢業(yè)學生尼拉吉·凱亞爾和尼廷·薩克塞納——發(fā)表了一個檢驗一個數(shù)是質數(shù)或復合數(shù)的算法。這個算法運用的是非?；镜倪\算并且作者的代碼只有13行。這個算法有一個重要的新功能是測試數(shù)字N是否為質數(shù)所用時間是N的線性級而非指數(shù)級。實際上，這一時間為N的12倍。隨著這一算法的出現(xiàn)，也許我們不應該過于草率地排除存在著一個簡單的分解算法卻被忽略的可能性。也許密碼學家應該開始感到擔憂了。

原文作者，Nick Mee ，本文原載于+plus magazine網站

翻譯作者，劉雄威，[遇見數(shù)學]翻譯小組核心成員