“是什么讓素數(shù)如此特別？”

這是125個新科學(xué)問題的第一問. 2021年, 上海交通大學(xué)攜手《科學(xué)》雜志發(fā)布“新125個科學(xué)問題”——《125個科學(xué)問題：探索與發(fā)現(xiàn)》. 其中三個數(shù)學(xué)問題被列在首位, 第一個問題就是關(guān)于素數(shù)的. 下面是這個問題描述的中文翻譯.

是什么讓素數(shù)如此特別? 素數(shù)：只能被 1 和其本身整除的數(shù), 有無限多個. 對于數(shù)學(xué)家、計算機(jī)科學(xué)家和其他專家來說, 其存在性和屬性非常有趣. 雖然所有的自然數(shù)都可以表示為素數(shù)的乘積, 但將大數(shù)分解為素數(shù)的積卻存在很大困難. 由于素數(shù)具有與分解相關(guān)的獨(dú)特屬性, 因此它們在密碼學(xué)領(lǐng)域非常有用. 想象一下, 計算機(jī)加密依賴于一個非常大的數(shù)字, 例如具有數(shù)十甚至數(shù)百位數(shù)字的多個因數(shù)的數(shù)字；即使是超級計算機(jī)在識別其素因數(shù)方面也會面臨巨大的挑戰(zhàn), 這使得素數(shù)在信息加密領(lǐng)域極有潛力.

素數(shù)被列在125個科學(xué)問題之首, 可見素數(shù)的重要性. 千百年來, 數(shù)學(xué)家們一直在追尋素數(shù)的規(guī)律, 挖掘它們隱藏的深層奧秘. 本文將從素數(shù)的定義開始, 介紹素數(shù)在數(shù)論中的重要地位, 以及數(shù)學(xué)家為尋找素數(shù)和研究素數(shù)的分布提出的各種定理和猜想.

素數(shù)有無限多個

素數(shù), 又稱質(zhì)數(shù), 指在大于1的自然數(shù)中, 除了1和它本身外, 無法被其他自然數(shù)整除的數(shù).

大于1的自然數(shù)若不是素數(shù), 則稱之為合數(shù).

例如, 23是個素數(shù), 因?yàn)槠湔s數(shù)只有1與23. 而22則是個合數(shù), 因?yàn)槌?與22外, 2與11也是其正約數(shù). 對于比較小的數(shù)字, 我們很容易判斷是不是素數(shù), 一旦數(shù)字變大, 這個工作就變得很困難.

一個很自然的問題是：素數(shù)有多少個？早在公元前300年, 古希臘數(shù)學(xué)家歐幾里得就已經(jīng)研究過這個問題了, 稱素數(shù)有無窮多個, 并用反證法給出了證明. 你可以點(diǎn)擊下面的證明進(jìn)行閱讀也可以跳過.

證明

假設(shè)存在有限個素數(shù), 將他們寫在一個集合里, 用 ,其中 是集合里最大的素數(shù). 然后我們定義

根據(jù)假設(shè), 是素數(shù), 并且 不能被 整除. 因此, 不能被任何素數(shù)整除, 根據(jù)素數(shù)的定義, 是一個素數(shù)并且大于 , 所以 不是全部的素數(shù), 故與假設(shè)矛盾, "素數(shù)有有限個"這一假設(shè)應(yīng)該被否定.

但要注意的是, 此證明并不說明n個素數(shù)的乘積與1的和是素數(shù). 例如：

