“是什么讓素數如此特別？”

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

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

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

素數有無限多個

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

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

例如, 23是個素數, 因為其正約數只有1與23. 而22則是個合數, 因為除了1與22外, 2與11也是其正約數. 對于比較小的數字, 我們很容易判斷是不是素數, 一旦數字變大, 這個工作就變得很困難.

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

證明

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

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

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

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

素數的重要性

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

定理1 ( 算術基本定理 )

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

例如:

定理具體的證明如下.

證明

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

如果 都是素數, 與假設矛盾.

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

總之假設不成立, 結論成立.

唯一性證明略.

從這個定理中我們可以理解, 為什么要規定1不是素數, 因為在因式分解中可以有任意多個1, 這樣就破壞了分解的唯一性.算術基本定理又稱為正整數的唯一分解定理, 所以一些數學家將素數喻為構成數學大廈的磚塊.

關于正整數的分解不得不提著名的哥德巴赫猜想. 哥德巴赫猜想是德國數學家哥德巴赫（Christian Goldbach）于1742年提出的.

猜想1 ( 哥德巴赫猜想 )

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

例如：

, , , ,以此類推.

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

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

尋找素數

自從歐幾里得證明了有無窮個素數以后, 人們就企圖尋找一個可以構造所有素數的公式, 找到判定素數的方法. 遺憾的是素數隨機出現在數字當中, 沒有任何規律. 到了高斯時代, 基本上確認了簡單的素數公式是不存在的.

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

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

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

前20位素數依次是：

盡管如此, 素數本身還是有很多優美的內在規律的.

對整數 , 如果 是素數, 則 是 的倍數. 這就是費馬小定理. 比如 , , 則 , 是 的倍數.

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

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

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

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

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

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

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

素數的應用

別以為研究素數只是數學家們的消遣和游戲, 事實上素數的研究在當代具有十分豐富的理論意義和實用價值.

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

素數理論是RSA加密算法的基石. 兩個大素數相乘非常容易, 但將它們的乘積分解回這兩個素數則非常困難. 正是基于此不對稱性, MIT的三位大咖在1977年發明了RSA算法. RSA是他們三人姓名的首字母. 這是一種公開密鑰算法, 這個算法廣泛應用于數字通信和網絡安全領域, 為信息的加密和解密提供了高度的安全性.

此外, 素數還在隨機數生成、哈希函數設計、錯誤檢測和分布式計算等領域發揮重要作用.

參考文獻

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

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

來源：數來數趣

編輯：紫竹小筑

轉載內容僅代表作者觀點

不代表中科院物理所立場

如需轉載請聯系原公眾號