素數隨想
（一）隨想的前奏
作為一個數學係學生，我應該算是一個曾經比較熱血的，一直喜歡那些關於數論、平麵幾何等各種與自然界相關聯的東西，直到畢業轉行了還是如此。
我的中學時代受宣傳陳景潤的影響，當然也是本色亦然，對數學可以說是熱愛，結果就在上大學時選擇了這個專業 – 我是被第一誌願錄取到數學係的。那時的人們還都比較理想化，就算是有務實的想法，也相信“學好數理化，走遍天下都不怕”那套說教。
上了大學後慢慢發現高級純理論的數學和自己的想象不太一樣，有點脫離自然世界，越來越抽象晦澀。但我比較懶，也比較皮實抗壓，挺了過來，懶得去轉換專業。
我的本科畢業論文搞得是調和分析（Harmonic Analysis）。那時因為家父病危，需要回家照顧，連這個論文也完全是好友幫忙的結果，很慚愧 – 這位好友現在美國大學做計算機教授，在此再次感謝 – 那可是真哥們兒：我離校回家一個多月，隻是臨走前告訴他有事就幫我應付一下，因為我不知道要回去多長時間，結果我在論文答辯前兩天才回來，此時他在我不知情的情況下已經幫我寫好了論文，連標題都是他命的名 – 關於調和函數性質的幾點注記。
然後，畢業答辯時有一個精彩的橋段：
在我“複習”了一下那篇畢業論文後，就是看懂那些公式推導，就做了答辯。當我介紹了這種調和函數產生的幾個“美麗”的屬性之後，一個我不認識的評審老師提問，你能不能舉一個具體的調和函數的例子來說明？應該說，這個問題是最基本的了，沒有任何刁難之意。不幸的是，我還真的找不出這樣一個例子。於是，我紅著臉轉向我的導師，尋求幫助。
在前排坐著的我的導師也是麵露尷尬，轉過頭去解釋說：我們搞理論數學研究的，主要注重形式邏輯推導和公式的美感，希望能夠得到像愛因斯坦的質能方程、麥克斯韋電磁方程、歐拉公式等那樣漂亮的公式。至於在現實中如何應用，不是我們關注的重點。說實話，這個例子我現在也舉不出來。
這時我已經考了他的研究生並被錄取了。我開始逐漸體會到，數學不屬於真正的自然科學！數學隻是純理抽象，是一種邏輯工具。喜歡聯係實際，對純抽象有點臉盲的我，此時對於純理數學的熱情到此也消磨一空，後來雖然讀了數學研究生，但還是又轉成工科，離開了純理抽象的數學天地。但巧合的是，畢業後我還真的做了多年的調和分析的應用，比如傅裏葉譜分析、核磁共振信號處理等工作，雖然與理論數學上的調和分析不搭嘎。
這裏插一句 – 人生就是這麽狗血：在《童年的記憶》裏我曾提及，我的小學第一堂課是以無知、無感的被動“作弊”開始的，我沒有動一下筆就得到了入學考試的 100 分；而大學畢業又複製了小學入學的魔幻，沒有動一下筆，畢業論文就得了 A – 當時考上研究生的同學好像都拿了 A。
我對數學中那些和自然世界貼近的部分還是情有獨鍾，在畢業工作後有時還會去琢磨一下。其中一大興趣就是關於素數，也稱為質數， prime number。它們像生長於自然數間的雜草，看上去隨機分布，但又表現出驚人的規律性，並有規範其行為之法則，且以可證明的精準度遵守著這些法則。
為紀念創刊 125 周年，Science 雜誌於 2005 年 7 月提出了 125 個重要的科學問題，其中包含 25 個最突出的重點問題以及其他 100 個生命科學、物理學、數學等領域的難題。
2021年，上海交大協同 Science 在全世界範圍內再次征集並發布了新的 125 個問題。其中三個數學問題被列在首位，而第一個問題就是 “是什麽讓素數如此特別？”。
【翻譯】有無限多個素數，就是那些隻能被 1 和該數字本身整除的數。對於數學家、計算機科學家和其他專家來說，其存在性和屬性非常有趣。雖然所有的自然數都可以表示為素數的乘積，但將大數分解為素數的積卻存在很大困難。 由於素數具有與分解相關的獨特屬性，因此它們在密碼學領域非常有用。想象一下，計算機加密依賴於一個非常大的數字，例如具有數十甚至數百位數字的多個因數的數字； 即使是超級計算機在識別其素因數方麵也會麵臨巨大的挑戰，這使得素數在信息加密領域極有潛力。
雖然數學在嚴格意義上不屬於自然科學（沒有證偽性），而是以形式邏輯為核心的符號語言，但在各種科學問題上數學工具是不可或缺的，而且極為重要。不信，你看看下麵的公式，如果出現在某篇文章中，是不是就有讓人肅然起敬的高大上的感覺？
– 熟識這個公式的人一定是物理學界的好學生。
聲明一下：其實概率統計是可以驗證的。所以我個人認為概率統計學屬於自然科學範疇。但概率統計是否該歸類為純理數學，就是另一個問題了。
在八十年代，計算機性能還不像現在的水平，對複雜計算的能力有限。當時我接觸到偽隨機序列生成，就是用一個種子不斷乘積後用大素數求模產生的序列。現在還記得一個經典的數對：種子是16807，大素數是2147483647 – 這是一個梅森素數，231-1，第31個梅森數。這對數產生的偽隨機序列的“隨機性”很好，序列長度為10位數。但理想的隨機序列式白噪聲，還是達不到的。
素數對應的是合數，也就是說，不是素數的自然數就是合數。對於剛剛接觸到初等數學的人來說，素數與合數的關係和奇數與偶數的關係有點類似。但其本質卻是有巨大的差異。和多年來的社會閱曆融合在一起，我感受到素數及其屬性可以映射到人類社會中。
現在我試一試用“關於素數的一點注記”的方式來補上我那“作弊”的大學畢業論文，也以此紀念我那數學係為我辯護的導師 – 他在我畢業後沒幾年就故去了，還不到50歲，英年早逝，也是癌症。可惜我連一張他的照片都沒有，不過他長得很像陳教授：
下麵就是我的素數隨想。在開始之前，請有興趣的讀者做一個小練習，試證明：在n2和(n+1)2之間，至少有一個素數 – 答案在文後找，不過最好自己先嚐試一下。
（二）隨想
【素數性質 – 1】素數是自然數中的中堅。如果把自然數看成一個空間，那麽素數就是這個空間的支撐框架。任何一個大於1的合數都可以用素數的積來表示。比如，2023 = 7 x 17 x 17。這樣，素數就可以用來構成這個自然數世界。這就是我們小學學習的因式分解。
隨想 – 這個社會上有一些素數人，就像砼（tóng，混凝土，我從土木係同學那裏學習來的字）裏的鋼筋，支撐起了這個社會大廈。這些人有獨立的人格，有自由的思想，不會人雲亦雲、隨波逐流。這個人類社會靠的不是那些唯唯諾諾、見風使舵的人。當社會風起雲湧之時，牆頭草們都隨風而去，隻有他們堅韌不折，撐起這片天，是社會的中流砥柱；當社會政通人和，國泰民安之時，他們又是走在時代前列的先行者，引領著時代的潮流。人類社會上的最小思維單位就是那些素數人。
【素數性質 – 2】素數在自然數中的完備的。哥德巴赫猜想（向陳景潤致敬）：任何一個大偶數都可以用兩個素數的和來表示。雖然這個猜想沒有被完全證明，但現在數學界沒有人懷疑其正確性。比如，20 = 3 + 17。當然，奇數加 3 就是偶數，所以奇數可以最多用三個素數的和來表示。這樣，不超過 3 個素數相加就可以得到所有的自然數。
隨想 – 僅靠素數人就可以完成這個世界上的任何人間奇跡，素數人也可以把思想活動伸延到社會各個領域、各個角落，沒有死角。如果有什麽自然界的難題產生，隻要有足夠的時間，素數人就可以找出解決問題的方法，不管是小行星要撞地球，還是超級細菌未知病毒侵蝕人類健康。
【素數性質 – 3】素數在自然數中是稀疏的，而且值越大越稀疏。雖然在數值較小時，有不少靠近的素數，但隨著數值的增大，素數在自然數中的分布就越來越稀少。比如以100為區間，100以下的素數有2、3、5、7…97等共25個，但1000~1100中就隻有16個素數，10000~10100中就隻有11個，100000~100100中就隻有6個。如果上麵的100區間改為1000區間，則上述的類似位置上素數的個數就變成了168、112、87、65、53。這個素數分布原理叫素數定理，用 π(x) 來代表小於x的素數的個數，其初等表達式： π(x) ≈ x / ln(x)，ln是自然對數。比如 π(100) = 22， π(1000) = 145， π(10000) = 1086， π(100000) = 8686，...；而實際上的素數個數對應為 25，168，1229，9592，...。其高級表達式更準確：π(x) = ∫1/ln(t)dt。當年高斯和勒讓德都在18世紀末提出了類似的理論，但無法證明。這個問題的證明成為當時數學界的頂尖難題，當時有傳言，誰證明了這個問題，就會得到永生。100年後，法國數學家雅克·阿達馬和比利時數學家德·拉·瓦萊布桑先後獨立給出證明！他們倆果然高壽，分別活到了98歲和96歲。相關聯的素數定理推論：對每個正整數 n，從 (n+1)! + 2 至 (n+1)! + n + 1 的 n個連續正整數都是合數(非素數)。
隨想 – 我也想長壽，可惜沒有這份天賦去證明這個素數定理。社會中素數人不是均勻分布的，而是距你越遠的地方素數人越稀少。這就好像是廣義相對論中質量（引力）對時空的密度壓變，讓觀察者看到平麵的扭曲。素數數量本身就大大少於非素數，那麽在你不熟悉的環境下，素數人更是顯得少。在這個世界裏，庸庸碌碌的人永遠是大多數。
【素數性質 – 4】不僅素數是可以無限大的（歐幾裏得定理），而且孿生素數也是可以無窮大的 – 這就是希爾伯特在1900年提出的孿生素數猜想。孿生素數就是 N 和 N+2 都是素數的情況，比如17和19。雖然素數在自然數中是稀疏的，但不管如何設限，總有更大的孿生素數。北大學子張益唐對此頗有研究，目前他的結果在這個問題的研究上也是最先進的，不過和哥德巴赫猜想一樣，也沒有完全證明，不過大家都相信證明隻是時間問題。
隨想 – 道不孤行，不管素數人是如何的少，總會有結伴的素數人，在某個地方、某個領域，做出傑出的貢獻。比如楊振寧與李政道，雖然前者在非學術領域讓人有些微詞。
【素數性質 – 5】素數理論是RSA加密算法的基石。因為對大數做因式分解的算法複雜度與大數相乘或求模的不對稱性，兩個大素數可以用來產生RSA算法。這樣的兩個素數的積也被稱為半素數，RSA數是一些大的半素數的集合。這種加密算法是MIT的三位大咖在1977年提出的，隨用他們三人姓名的首字母命名。這是一種公開密鑰算法，在電子商務中被廣泛應用。
隨想 – 這就是 2021 版 Science 的 125 重要問題 No 1 的描述。到目前為止，分解素數還是沒有什麽太好辦法，除了 brutal force，一些算法可以加速，但還是很慢。這就像在茫茫人海中尋找那個對的你，或是在複雜工程中尋找合適的能工巧匠。素數不像毛遂，無法自薦，薦了也不一定有用。素數人也是如此，能識別素數人的才是高才伯樂。
【素數性質 – 6】素數本身是有優美的內在規律的。對整數a，如果p是素數，則 ap-a 是p倍數 – 這就是費爾馬小定理，比如 a = 2，p = 31，則 2 的 31 次方減 2 就是 2147483646，是 31 的倍數。
隨想 – 發現素數人特征是很 tricky 的。作為律師，費爾馬四百年前就發現了這麽複雜的素數內在屬性，厲害。歐拉和萊布尼茲都在費爾馬發現約100 年後給出了證明。我也曾碰巧對此感興趣 – 那還是在我知道有這個費爾馬小定理之前，我也發現了類似的規律，但是是其逆命題，即如果 ap-a 是 p 倍數，則 p 是素數。我當時高興得想發表論文，可遺憾的是這個發現是錯的，而且我不是第一個犯錯的人。中國數學前輩李善蘭 （1810年—1882年）就曾發現過，並被稱為中國猜想：當 a = 2，n = 341 時，中國猜想不成立，因為 341 = 11 x 31。關於這個中國猜想，還有許多神奇的故事，甚至被神話到春秋時代，李約瑟在《中國科學技術史》中也有提及。
素數還有許多性質，在此就不拓展了，大家可以自行腦補：
- 素數和而不同...
- 素數可助韓信點兵...
- 素數除了 2 都是奇數...
- 素數是有棱有角的石頭…
- 素數是個性十足的的另類…
- 素數是不隨波逐流的非主流…
- 素數是有自我意識的萬物代表…
（三）隨想的伸延
從其名字上就可以感受到其特性：素數、質數，翻譯得真好，反映了其性質，類似幾何上的奇點。英文更是有味道，prime，來自拉丁語primus，就是第一位的，初始的。由此派生的名詞：
Prime minister – 總理
Prime time – 黃金時間
Primer – 底漆
歐幾裏得（公元前 325 ~ 公元前 265）是偉大的古希臘數學家，在思想巨匠亞裏斯多德離世前三年出生，和超長待機的秦昭襄王（秦始皇的曾祖父）是同時期的人。就在東方世界上演連橫合縱、爾虞我詐之際，他貢獻了三維空間的公理化體係結構，故我們現在最基本的三維幾何空間被稱為歐幾裏得空間。那時古希臘的哲學、科學、方法論是如此輝煌，看歐幾裏得的關於 “素數是無窮的” 證明就可見一斑。因為是歐幾裏得給出了第一個證明，故也稱為歐幾裏得定理（後來歐拉在18世紀也給出過解析的證明，並且推論出素數的出現密度高於自然數的平方數）：
【證明】如果素數是有限的， S{P1,P2,P3…Pn} 是由所有素數所組成的有限集合，令 N = 1 + （P1…Pn）， （P1…Pn）為所有 S 中所有素數的積。如同其他自然數一樣，N大於所有素數，必可被至少一個素數整除。但任何可整除 N 的素數都不可能是有限集合 S 內的元素（素數），因為後者除 N 都會餘 1。所以，N可被其他不屬於 S 的素數所整除。這與前麵 S 的定義是矛盾的，所以 S 不是有限的。
前麵的練習題“在n2和(n+1)2之間，至少有一個素數”的答案：不好意思，開了一個天大的玩笑 – 這是著名的勒讓德猜想，由德國人 Edmund Georg Hermann Landau 在1912年提出，已經有一百多年了，至今無人征服，既無法證明也無法證偽。
我在上高中時曾經也有過類似的笑話。1978年，“科學的春天”剛剛開始，我靠數理競賽上了我們那裏唯一的重點高中。當時分班是按成績排名，我們年級 7 個理科班，完全按入學考試成績分，把我們競賽的前 20 名加上升高中考試的前 30 名拚成一班。可想而知，同學們都是來自各個中學的尖子，牛氣得不要不要的，感覺自己離陳景潤華羅庚不遠了。
高中開學的第一天，報到後也沒有什麽事，我們這些靠競賽上去的因為不久前在地區禮堂裏頒獎時見過，彼此認識，就嗨了起來：有一位猥瑣的高手出了一道題，讓這些不知深淺的同學證明：X3 + Y3 = Z3 沒有非零整數解。一幫“驕子”們瞬間都靜了下來，憋著勁要當第一個證明人。嘿嘿，結果可想而知......
1993 年 6 月，英國人 Andrew John Wiles 發表了他的證明，“解決”了費爾馬大定理（也稱費爾馬最後定理），也就是這個題目的一般形式：“Xn + Yn = Zn 當 n 大於 2 時沒有非零整數解”。
Andrew 的證明在數學界極為轟動，這可是公認的三百五十百年來最難啃的骨頭。 他獨自一人花了 7 年的時間，悄悄地啃了下來，並為此發明了許多新概念和方法。可是，可但是，但可是，他複雜的證明在當時無法馬上驗證，而幾個月後在同行評審中發現了邏輯錯誤，有致命傷。雖然他發明的數學工具還是有巨大的價值，但此證明還是無法成立 – 數學就是這樣黑白分明的邏輯關係。
攜 170 的智商，Andrew 再度投入到證明中，和他的學生 Richard Taylor 一起，經過不到一年的奮戰，居然再次完整地證明費爾馬大定理，並在 1995 年《數學年刊》發表，這是經過同行評審、邏輯驗證了的 – 真是神人啊，最終的證明和附帶的討論長達 130 頁紙。他後來也因此獲得了一係列的數學大獎，包括有數學界諾貝爾之稱的菲爾茲獎 – 不過是特別獎，因為他已經超齡了（菲爾茲獎上限是 40 歲）。這個證明被譽為 “20 世紀最輝煌的數學成就”。
法國大律師費爾馬搞數學是純業餘愛好。當年他在書的旁空處寫下此式，並標注：“我確信我發現一種美妙的證法，可惜這裏的空白處太小，寫不下（Hanc marginis exiguitas non caperet）”，喜歡惡作劇的費爾馬害得數學界努力了幾百年也不見效，不知道那個“美妙的證法”是什麽。這句話也成為了他的名言。
費爾馬不願意發表他的成果，所以好東西都在手稿裏麵。他在閱讀數學書籍的過程中，習慣地把隨想的一些思路寫在旁邊空白的地方。他還對證明思路諱莫如深，往往隻會寫出推導得到的定理，而不會保留證明過程。有趣的是，他還在手稿中非常理直氣壯地給出理由，為什麽沒有給出證明過程：比如 “我可以證明這個結論，但現在我必須去喂貓了” 或者是 “我可以證明這一點，但我要去洗頭了”。這種惡趣味讓幾百年以來的數學家對他又愛又恨。
費爾馬去世後，其子出版了一本書，裏麵囊括了他老爹在頁邊空白處所做的所有筆記。因為都沒有證明隻有結果，所以留下了一個個極為誘人的挑戰，無數數學家隻能前赴後繼去求證費馬潦草筆記的正確性。這些東西在被後人證明之前，隻能稱為猜想，雖然被費爾馬稱為定理。
別總瞧不起民科，費爾馬就是民科鼻祖。當年在中關村的人常能看到科學院數學所和北大來打擂台的民科，其中就有“證明了”費爾馬大定理的，他們多被 “讀過什麽專業書？” 給打發回去了，不知道有沒有誤人子弟的。
費爾馬這樣的大咖，自然不會對素數熟視無睹。他對素數的貢獻：
- 費爾馬小定理：a^p-a ≡ 0 (mod p)，其中p是一個素數，a是正整數
- 素數可分為 4n+1 和 4n+3 兩種形式
- 形如 4n+1 的素數能夠、而且隻能夠以一種方式表為兩個平方數之和
- 沒有一個形如 4n+3 的素數可以表示為兩個平方數之和
- 形如 4n+1 的素數能夠且隻能夠作為一個直角邊為整數的直角三角形的斜邊；4n+1 的平方是且隻能是兩個這種直角三角形的斜邊；類似地，4n+1 的 m 次方是且隻能是 m 個這種直角三角形的斜邊
- 形如 4n+1 的素數與它的平方都隻能以一種方式表達為兩個平方數之和；它的3次和4次方都隻能以兩種表達為兩個平方數之和；5次和6次方都隻能以3種方式表達為兩個平方數之和，以此類推，直至無窮
歐拉給費爾馬擦屁股：
- 1770年，證明了費爾馬大定理當 n = 3 時成立，也就是我上高中碰到的第一個惡作劇。其實歐拉做了兩種不同的證明，詳情見這裏。而且其中一個有問題，雖然看上去很手段巧妙 – 天才如歐拉也會犯錯誤。如果感興趣關於歐拉的錯誤，可以看這裏。
- 費爾馬說他發現形如 Fn = 2^(2^n)+1 的數全是素數，比如 n 為 0~4 時，對應的值是3，5，17，257，65537都是素數。歐拉發現 n=5時，4294967297 = 641x6700417 卻是個合數，而後麵的直到 n < 1495 時都是合數。
不知道這費爾馬的腦子是怎麽長的，業餘愛好吊打專業大咖。另一個類似的情況是孟德爾，作為神職人員窺視上帝造物的秘密，把豌豆玩個爆，發現了遺傳規律，不知道是否符合教規。達爾文也是差不多，學習醫學、神學，最後反叛了教會，用《物種起源》闡明了生物進化原理。
現在還有許多素數相關的猜想沒有解決，其中最著名的就是黎曼猜想，其描述比較複雜，是猜想中的皇冠，有興趣的可以看這裏。黎曼猜想與素數定理密切相關，不過，作為數學係的學生，我聽到黎曼頭就有點大。
還有許多關於素數的猜想，有興趣的可以去研究，比如：
- 斐波那契素數是無限的
- 梅森素數是無限的
- 費爾馬素數是有限的
回到我的高中課堂上。這個題目雖然通式證明非常困難，但當 n 為 3 的時候，並不是通式級別的超級難題，雖然對我們這些自以為是的小白們還是無法觸及的。
下麵給出歐拉在1770 年時候的證明，他使用了無窮遞降法（proof by infinite descent）。術語：coprime – 互素；gcd – 最大公約數（greatest common divisor） 。
慎入！Theorem: Euler's Proof for FLT （Fermat's Last Theorem）: n = 3
x3 + y3 = z3 has integer solutions -> xyz = 0
(1) Let's assume that we have solutions x,y,z to the above equation.
(2) We can assume that x,y,z are coprime. [See here for the proof].
(3) First, we observe that there must exist p,q such that (see here for proof):
(a) gcd(p,q) = 1
(b) p,q have opposite parities (one is odd; one is even)
(c) p,q are positive
(d) 2p*(p2 + 3q2) is a cube
(4) Second, we know that gcd(2p, p2+3q2) is either 1 or 3. (see here for proof).
(5) If gcd(2p, p2+3q2) = 1, then there must be a smaller solution to FLT n=3. (see here for proof).
(6) Likewise, if gcd(2p, p2+3q2) = 3, then there must be a smaller solution to FLT n=3. (see here for proof).
(7) But then there is necessarily a smaller solution and we could use the same argument on this smaller solution to show the existence of an even smaller solution. We have thus shown a condition of infinite descent.
能看明白這個解題思路的，可以去練國際數學奧林匹克了。
我們那時還是一幫生瓜蛋子，哪裏有這個本事？記得我用了一個不容易看出錯誤的簡單方法給出了證明，高興了兩分鍾，一片歡呼，但很快就被人看出了破綻，原來是個假把式。那個時候競賽級別的難題很少見，後來出題人說這是費爾馬大定理的特殊形式，我們馬上就都打蔫了。
十幾年後，留美時的一位同學，說到他剛剛上北大時，班上同學都是各地的尖子，不服不忿的，老師就用一道初等數學的平麵幾何題來震懾大家，說讓你們看看什麽是難題：
用圓規和直尺在三條平行線上畫出一個等邊三角形，使得三角形的三個頂點分別落在三條平行線上。
這道題很有趣，你來試試？
（四）隨想中的生物
在北美有一種蟬，叫周期蟬，其生命周期是 13 年或 17 年，相應被稱為 13 年蟬或 17 年蟬。幼蟲孵化後即鑽入地下，一生絕大多數時間在地下度過，靠吸食樹根的汁液生存。它們在地下生活 13 年或 17 年後，同種蟬的幼蟲同時破土而出，在 4~6 周內羽化、交配、產卵、死亡，而卵孵化後進入下一個生命周期。因此某一年份在美國東部一些地方每過 13 或 17 年就會突然出現大量的蟬，成為一種奇景。
為什麽會有這個 13 年 或 17 年的奇怪周期？對了，就是素數長周期。
在這樣長的素數周期年裏，一般不會連續碰到天敵和自然災害也與這個周期同步，從而避免被滅族。不同的周期蟬種群出地的年份不同，使這個大家族的基因繼承就更安全了。
大自然真的很神奇。
|