素數(shù)有無窮多個這一命題簡單卻魅力無窮, 2300多年間, 許多數(shù)學(xué)家都給出了數(shù)以百計的證明. 但在眾多證明中, 英國數(shù)學(xué)家哈代 (G. H. Hardy) 在《一位數(shù)學(xué)家的辯白》 (A Mathematician's Apology) 一書中稱歐幾里得的證明歷久彌新, 依然如初發(fā)現(xiàn)時一樣重要, 兩千年的時光不曾刻下絲毫褶痕. 如果你想了解更多的證明, 可以閱讀參考文獻(xiàn)[1].

素數(shù)的重要性

要說素數(shù)在數(shù)論中的重要地位, 一個定理便足以說明, 那就是算術(shù)基本定理.

定理1 ( 算術(shù)基本定理 )

任何大于1的整數(shù)要么本身就是素數(shù), 要么可以寫為兩個或以上的素數(shù)的乘積, 如果將這些素因子按大小排列之后, 寫法唯一.

例如:

定理具體的證明如下.

證明

假設(shè)存在不能分解成有限個素數(shù)的乘積的合數(shù), 根據(jù)最小數(shù)原理, 其中必有一個最小的數(shù), 設(shè)為 . 根據(jù)合數(shù)的定義, 存在小于 的自然數(shù) 使得 .

如果 都是素數(shù), 與假設(shè)矛盾.

如果 至少有一個是合數(shù), 由于都比 小, 所以這個合數(shù)一定可以被分解成有限個素數(shù)的乘積, 用乘積替換這個數(shù), 可推出 可以分解成有限個素數(shù)的乘積, 與假設(shè)矛盾.

總之假設(shè)不成立, 結(jié)論成立.

唯一性證明略.

從這個定理中我們可以理解, 為什么要規(guī)定1不是素數(shù), 因?yàn)樵谝蚴椒纸庵锌梢杂腥我舛鄠€1, 這樣就破壞了分解的唯一性.算術(shù)基本定理又稱為正整數(shù)的唯一分解定理, 所以一些數(shù)學(xué)家將素數(shù)喻為構(gòu)成數(shù)學(xué)大廈的磚塊.

關(guān)于正整數(shù)的分解不得不提著名的哥德巴赫猜想. 哥德巴赫猜想是德國數(shù)學(xué)家哥德巴赫（Christian Goldbach）于1742年提出的.

猜想1 ( 哥德巴赫猜想 )

任何一個大于2的偶數(shù)都可以表示為兩個素數(shù)的和.

例如：

, , , ,以此類推.

由于任何一個大于5的奇數(shù)減去3都是一個偶數(shù), 若哥德巴赫猜想成立，那么任一大于3的整數(shù)都可以表示為2個或3個素數(shù)的和. 這是一個多么令人激動的結(jié)論啊.

雖然哥德巴赫猜想尚未被證明, 但已經(jīng)在計算機(jī)上通過枚舉的方式驗(yàn)證了很大范圍內(nèi)的情況. 但我們相信, 這個難題一定能被攻克. 而一旦猜想被證實(shí), 那么素數(shù)的地位將更加凸顯.

尋找素數(shù)

自從歐幾里得證明了有無窮個素數(shù)以后, 人們就企圖尋找一個可以構(gòu)造所有素數(shù)的公式, 找到判定素數(shù)的方法. 遺憾的是素數(shù)隨機(jī)出現(xiàn)在數(shù)字當(dāng)中, 沒有任何規(guī)律. 到了高斯時代, 基本上確認(rèn)了簡單的素數(shù)公式是不存在的.

缺少規(guī)律意味著只能通過一個一個的試驗(yàn)來尋找. 其中一個常用的生成素數(shù)的篩法稱為埃拉托斯特尼篩法(sieve of Eratosthenes)，簡稱埃氏篩, 得名于古希臘數(shù)學(xué)家埃拉托斯特尼.

埃氏篩基本步驟是從最小的素數(shù)2開始, 將該素數(shù)的所有倍數(shù)標(biāo)記成合數(shù), 而下一個尚未被標(biāo)記的最小自然數(shù)3即是下一個素數(shù). 如此重復(fù)這一過程, 將各個素數(shù)的倍數(shù)標(biāo)記為合數(shù)并找出下一個素數(shù), 最終便可找出一定范圍內(nèi)所有素數(shù).

這一過程的動圖如下圖所示

前20位素數(shù)依次是：

盡管如此, 素數(shù)本身還是有很多優(yōu)美的內(nèi)在規(guī)律的.

對整數(shù) , 如果 是素數(shù), 則 是 的倍數(shù). 這就是費(fèi)馬小定理. 比如 , , 則 , 是 的倍數(shù).

