素數

素數（或素整數，通常簡稱為“素數”）是一個正整數 ，除了 1 和 本身之外，沒有其他正整數除數。更簡潔地說，素數 是一個正整數，除了 1 之外，正好有一個正除數，這意味著它是一個不能被分解的數。例如，13 的唯一除數是 1 和 13，因此 13 是素數，而數字 24 的除數是 1、2、3、4、6、8、12 和 24（對應於因式分解 ），因此 24 不是素數。除 1 以外的正整數，如果不是素數，則稱為合數。

雖然術語“素數”通常指正素整數，但也定義了其他型別的素數，例如高斯素數。

數字 1 是一個特例，它既不被認為是素數，也不被認為是合數 (Wells 1986, p. 31)。雖然數字 1 曾經被認為是素數 (Goldbach 1742; Lehmer 1909, 1914; Hardy and Wright 1979, p. 11; Gardner 1984, pp. 86-87; Sloane and Plouffe 1995, p. 33; Hardy 1999, p. 46)，但在許多涉及大於或等於 2 的素數的定義和應用中，它都需要特殊處理，因此通常將其歸為一類。不稱 1 為素數的一個很好的理由是，如果 1 是素數，那麼算術基本定理的陳述就必須修改，因為“以正好一種方式”將是錯誤的，因為任何 。換句話說，如果素數包含 1，則唯一分解為素數的乘積將失敗。Tietze (1965, p. 2) 指出了一個稍微不那麼啟發性但數學上正確的原因，他指出“為什麼數字 1 被排除在外？這是一個小學生經常爭論的問題，但由於這是一個定義問題，因此無可爭辯。”正如 Derbyshire (2004, p. 33) 更簡單地指出，“2 [作為素數] 在平衡方面是值得的；1 則不然。”

排除 1 後，最小的素數是 2。然而，由於 2 是唯一的偶素數（具有諷刺意味的是，在某種意義上，它也是“最奇怪”的素數），它也有些特殊，因此排除 2 的所有素數的集合被稱為“奇素數”。另請注意，雖然 2 今天被認為是素數，但曾經有一段時間它不是 (Tietze 1965, p. 18; Tropfke 1921, p. 96)。

第 個素數通常表示為 ，因此 、 等等，並且可以在 Wolfram 語言 中計算為Prime[n]。

前幾個素數是 2、3、5、7、11、13、17、19、23、29、31、37、... (OEIS A000040; Hardy and Wright 1979, p. 3)。記住前七個素數的助記符是，“在清晨，天文學家使非數學家精神化”（G. L. Honaker, Jr.，私人通訊，2005 年 8 月 4 日）。在小說深夜小狗神秘習題 (Haddon 2003) 中，主角克里斯托弗有趣地使用素數而不是（更）傳統的正整數來為章節編號。在電視劇數字追兇第一季劇集“頭號嫌疑犯” (2005) 中，數學天才查理·埃普斯意識到角色伊森的女兒被綁架是因為他即將解決黎曼猜想，據稱這將使犯罪者能夠透過分解大數來破解基本上所有的網際網路安全。

中十進位制數字的位數，對於 、1、... 由 1、2、3、4、6、7、8、9、10、11、12、13、14、... 給出 (OEIS A099260)。

素數的集合有時表示為 ，在 Wolfram 語言 中表示為Primes.

上面以二進位制位的序列說明了前幾個素數。

尤拉評論道：“數學家們至今徒勞地試圖發現素數序列中的某種規律，我們有理由相信這是一個思想永遠無法穿透的謎團”（Havil 2003, p. 163）。在 1975 年的一次演講中，D. Zagier 評論道：“關於素數的分佈，我有兩個事實希望能夠讓你確信，它們將永遠銘刻在你的心中。第一個事實是，儘管它們的定義很簡單，並且作為自然數的構建塊，素數像雜草一樣在自然數中生長，似乎除了機會法則之外沒有其他法則，沒有人可以預測下一個素數會在哪裡出現。第二個事實甚至更令人驚訝，因為它恰恰相反：素數表現出驚人的規律性，存在支配其行為的規律，並且它們幾乎以軍事般的精確度遵守這些規律”（Havil 2003, p. 171）。

第 個素數，對於 、1、... 由 2、29、541、7919、104729、1299709、15485863、179424673、2038074743、... 給出 (OEIS A006988; Graham et al. 1990, p. 111)。

