算術(shù)中的基石

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

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

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

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個(gè)，介于100與200的有21個(gè)，介于200與300的有16個(gè)?？瓷先ベ|(zhì)數(shù)會(huì)隨增大而稀少。如果選擇更大的數(shù)，我們會(huì)發(fā)現(xiàn)10,000和10,100之間僅有11個(gè)質(zhì)數(shù)，100,000和100,100之間僅有6個(gè)。這似乎證明了質(zhì)數(shù)的數(shù)量隨數(shù)值增大逐漸減少， 那么它們最終會(huì)消失嗎？ 我們知道，地球上沒(méi)有超過(guò)92-鈾的自然存在的元素。那么質(zhì)數(shù)也適用同理嗎？最大質(zhì)數(shù)是什么？

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

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

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

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

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

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

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

沒(méi)有一個(gè)簡(jiǎn)單的公式能夠歸納所有的質(zhì)數(shù)，但歐拉得出了一個(gè)具有代表性的公式：

因?yàn)閷?duì)于每個(gè)整數(shù)n，函數(shù)值都大于等于40的質(zhì)數(shù)，輸出的質(zhì)數(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í)無(wú)法輸出質(zhì)數(shù)，因?yàn)榇藭r(shí)不可避免的由下式得出結(jié)論來(lái)。

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

歐拉給出了ζ函數(shù)的無(wú)窮項(xiàng)積形式

其中的積包含所有的質(zhì)數(shù)p。從而可知一個(gè)明顯的結(jié)論：當(dāng)該函數(shù)表示為無(wú)窮項(xiàng)和時(shí)，和的通項(xiàng)取所有正整數(shù)，但當(dāng)該函數(shù)表示為無(wú)窮項(xiàng)積時(shí)，積的通項(xiàng)只取所有質(zhì)數(shù)。

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

每一項(xiàng)都在無(wú)窮無(wú)盡地增大。相比之下，取s=2有

可以求和得

黎曼ζ函數(shù)

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

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

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

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

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

數(shù)學(xué)界最難的問(wèn)題？

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

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

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

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

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

在插圖里，41位于螺旋的中央，其它整數(shù)繞螺旋的逆時(shí)針?lè)较蚺帕?。方格圖中的復(fù)合數(shù)格子標(biāo)為黃色，質(zhì)數(shù)格子標(biāo)為白色。 f(n)=n2-n+41輸出的前15個(gè)數(shù)沿方格圖的其中一條對(duì)角線排列。

數(shù)字的漩渦

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

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

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

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

原文作者，Nick Mee ，本文原載于+plus magazine網(wǎng)站

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