在尋找素數(shù)時, 歐幾里得曾提出有少量素數(shù)可以寫成 (其中指數(shù) 為素數(shù))的形式. 究竟有多少個素數(shù)可以寫成這種形式？歐幾里得把這個問題留給了后人. 于是, 費(fèi)馬、笛卡爾、哥德巴赫、歐拉、高斯……幾乎所有大數(shù)學(xué)家都研究過這種特殊形式的素數(shù), 17世紀(jì)的法國數(shù)學(xué)家馬林·梅森是其中成果最為卓著的一位.

梅森學(xué)識淵博、才華橫溢, 是法蘭西科學(xué)院的奠基人和當(dāng)時歐洲科學(xué)界的中心人物. 為了紀(jì)念他, 數(shù)學(xué)界就把 型的數(shù)稱為“梅森數(shù)”, 并以 記之；如果 為素數(shù), 則稱之為“梅森素數(shù)”. 然而, 2300多年來, 人類僅發(fā)現(xiàn)47個梅森素數(shù). 這種素數(shù)新奇而迷人, 因此有“數(shù)學(xué)珍寶”的美譽(yù). 梅森素數(shù)歷來是數(shù)論研究的一項(xiàng)重要內(nèi)容, 也是當(dāng)今科學(xué)探索的熱點(diǎn)和難點(diǎn)之一[2].

另外在尋找素數(shù)時還有下面幾個著名猜想.

孿生素數(shù)猜想：是否存在無窮多個素數(shù) , 使得 也是素數(shù)？

勒讓德猜想：是否在所有連續(xù)的平方數(shù)之間至少存在一個素數(shù)？

未命名猜想：是否有無窮多個素數(shù) , 使得 是一個平方數(shù)？換句話說：是否有無窮多個形式為 的素數(shù)？

在1912年國際數(shù)學(xué)家大會中, 埃德蒙蘭道列出了關(guān)于素數(shù)的四個基本問題, 就是上述3個猜想外加哥德巴赫猜想. 這些問題在他認(rèn)為是"在當(dāng)前的數(shù)學(xué)認(rèn)識下無法解決", 后人稱之為蘭道問題. 到2023年為止, 所有四個問題都未得到解決.

素數(shù)的應(yīng)用

別以為研究素數(shù)只是數(shù)學(xué)家們的消遣和游戲, 事實(shí)上素數(shù)的研究在當(dāng)代具有十分豐富的理論意義和實(shí)用價值.

比如尋找梅森素數(shù)是發(fā)現(xiàn)已知最大素數(shù)的最有效途徑, 它的探究推動了數(shù)論的研究, 促進(jìn)了計算技術(shù)、程序設(shè)計技術(shù)、密碼技術(shù)、網(wǎng)格技術(shù)的發(fā)展以及快速傅立葉變換的應(yīng)用. 另外, 梅森素數(shù)的探究方法還可用來測試計算機(jī)硬件運(yùn)算是否正確.

素數(shù)理論是RSA加密算法的基石. 兩個大素數(shù)相乘非常容易, 但將它們的乘積分解回這兩個素數(shù)則非常困難. 正是基于此不對稱性, MIT的三位大咖在1977年發(fā)明了RSA算法. RSA是他們?nèi)诵彰氖鬃帜? 這是一種公開密鑰算法, 這個算法廣泛應(yīng)用于數(shù)字通信和網(wǎng)絡(luò)安全領(lǐng)域, 為信息的加密和解密提供了高度的安全性.

此外, 素數(shù)還在隨機(jī)數(shù)生成、哈希函數(shù)設(shè)計、錯誤檢測和分布式計算等領(lǐng)域發(fā)揮重要作用.

參考文獻(xiàn)

[1] 盧昌海.素數(shù)有無窮多個之九類證明. https://www.changhai.org/articles/science/mathematics/IP.php

[2] 梅森素數(shù)為何這樣重要. https://mathcubic.org/article/article/index/id/113.html

來源：數(shù)來數(shù)趣

編輯：紫竹小筑

轉(zhuǎn)載內(nèi)容僅代表作者觀點(diǎn)

不代表中科院物理所立場

如需轉(zhuǎn)載請聯(lián)系原公眾號