大素數 (Caldwell) 包括大的梅森素數、費雷爾素數和 位數字的反例 ，表明 5359 不是第二類謝爾賓斯基數 (Helm 和 Norris)。截至 2024 年 10 月，已知最大的素數是梅森素數 ，它有驚人的 位十進位制數字。

素數可以透過篩選過程（例如埃拉託斯特尼篩法）生成，而幸運數也是透過篩選生成的，並且似乎與素數共享一些有趣的漸近性質。素數滿足許多奇怪而美妙的性質。雖然存在顯式的素數公式（即，要麼為所有值生成素數，要麼將第 個素數作為 的函式），但它們是人為設計的，以至於幾乎沒有實際價值。

素數特徵函式的狄利克雷生成函式 由下式給出

			(1)
			(2)
			(3)

其中 是素數 zeta 函式， 是一個艾弗森括號。

給出小於或等於數字 的素數個數的函式表示為 ，稱為素數計數函式。給出 漸近形式的定理稱為素數定理。類似地，小於或等於數字 的 形式的素數個數表示為 ，稱為模素數計數函式。

和 是反函式，因此

(4)

對於所有正整數，且

(5)

當且僅當 是素數時。

已經設計了許多素因數分解演算法，用於確定給定整數的素因子，這個過程稱為因式分解或素因數分解。它們的複雜性和複雜程度差異很大。構建一個通用的演算法來解決這個計算上“困難”的問題非常困難，因此關於問題中的數字或其因子的任何額外資訊通常可以用於節省大量時間。應該強調的是，儘管沒有已知的有效演算法可以分解任意整數，但尚未證明不存在這樣的演算法。因此，可以想象，一個足夠聰明的人可以設計出一種通用的因式分解方法，這種方法將使當前廣泛使用的絕大多數加密方案（包括銀行和政府使用的那些）易於破解。

由於素數在RSA 加密等加密演算法中的重要性，素數可能成為重要的商業商品。事實上，R. Schlafly (1994) 獲得了美國專利 ，用於以下兩個素數（以十六進位制表示法表示）

(6)

和

(7)

算術基本定理指出，任何正整數都可以以正好一種方式表示為素數的乘積。歐幾里得第二定理證明了存在無限多個素數。然而，尚不清楚是否存在無限多個形式為 的素數 (Hardy and Wright 1979, p. 19; Ribenboim 1996, pp. 206-208)，是否存在無限多個孿生素數（孿生素數猜想），或者是否總能在 和 之間找到素數 (Hardy and Wright 1979, p. 415; Ribenboim 1996, pp. 397-398)。後兩個是蘭道問題中的兩個。

尋找因子的最簡單方法是所謂的“直接搜尋因式分解”（又名試除法）。在這種方法中，所有可能的因子都使用試除法進行系統地測試，以檢視它們是否實際整除給定的數字。它僅適用於非常小的數字。更通用（且更復雜）的方法包括橢圓曲線因式分解法和數域篩法因式分解法。

已經證明，素數集合是一個丟番圖集 (Ribenboim 1991, pp. 106-107)。

除了 2 和 3 之外，所有素數都具有 的形式，即 (Bungus 1599, p. 399, quoted in Peano 1908, p. 59; Wells 1986, p. 68)。對於整數 的 ， 是素數當且僅當同餘方程

(8)

對於 、1、...、 成立 (Deutsch 1996)，其中 是一個二項式係數。此外，整數 是素數當且僅當

(9)

前幾個複合 ，對於它們 是 、560、588、1400、23760、... (OEIS A011774; Guy 1997)，總共有 18 個這樣的數字小於 。

Chen (1979) 表明，對於足夠大的 ，在 和 之間，對於 ，總是存在一個至少有兩個素因子的數字 (Le Lionnais 1983, p. 26; Guy 2004, p. 34)。實際上，這種關係似乎適用於所有 。

由連續數字組成的素數（將 0 視為在 9 之後）包括 2、3、5、7、23、67、89、4567、78901、... (OEIS A006510)。由本身是素數的數字組成的素數包括 23、37、53、73、223、227、233、257、277、337、353、373、523、557、... (OEIS A019546)，這是斯馬蘭達克序列之一。

由於素數 只有平凡因子 1 和 ，比爾·蓋茨在他的未來之路中意外地提到了一個平凡的操作，當時他說：“由於系統的隱私和數字貨幣的安全性都依賴於加密，因此數學或計算機科學方面的突破如果擊敗了密碼系統，可能會是一場災難。明顯的數學突破將是開發一種分解大素數的簡單方法[重點新增]”（Gates 1995, p. 265）。