卡爾·弗裡德裡希·高斯
德國偉大的數學家卡爾·弗裡德裡希·高斯曾說:"數學是科學的皇後,而算術是數學的皇後。"高斯所說的算術這一數學分支,如今被命名為數論,即關于正整數或整數的研究。十九世紀數學家克羅内克有一句名言"上帝創造了整數,其餘的一切則是人造的。"
數論的基本組成部分是質數。即諸如:2、3、5、7、11、13等不能被1以外的數整除的整數。質數無法被分解為更簡單的元素;它與數學的關系恰如元素與化學的關系。由100個左右的化學元素可以合成化學家們所研究的上百萬種化合物。歐幾裡得證得算術的基本理論為:所有的正整數要麼是質數,要麼能被唯一地分解為一組質數。
若取小于 300 的質數,則共有 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個。看上去質數會随增大而稀少。如果選擇更大的數,我們會發現10,000和10,100之間僅有11個質數,100,000和100,100之間僅有6個。這似乎證明了質數的數量随數值增大逐漸減少, 那麼它們最終會消失嗎? 我們知道,地球上沒有超過92-鈾的自然存在的元素。那麼質數也适用同理嗎?最大質數是什麼?
不存在最大的質數早在古代,就有數學家開始研究質數的性質。古希臘人首先證明了質數的數量有無窮多,因此實際上不存在一個最大的質數。 歐幾裡得的證明部分是已知的最古老的證明。
他通過假設存在最大的質數,從而得出矛盾,借用反證法進行證明。 我們給所有質數以升序編号,則有P1=2, P2=3, P3=5以此類推。假設有n個質數,記最大質數為。現取Q為全體質數乘積加1,有
現在我們可以發現,Q除以以上任何一個質數,都有餘數1,所以Q不能被以上的任何質數整除。但我們知道,任意正整數要麼是質數,要麼能被分解為一組質數。這就意味着,Q要麼是質數,要麼能被比更大的質數整除。與我們的為最大質數假設相矛盾,原假設不成立,故不存在最大質數。
質數是如何分布的?我們知道質數的數量随數值增大而減少,但它們不會逐漸消失。那下一個問題便是,我們能否得知質數的分布?質數是否像化學元素排列在元素周期表上那樣符合某種分布?這是整個數學界的重要問題之一。
質數之間的間距看上去呈無規則變化,但正如上文所列呈現出不斷增大的趨勢,。質數定理表明函數x/ln(x)所得為小于x的質數個數的近似值,其中ln(x)為x的自然對數,我們用π(x)表示小于x的質數的實際個數,随着x的增大,近似值逐漸趨近于實際值。下表為兩個函數之間的比較:
沒有一個簡單的公式能夠歸納所有的質數,但歐拉得出了一個具有代表性的公式:
因為對于每個整數n,函數值都大于等于40的質數,輸出的質數有:
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時無法輸出質數,因為此時不可避免的由下式得出結論來。
此外,歐拉還提出了一個更重要的函數,即現在我們所知的ζ函數:
歐拉給出了ζ函數的無窮項積形式
其中的積包含所有的質數p。從而可知一個明顯的結論:當該函數表示為無窮項和時,和的通項取所有正整數,但當該函數表示為無窮項積時,積的通項隻取所有質數。
歐拉把該函數定義在s>1時有效。在定義域内,即使和包含無數項,但總收斂于某個值。然而,當s<=1時,這一系列項的和卻是分散的,從而導緻函數難以定義。比如,取s=-2時有
每一項都在無窮無盡地增大。相比之下,取s=2有
可以求和得
黎曼ζ函數
波恩哈德·黎曼
波恩哈德·黎曼在1859年發表了他在數論方面唯一的論文。論文中黎曼論述了一個函數,當s>1時,該函數與歐拉ζ函數完全相同,但黎曼的函數能夠定義在全體實數上。實際上黎曼ζ函數是定義于複數s上的,其中 s=a b i,且 i²=-1。
黎曼證得他的解析連續ζ函數與質數分布有着密切聯系。他驚人的直覺使得他将連續複變函數的性質與質數那實數與獨立的性質聯系在一起。更具體地說,黎曼說明了π(x)與ζ函數的零點的關系,其中π(x)是比x小的質數。黎曼發現當s取實數時,即便是取負整數,如s=-2,-4,-6,…ζ函數均為零,但黎曼同樣發現了函數的其它零點都出現s=1/2 bi直線上。其中第一個零點大約在b=14.134725處。黎曼猜測ζ函數的所有的非實數零點都在s=1/2 bi上,雖然他尚不能證明這一點。這個猜想很快成為人盡皆知的黎曼猜想,并成為了理解質數分布的關鍵。最近,由計算機算得至少前1000億個非實數零點s全都落在黎曼猜想的線上。但是,到目前為止,仍未證得這個猜想沒有例外。
英國的數論數學家G.H.哈代在他的書《一個數學家的自白》中講到,他在20世紀20年代從丹麥跨國南海返航啟程之前留了一張紙條給同事,裡面寫着自己已經證明了黎曼猜想,他預料到航行的危險。盡管是一個堅定的、并緻力于勸服别人的無神論者,哈代解釋道他寫那張紙條的目的是希望上帝能夠保佑他不會淹死。因為假若他淹死了,就意味着數學家生前聲稱已證明了,卻在與别人讨論證明之前就離世的著名數學問題有兩個,即費馬大定理與黎曼猜想。費馬大定理早已在數學界中名聲顯赫。17 世紀法國的律師兼業餘數學家皮埃爾·德·費馬,也是數論曆史上的名人之一。他在閱讀關于丢番圖《算術》所著《頁邊筆記》中此命題旁邊寫道:
将一個立方數分成兩個立方數之和,或一個四次幂分成兩個四次幂之和,或者一般地将一個高于二次的幂分成兩個同次幂之和,這是不可能的。關于此,我确信我發現了一種美妙的證法,可惜這裡的空白處太小,寫不下。
而在費馬去世之後,數學家們用了 350 年的努力,才把猜想變成這個定理。
數學界最難的問題?
烏拉姆的質數螺旋
自從黎曼發表論文的150年間都沒有人能證明或證僞他的猜想,但費馬大定理最後在1994年被安德魯·懷爾斯成功證明。黎曼猜想是當今數學界最著名和最傑出的問題。同時相比于費馬大定理,黎曼猜想有着更深遠的數學意義。實際上,許多數學家在假定黎曼猜想正确的基礎上發展了許多數學領域。黎曼猜想看上去也比費馬大定理更難解。
所有編碼在ζ函數中模模糊糊的質數規律仍未被清晰地破解。但是黎曼猜想展示了一個關于質數的更明顯的規律。1963年,一位在美國專攻原子核項目、曾參與曼哈頓計劃的波蘭數學家塔尼斯拉夫·烏拉姆在二戰期間的參與了一個會議,他在會議的研讨會期間心不在焉地随手亂畫。畫了一個正方形的網格圖,然後在網格圖的中央标記1,接着以螺旋形往外的方向按遞增順序标記了其他的正整數。烏拉姆十分驚喜地注意到:當他以這種方式排列整數時,在網格圖的對角線上整齊地排列着質數。
這個結果太過出乎預料,以至于質數螺旋的圖片登在了《科學美國人》雜志1964年3月期的封面,同時雜志中刊載了馬丁·加德納的文章《Mathematical Recreations: The Remarkable Lore of the Prime Number.》。
螺旋的對角線上皆為質數
上圖展示了的螺旋僅包含前100,000個整數。複合數表示為黑點,質數表示為白點。可以在網格圖中清晰地看到大量的白色對角線。即使用除1以外的其他數作為螺旋的起始點,也會有同樣的現象。沒人能對此提出一個清晰的解釋。但這暗示着有很長一系列的質數能被函數 f(n)=an² bn c生成,其中a、b和c均為整數。
如果我們把41作為螺旋中央的起始數,我們将發現對角線上的數字恰符合歐拉發現的公式f(n)=n²-n 41;正如前文所述,對于n取每個正整數,函數都有大于40的質數。
在插圖裡,41位于螺旋的中央,其它整數繞螺旋的逆時針方向排列。方格圖中的複合數格子标為黃色,質數格子标為白色。 f(n)=n²-n 41輸出的前15個數沿方格圖的其中一條對角線排列。
數字的漩渦雖然塔尼斯拉夫·烏拉姆因質數螺旋的發現而受到普遍的贊譽,但是他可能不是第一發現人。亞瑟C.克拉克1956年的經典小說《城市與群星》的第六章的開頭是英雄傑賽拉克一邊分析着電腦屏幕裡的整數"漩渦",一邊看着質數像珠子一樣近乎整齊地排列在網的交織點。似乎在烏拉姆發現質數螺旋的七年前,亞瑟C.克拉克就已經發現了。
數學家們出于自己的樂趣而研究質數的性質。但質數有其現代科學的應用,尤其在加密領域上。美國政府情報局NSA是理論數學家在世界上最大的雇主。無論何時你在互聯網上進行一筆交易,比如信用卡購物,都會使用公鑰加密确保你的交易安全,這就是著名的RSA加密算法,它是由羅納德·李維斯特、阿迪·薩莫爾和倫納德·阿德曼基于精妙的數論發明的。
RSA加密算法用的是由兩個很大的質數相乘得到的數字密鑰。這個系統的安全性取決于分解大量數據的難度。使用已知的所有算法去分解大量數據所需步驟數随數字大小呈指數級增長。這意味着密碼學家總會領先于計算機一步。若計算機處理器能足夠快地分解用于編碼的128位數字,我們就可以開始采用512位。然而,如果一個數學家找到一種新的更高效率的分解算法,我們的編碼交易安全将會遭到威脅。但密碼學家依舊認為當前的算法是安全的,因為盡管許多世紀以來數學家一直尋求破解的算法,但從未成功過。
去年三位印度數學家——馬甯德拉·阿格拉沃教授和他的兩位畢業學生尼拉吉·凱亞爾和尼廷·薩克塞納——發表了一個檢驗一個數是質數或複合數的算法。這個算法運用的是非常基本的運算并且作者的代碼隻有13行。這個算法有一個重要的新功能是測試數字N是否為質數所用時間是N的線性級而非指數級。實際上,這一時間為N的12倍。随着這一算法的出現,也許我們不應該過于草率地排除存在着一個簡單的分解算法卻被忽略的可能性。也許密碼學家應該開始感到擔憂了。
原文作者,Nick Mee ,本文原載于 plus magazine網站
翻譯作者,劉雄威,[遇見數學]翻譯小組核心成員
,更多精彩资讯请关注tft每日頭條,我们将持续为您更新最新资讯!