素数检验

**質數**（Prime number），又稱**素數**，指在大於 1 的自然數中，除了 1 和該數自身外，無法被其他自然數整除的數（也可定義為只有 1 與該數本身兩個正因數的數）。大於 1 的自然數若不是質數，則稱之為合數（也稱為合成數）。例如，5 是個質數，因為其正因數只有 1 與 5。7 是個質數，因為其正因數只有 1 與 7。而 4 則是個合數，因為除了 1 與 4 外，2 也是其正因數。6 也是個合數，因為除了 1 與 6 外，2 與 3 也是其正因數。算術基本定理確立了質數於數論裡的核心地位：任何大於 1 的整數均可被表示成一串唯一質數之乘積。為了確保該定理的唯一性，1 被定義為不是質數，因為在因式分解中可以有任意多個 1（如 3、1×3、1×1×3 等都是 3 的有效因數分解）。

古希臘數學家歐幾里得於公元前 300 年前後證明有無限多個質數存在（歐幾里得定理）。現時人們已發現多種驗證質數的方法。其中試除法比較簡單，但需時較長：設被測試的自然數為 $n$ ，使用此方法者需逐一測試 2 與 ${\sqrt {n}}$ 之間的質數，確保它們無一能整除 $n$ 。對於較大或一些具特別形式（如梅森數）的自然數，人們通常使用較有效率的演算法測試其是否為質數（例如 282589933-1 是直至 2018 年 12 月為止已知最大的梅森質數，也是直至 2018 年 12 月為止已知最大的質數）。雖然人們仍未發現可以完全區別質數與合數的公式，但已建構了質數的分布模式（亦即質數在大數時的統計模式）。19 世紀晚期得到證明的質數定理指出：一個任意自然數 n 為質數的機率反比於其數位（或 $n$ 的對數）。

許多有關質數的問題依然未解，如哥德巴赫猜想（每個大於 2 的偶數可表示成兩個質數之和）及孿生質數猜想（存在無窮多對相差 2 的質數）。這些問題促進了數論各個分支的發展，主要在於數字的解析或代數方面。質數被用於資訊科技裡的幾個程序中，如公鑰加密利用了難以將大數分解成其質因數之類的性質。質數亦在其他數學領域裡形成了各種廣義化的質數概念，主要出現在代數裡，如質元素及質理想。

## 定義和例子

一個自然數（如 1、2、3、4、5、6 等）若恰有兩個正因數（1 及此數本身），則稱之為**質數**。大於 1 的自然數若不是質數，則稱之為合數。

在數字 1 至 6 間，數字 2、3 與 5 為質數，1、4 與 6 則不是質數。1 不是質數，其理由見下文。2 是質數，因為只有 1 與 2 可整除該數。接下來，3 亦為質數，因為 1 與 3 可整除 3，3 除以 2 會餘 1。因此，3 為質數。不過，4 是合數，因為 2 是另一個（除 1 與 4 外）可整除 4 的數：

　
: 4 = 2 · 2.

5 又是個質數：數字 2、3 與 4 均不能整除 5。接下來，6 會被 2 或 3 整除，因為

　
: 6 = 2 · 3.

因此，6 不是質數。右圖顯示 12 不是質數：12 = 3 · 4。不存在大於 2 的偶數為質數，因為依據定義，任何此類數字 $n$ 均至少有三個不同的因數，即 1、2 與 $n$ 。這意指 $n$ 不是質數。因此，「奇質數」係指任何大於 2 的質數。類似地，當使用一般的十進位制時，所有大於 5 的質數，其尾數均為 1、3、7 或 9，因為尾數 0、2、4、6、8 為 2 的倍數，尾數為 0 或 5 的數字為 5 的倍數。

若 $n$ 為一自然數，則 1 與 $n$ 會整除 $n$ 。因此，質數的條件可重新敘述為：一個數字為質數，若該數大於 1，且沒有

　
: $2,3,\ldots ,n-1$

會整除 $n$ 。另一種敘述方式為：一數 $n>1$ 為質數，若不能寫成兩個整數 $a$ 與 $b$ 的乘積，其中這兩數均大於 1：

　
: $n=a\cdot b$ .

換句話說， $n$ 為質數，若 $n$ 無法分成數量都大於 1 且都相同的各組。

由所有質數組成之集合通常標記為 **P** 或 $\mathbb {P} $ 。

前 168 個質數（所有小於 1000 的質數）為 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 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, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, ...（OEIS 數列 A000040）。

## 算術基本定理

質數對於數論與一般數學的重要性來自於「算術基本定理」。該定理指出，每個大於 1 的整數均可寫成一個以上的質數之乘積，且除了質因數的排序不同外是唯一的。質數可被認為是自然數的「基本建材」，例如：

　
:

如同此例一般，相同的因數可能出現多次。一個數 n 的分解：

　
: $n=p_{1}\cdot p_{2}\cdot \ldots \cdot p_{t}$

成（有限多個）質因數 $p_{1}$ 、 $p_{2}$ 、……、 $p_{t}$ ，稱之為 $n$ 的「因數分解」。算術基本定理可以重新敘述為，任一質數分解除了因數的排序外，都是唯一的。因此，儘管實務上存在許多質數分解演算法來分解較大的數字，但最後都會得到相同的結果。

若 $p$ 為質數，且 $p$ 可整除整數的乘積 $ab$ ，則 $p$ 可整除 $a$ 或可整除 $b$ 。此一命題被稱為歐幾里得引理，被用來證明質數分解的唯一性。

### 1 是否為質數

最早期的希臘人甚至不將 1 視為是一個數字，因此不會認為 1 是質數。到了中世紀與文藝復興時期，許多數學家將 1 納入作為第一個質數。到 18 世紀中期，克里斯蒂安・哥德巴赫在他與李昂哈德・歐拉著名的通信裡將 1 列為第一個質數，但歐拉不同意。然而，到了 19 世紀，仍有許多數學家認為數字 1 是個質數。例如，德里克・諾曼・雷默（Derrick Norman Lehmer）在他那最大達 10,006,721 的質數列表中，將 1 列為第 1 個質數。昂利・勒貝格據說是最後一個稱 1 為質數的職業數學家。到了 20 世紀初，數學家開始認為 1 不是個質數，但反而作為「單位」此一特殊類別。

許多數學成果在稱 1 為質數時，仍將有效，但歐幾里何的算術基本定理（如上所述）則無法不重新敘述而仍然成立。例如，數字 15 可分解成 3 · 5 及 1 · 3 · 5；若 1 被允許為一個質數，則這兩個表示法將會被認為是將 15 分解至質數的不同方法，使得此一定理的陳述必須被修正。同樣地，若將 1 視為質數，埃拉托斯特尼篩法將無法正常運作：若將 1 視為質數，此一篩法將會排除掉所有 1 的倍數（即所有其他的數），只留下數字 1。此外，質數有幾個 1 所沒有的性質，如歐拉函數的對應值，以及除數函數的總和。

## 歷史

在古埃及人的倖存紀錄中，有跡象顯示他們對質數已有部分認識：例如，在萊因德數學紙草書中的古埃及分數展開時，對質數與對合數有著完全不同的類型。不過，對質數有過具體研究的最早倖存紀錄來自古希臘。公元前 300 年左右的《幾何原本》包含與質數有關的重要定理，如有無限多個質數，以及算術基本定理。歐幾里得亦展示如何從梅森質數建構出完全數。埃拉托斯特尼提出的埃拉托斯特尼篩法是用來計算質數的一個簡單方法，雖然今天使用電腦發現的大質數無法使用這個方法找出。

希臘之後，到 17 世紀之前，質數的研究少有進展。1640 年，皮埃爾・德・費馬敘述了費馬小定理（之後才被萊布尼茨與歐拉證明）。費馬亦推測，所有具 $2^{2^{n}}+1$ 形式的數均為質數（稱之為費馬數），並驗證至 $n=4$ （即 216+ 1）不過，後來由歐拉發現，下一個費馬數 232+ 1 即為合數，且實際上其他已知的費馬數都不是質數。法國修道士馬蘭・梅森發現有的質數具 $2^{p}-1$ 的形式，其中 $p$ 為質數。為紀念他的貢獻，此類質數後來被稱為梅森質數。

歐拉在數論中的成果，許多與質數有關。他證明無窮級數 ${\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{5}}+{\frac {1}{7}}+{\frac {1}{11}}+\ldots $ 會發散。1747 年，歐拉證明每個偶完全數都確實為 $2^{p-1}(2^{p}-1)$ 的形式，其中第二個因數為梅森質數。

19 世紀初，勒壤得與高斯獨立推測，當 $x$ 趨向無限大時，小於 $x$ 的質數數量會趨近於 ${\frac {x}{\ln x}}$ ，其中 $\ln x$ 為 $x$ 的自然對數。黎曼於 1859 年有關 ζ 函數的論文中勾勒出一個程式，導出了質數定理的證明。其大綱由雅克・阿達馬與查爾斯・貞・德・拉・瓦萊 - 普森所完成，他們於 1896 年獨立證明出質數定理。

證明一個大數是否為質數通常無法由試除法來達成。許多數學家已研究過大數的質數測試，通常侷限於特定的數字形式。其中包括費馬數的貝潘測試（1877 年）、普羅絲定理（約 1878 年）、盧卡斯 - 萊默質數判定法（1856 年起）及廣義盧卡斯質數測試。較近期的演算法，如 APRT-CL、ECPP 及 AKS 等，均可作用於任意數字上，但仍慢上許多。

長期以來，質數被認為在純數學以外的地方只有極少數的應用。到了 1970 年代，發明公共密鑰加密這個概念之後，情況改變了，質數變成了 RSA 加密演算法等一階演算法之基礎。

自 1951 年以來，所有已知最大的質數都由電腦所發現。對更大質數的搜尋已在數學界以外的地方產生出興趣。網際網路梅森質數大搜索及其他用來尋找大質數的分散式運算計畫變得流行，在數學家仍持續與質數理論奮鬥的同時。

## 質數的數目

存在無限多個質數。另一種說法為，質數序列

　
: 2, 3, 5, 7, 11, 13, ...

永遠不會結束。此一陳述被稱為「歐幾里得定理」，以古希臘數學家歐幾里得為名，因為他提出了該陳述的第一個證明。已知存在其他更多的證明，包括歐拉的分析證明、哥德巴赫依據費馬數的證明、弗斯滕伯格使用一般拓撲學的證明，以及庫默爾優雅的證明。

### 歐幾里得的證明

歐幾里得的證明取任一個由質數所組成的有限集合 $S$ 。該證明的關鍵想法為考慮 $S$ 內所有質數相乘後加一的一個數字：

　
: $N=1+\prod _{p\in S}p$ 。

如同其他自然數一般， $N$ 可被至少一個質數整除（即使 N 本身為質數亦同）。

任何可整除 N 的質數都不可能是有限集合 $S$ 內的元素（質數），因為後者除 N 都會餘 1。所以， $N$ 可被其他質數所整除。因此，任一個由質數所組成的有限集合，都可以擴展為更大個由質數所組成之集合。

這個證明通常會被錯誤地描述為，歐幾里得一開始假定一個包含所有質數的集合，並導致矛盾；或者是，該集合恰好包含 n 個最小的質數，而不任意個由質數所組成之集合。今日， $n$ 個最小質數相乘後加一的一個數字，被稱為第 $n$ 個歐幾里得數。

### 歐拉的解析證明

歐拉的證明使用到質數倒數的總和

　
: $S(p)={\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{5}}+{\frac {1}{7}}+\cdots +{\frac {1}{p}}$ 。

當 $p$ 夠大時，該和會大於任意實數。這可證明，存在無限多個質數，否則該和將只會增長至達到最大質數 $p$ 為止。 $S(p)$ 的增加率可使用梅滕斯第二定理來量化。比較總和

　
: ${\frac {1}{1^{2}}}+{\frac {1}{2^{2}}}+{\frac {1}{3^{2}}}+\cdots +{\frac {1}{n^{2}}}=\sum _{i=1}^{n}{\frac {1}{i^{2}}}$

當 $n$ 趨向無限大時，此和不會變成無限大（見巴塞爾問題）。這意味著，質數比自然數的平方更常出現。布朗定理指出，孿生質數倒數的總和

　
: $\left({{\frac {1}{3}}+{\frac {1}{5}}}\right)+\left({{\frac {1}{5}}+{\frac {1}{7}}}\right)+\left({{\frac {1}{11}}+{\frac {1}{13}}}\right)+\cdots =\sum \limits _{\begin{smallmatrix}p{\text{ prime, }}\\p+2{\text{ prime}}\end{smallmatrix}}{\left({{\frac {1}{p}}+{\frac {1}{p+2}}}\right)},$

是有限的。

## 測試質數與整數分解

確認一個數 $n$ 是否為質數有許多種方法。最基本的程序為試除法，但因為速率很慢，沒有什麼實際用處。有一類現代的質數測試可適用於任意數字之上，另有一類更有效率的測試方法，則只能適用於特定的數字之上。大多數此類方法只能辨別 $n$ 是否為質數。也能給出 $n$ 的一個（或全部）質因數之程序稱之為因數分解演算法。

### 試除法

測試 $n$ 是否為質數的最基本方法為試除法。此一程序將 n 除以每個大於 1 且小於等於 $n$ 的平方根之整數 $m$ 。若存在一個相除為整數的結果，則 $n$ 不是質數；反之則是個質數。實際上，若 $n=ab$ 是個合數（其中 $a$ 與 $b\neq 1$ ），則其中一個因數 $a$ 或 $b$ 必定至大為 ${\sqrt {n}}$ 。例如，對 $n=37$ 使用試除法，將 37 除以 $m=2,3,4,5,6$ ，沒有一個數能整除 37，因此 37 為質數。此一程序若能知道直至 ${\sqrt {n}}$ 的所有質數列表，則可以只檢查 $m$ 為質數的狀況，以提升效率。例如，為檢查 37 是否為質數，只有 3 個相除是必要的（ $m=2,3,5$ ），因為 4 與 6 為合數。

作為一個簡單的方法，試除法在測試大整數時很快地會變得不切實際，因為可能的因數數量會隨著 n 的增加而迅速增加。依據下文所述之質數定理，小於 ${\sqrt {n}}$ 的質數之數量約為 ${\frac {\sqrt {n}}{\ln {\sqrt {n}}}}$ ，因此使用試除法測試 $n$ 是否為質數時，大約會需要用到這麼多的數字。對 $n=10^{20}$ ，此一數值約為 4.5 億，對許多實際應用而言都太過龐大。

### 篩法

一個能給出某個數值以下的所有質數之演算法，稱之為質數篩法，可用於只使用質數的試除法內。最古老的一個例子為埃拉托斯特尼篩法（見上文），至今仍最常被使用。阿特金篩法為另外一例。在電腦出現之前，篩法曾被用來給出 107 以下的質數列表。

### 質數測試與質數證明

現代測試一般的數字 $n$ 是否為質數的方法可分成兩個主要類型，隨機（或「蒙地卡羅」）與確定性演算法。確定性演算法可肯定辨別一個數字是否為質數。例如，試除法即是個確定性演算法，因為若正確執行，該方法總是可以辨別一個質數為質數，一個合數為合數。隨機演算法一般比較快，但無法完全證明一個數是否為質數。這類測試依靠部分隨機的方法來測試一個給定的數字。例如，一測試在應用於質數時總是會通過，但在應用於合數時通過的機率為 $p$ 。若重復這個測試 $n$ 次，且每次都通過，則該數為合數的機率為 ${\frac {1}{(1-p)^{n}}}$ ，會隨著測試次數呈指數下滑，因此可越來越確信（雖然總是無法完全確信）該數為質數。另一方面，若測試曾失敗過，則可知該數為合數。

隨機測試的一個特別簡單的例子為費馬質數判定法，使用到對任何整數 $a$ ， $n^{p}\equiv n(\mod p)$ ，其中 $p$ 為質數的這個事實（費馬小定理）。若想要測試一個數字 $b$ 是否為質數，則可隨機選擇 $n$ 來計算 $n^{b}(\mod b)$ 的值。這個測試的缺點在於，有些合數（卡邁克爾數）即使不是質數，也會符合費馬恆等式，因此這個測試無法辨別質數與卡邁克爾數，最小的三個卡邁克爾數為 561，1105，1729。卡邁克爾數比質數還少上許多，所以這個測試在實際應用上還是有用的。費馬質數判定法更強大的延伸方法，包括貝利 - PSW、米勒 - 拉賓與 Solovay-Strassen 質數測試，都保證至少在應用於合數時，有部分時候會失敗。

確定性演算法不會將合數錯誤判定為質數。在實務上，最快的此類方法為橢圓曲線質數證明。其運算時間是透過實務分析出來的，不像最新的 AKS 質數測試，有已被嚴格證明出來的複雜度。確定性演算法通常較隨機演算法來得慢，所以一般會先使用隨機演算法，再採用較費時的確定性演算法。

下面表格列出一些質數測試。運算時間以被測試的數字 $n$ 來表示，並對隨機演算法，以 $k$ 表示其測試次數。此外， $\varepsilon $ 是指一任意小的正數， $\log $ 是指一無特定基數的對數。大 O 符號表示，像是在橢圓曲線質數證明裡，所需之運算時間最長為一常數（與 n 無關，但會與 ε 有關）乘於 log5+ε(_n_)。

### 專用目的演算法與最大已知質數

除了前述可應用於任何自然數 n 之上的測試外，一些更有效率的質數測試適用於特定數字之上。例如，盧卡斯質數測試需要知道 _n_ − 1 的質因數，而盧卡斯 - 萊默質數測試則需要以 _n_ + 1 的質因數作為輸入。例如，這些測試可應用在檢查

　
: _n_! ± 1 = 1 · 2 · 3 · ... · _n_ ± 1

是否為一質數。此類形式的質數稱之為階乘質數。其他具 p+1 或 p-1 之類形式的質數還包括索菲・熱爾曼質數（具 2p+1 形式的質數，其中 p 為質數）、質數階乘質數、費馬質數與梅森質數（具 2p − 1 形式的質數，其中 p 為質數）。盧卡斯 - 雷默質數測試對這類形式的數特別地快。這也是為何自電腦出現以來，最大已知質數總會是梅森質數的原因。

費馬質數具下列形式

　
: _F_k = 22k + 1,

其中，k 為任意自然數。費馬質數以皮埃爾・德・費馬為名，他猜想此類數字 _Fk_ 均為質數。費馬認為 _Fk_ 均為質數的理由為此串列的前 5 個數字（3、5、17、257 及 65537）為質數。不過，_F_5 卻為合數，且直至 2015 年發現的其他費馬數字也全都是合數。一個正 n 邊形可用尺規作圖，若且唯若

　
: _n_ = 2i · _m_

其中，m 為任意個不同費馬質數之乘積，及 i 為任一自然數，包括 0。

下列表格給出各種形式的最大已知質數。有些質數使用分散式計算找到。2009 年，網際網路梅森質數大搜索因為第一個發現具至少 1,000 萬個數位的質數，而獲得 10 萬美元的獎金。電子前哨基金會亦為具至少 1 億個數位及 10 億個數位的質數分別提供 15 萬美元及 25 萬美元的獎金。

### 整數分解

給定一合數 n，給出一個（或全部）質因數的工作稱之為 n 的因數分解。橢圓曲線分解是一個依靠橢圓曲線上的運算來分解質因數的演算法。

## 質數分布

1975 年，數論學家唐・察吉爾評論質數

> 像生長於自然數間的雜草，似乎不服從機率之外的法則，（但又）表現出驚人的規律性，並有規範其行為之法則，且以軍事化的精準度遵守著這些法則。
> 
> 

大質數的分布，如在一給定數值以下有多少質數這個問題，可由質數定理所描述；但有效描述第 n 個質數的公式則仍未找到。

存在任意長的連續非質數數列，如對每個正整數 $n$ ，從 $(n+1)!+2$ 至 $(n+1)!+n+1$ 的 $n$ 個連續正整數都會是合數（因為若 $k$ 為 2 至 $n+1$ 間的一整數， $(n+1)!+k$ 就可被 k 整除）。

狄利克雷定理表示，取兩個互質的整數 a 與 b，其線性多項式

　
: $p(n)=a+bn\,$

會有無限多個質數值。該定理亦表示，這些質數值的倒數和會發散，且具有相同 b 的不同多項式會有差不多相同的質數比例。

有關二次多項式的相關問題則尚無較好之理解。

### 質數的公式

對於質數，還沒有一個已知的有效公式。例如，米爾斯定理與賴特所提的一個定理表示，存在實常數 A>1 與 μ，使得

　
: $\left\lfloor A^{3^{n}}\right\rfloor {\text{ and }}\left\lfloor 2^{\dots ^{2^{2^{\mu }}}}\right\rfloor $

對任何自然數 n 而言，均為質數。其中， $\lfloor -\rfloor $ 為高斯符號，表示不大於符號內數字的最大整數。第二個公式可使用伯特蘭 - 柴比雪夫定理得證（由柴比雪夫第一個證得）。該定理表示，總是存在至少一個質數 p，使得 _n_ < _p_ < 2_n_− 2，其中 n 為大於 3 的任一自然數。第一個公式可由威爾遜定理導出，每個不同的 n 會對應到不同的質數，除了數字 2 會有多個 n 對應到外。不過，這兩個公式都需要先計算出 A 或 μ 的值來。

不存在一個只會產生質數值的非常數多項式，即使該多項式有許多個變數。不過，存在具 9 個變數的丟番圖方程式，其參數具備以下性質：該參數為質數，若且唯若其方程組有自然數解。這可被用來獲得其所有「正值」均為質數的一個公式。

### 一特定數以下的質數之數量

質數計算函數 π(n) 被定義為不大於 n 的質數之數量。例如，π(11) = 5，因為有 5 個質數小於或等於 11。已知有演算法可比去計算每個不大於 n 的質數更快的速率去計算 π(n) 的值。質數定理表示，π(n) 的可由下列公式近似給出：

　
: $\pi (n)\approx {\frac {n}{\ln n}},$

亦即，π(n) 與等式右邊的值在 n 趨近於無限大時，會趨近於 1。這表示，小於 n 的數字為質數的可能性（大約）與 n 的數位呈正比。對 π(n) 更精確的描述可由對數積分給出：

　
: $\operatorname {Li} (n)=\int _{2}^{n}{\frac {dt}{\ln t}}$ 。

質數定理亦薀涵著對第 n 個質數 _pn_（如 _p_1 = 2、_p_2 = 3 等）的大小之估算：當數字大到某一程度時，_pn_ 的值會變得約略為 _n_ log(_n_)。特別的是，質數間隙，即兩個連續質數 _p_n 與 _p_n+1 間的差會變得任意地大。後者可由數列 _n_! + 2, _n_! + 3,…, _n_! + _n_（其中 n 為任一自然數）看出。

### 等差數列

等差數列是指由被一固定數（模）q 除後會得到同一餘數的自然數所組成之集合。例如：

　
: 3, 12, 21, 30, 39, ...,

是一個等差數列，模 q = 9。除了 3 以外，其中沒有一個數會是質數，因為 3 + 9_n_ = 3(1 + 3_n_)，所以此一數列裡的其他數字均為合數。（一般來所有大於 q 的質數都具有 _q_#·_n_ + _m_ 的形式，其中 0 <_m_ < _q_#，且 m 沒有不大於 q 的質因數。）因此，數列

　
: _a_, _a_ + _q_, _a_ + 2_q_, _a_ + 3_q_,…

只在 a 與 q 互質（其最大公因數為 1）之時，可以有無限多個質數。若滿足此一必要條件，狄利克雷定理表示，該數列含有無限多個質數。下圖描述 _q_ = 9 時的情形：數字每遇到 9 的倍數就會再再由下往上纏一次。質數以紅底標記。行（數列）開始於 a = 3, 6, 9 者至多只包含一個質數。其他行（a = 1, 2, 4, 5, 7, 8）則均包含無限多個質數。更甚之，質數以長期來看，會均勻分布於各行之中，亦即每個質數模 9 會與 6 個數其中一數同餘的機率均為 1/6。

格林 - 陶定理證明，存在由任意多個質數組成的等差數列。一個奇質數 p 可表示成兩個平方數之和 _p_ = _x_2 + _y_2，若且唯若 p 同餘於 1 模 4（費馬平方和定理）。

### 二次多項式的質數值

歐拉指出函數

　
: $n^{2}+n+41\,$

於 0 ≤ _n_ < 40 時會給出質數，此一事實導致了艱深的代數數論，或更具體地說為黑格納數。當 n 更大時，該函數會給出合數值。哈代 - 李特伍德猜想（Hardy-Littlewood conjecture）能給出一個有關具整數係數 a、b 與 c 的二次多項式

　
: $f(n)=ax^{2}+bx+c\,$

的值為質數之機率的一個漸近預測，並能以對數積分 Li (n) 及係數 a、b、c 來表示。不過，該程式已被證實難以取得：仍未知是否存在一個二次多項式（_a_ ≠ 0）能給出無限多個質數。烏嵐螺旋將所有自然數以螺旋的方法描繪。令人驚訝的是，質數會群聚在某些對角線上，表示有些二次多項式會比其他二次多項式給出更多個質數值來。

## 未解決的問題

### ζ 函數與黎曼猜想

黎曼 ζ 函數 ζ(s) 被定義為一無窮級數

　
: $\zeta (s)=\sum _{n=1}^{\infty }{\frac {1}{n^{s}}},$

其中，s 為實數部分大於 1 的一個複數。由算術基本定理可證得，該級數會等於下面的無窮乘積

　
: $\prod _{p{\text{ prime}}}{\frac {1}{1-p^{-s}}}$ 。

ζ 函數與質數密切相關。例如，存在無限多個質數這個事實也可以使用 ζ 函數看出：若只有有限多個質數，則 ζ(1) 將會是個有限值。不過，調和級數 1 + 1/2 + 1/3 + 1/4 + ... 會發散，所以必須有無限多個質數。另一個能看見 ζ 函數的豐富性，並一瞥現代代數數論的例子為下面的恆等式（巴塞爾問題，由歐拉給出）：

　
: $\zeta (2)=\prod _{p}{\frac {1}{1-p^{-2}}}={\frac {\pi ^{2}}{6}}$ 。

ζ(2) 的倒數 6/π2，是兩個隨機選定的數字會互質的機率。

未被證明的「黎曼猜想」，於 1859 年提出，表示除 _s_ = −2, −4, ..., 外，ζ 函數所有的根，其實數部分均為 1/2。此一猜想與質數間的關連在於，該猜想實際上是在說，質數在正整數中出現頻率和統計學的隨機不同；若假設為真，質數計算函數便可有效掌握，在大數時不再需要近似求值。從物理的觀點來看，這大約是在說，質數分布的不規則性僅來自於隨機的雜訊。從數學的觀點來看，則大約是在說，質數的漸近分布（質數定理表示小於 x 的質數約有 x/log x 個）在 x 周圍的區間內，於區間長度遠小於 x 的平方根時亦成立。此一猜想一般認為是正確的。

### 其他猜想

除了黎曼猜想之外，還有許多其他的猜想存在。雖然這些猜想的陳述大多很簡單，但許多猜想經過了數十年仍提不出證明，如 4 個蘭道問題，從 1912 年提出至今仍然未解。其中一個為哥德巴赫猜想，該猜想認為每個大於 2 的偶數 n 都可表示成兩個質數之和。至於 2011 年 2 月，這個猜想對最大達 _n_ = 2 · 1017 的所有數字都會成立。較弱形式的哥德巴赫猜想已被證明，如維諾格拉多夫定理，該定理表示每個足夠大的奇數都可表示成三個質數之和。陳氏定理表示，每個足夠大的偶數都可表示成一個質數與一個半質數（兩個質數的乘積）之和。此外，任一個偶數均可寫成六個質數之和。數論研究這些問題的分支稱之為加法數論。反哥德巴赫猜想，所有的正偶數 n 都可以表示成兩個質數之差，但此猜想可由波利尼亞克猜想類推證明。

其他猜想處理是否有無限多個具某些限制的質數這類問題。據猜想，存在無限多個費波那契質數與無限多個梅森質數，但沒有無限多個費馬質數。還不知道是否存在無限多個維費里希質數與歐幾里得質數。

第三種類型的猜想涉及到質數的分布情形。據猜想，存在無限多對孿生質數，即有無限多對相差 2 的質數（孿生質數猜想）。波利尼亞克猜想是比孿生質數猜想更強的一個猜想，該猜想表示存在無限多對相差 2n 的連續質數。據猜想，存在無限多個具 _n_2+ 1 形式的質數。上述猜想都是申策爾猜想的特例。布羅卡猜想表示，在兩個大於 2 的連續質數之平方數之間，總是會有至少 4 個質數。勒讓德猜想表示，對每個正整數 n，_n_2 與 (_n_ + 1)2 間總會存在一個質數。克拉梅爾猜想可導出勒讓德猜想。

## 應用

長期以來，數論，尤其是對質數的研究，一般都會被認為是典型的純數學，除了求知的趣味之外，沒有其他應用。特別是，一些數論學家，如英國數學家戈弗雷・哈羅德・哈代即對其工作絕對不會有任何在軍事上的重大性感到自豪。然而，此一觀點在 1970 年代時遭到粉碎，當質數被公開宣布可以作為產生公鑰加密演算法的基礎之時。質數現在也被用在雜湊表與偽亂數產生器裡。

旋轉機被設計成在每個轉片上有不同數目的銷，在每個轉片上的銷的數量都會是質數，亦或是會與其他轉片上的銷的數量互質。這有助於在重復所有的組合之前，讓所有轉片的可能組合都能出現過一次。

國際標準書號的最後一碼為校驗碼，其演算法使用到了 11 是個質數的這個事實。

在汽車變速箱齒輪的設計上，相鄰的兩個大小齒輪齒數最好設計成質數，以增加兩齒輪內兩個相同的齒相遇嚙合次數的最小公倍數，可增強耐用度減少故障。

在害蟲的生物生長週期與殺蟲劑使用之間的關係上，殺蟲劑的質數次數的使用也得到了證明。實驗表明，質數次數地使用殺蟲劑是最合理的：都是使用在害蟲繁殖的高潮期，而且害蟲很難産生抗藥性。

以質數形式無規律變化的飛彈和魚雷可以使敵人不易攔截。

### 模一質數與有限體之運算

「模運算」使用下列數字修改了一般的運算

　
: $\{0,1,2,\dots ,n-1\},\,$

其中 n 是個固定的自然數，稱之為「模」。計算加法、減法及乘法都與一般的運算一樣，不過負數或大於 _n_− 1 的數字出現時，會被除以 n 所得的餘數取代。例如，對 n=7，3+5 為 1，而不是 8，因為 8 除以 7 餘 1。這通常念為「3+5 同餘於 1 模 7」，並標記為

　
: $3+5\equiv 1{\pmod {7}}$ 。

同樣地，6 + 1 ≡ 0 (mod 7)、2 - 5 ≡ 4 (mod 7)，因為 -3 + 7 = 4，以及 3・4 ≡ 5 (mod 7)，因為 12 除以 7 餘 5。加法與乘法在整數裡常見的標準性質在模運算裡也依然有效。使用抽象代數的說法，由上述整數所組成之集合，亦標記為 Z/nZ，且因此為一可交換環。不過，除法在模運算裡不一定都是可行的。例如，對 n=6，方程式

　
: $3\cdot x\equiv 2{\pmod {6}},$

的解 x 會類比於 2/3，無解，亦可透過計算 3・0、...、3・5 模 6 看出。不過，有關質數的不同性質如下：除法在模運算裡是可行的，若且唯若 n 為質數。等價地說，n 為質數，若且唯若所有滿足 2 ≤ _m_ ≤ _n_ − 1 的整數 m 都會與 n 互質，亦即其公因數只有 1。實際上，對 n=7，方程式

　
: $3\cdot x\equiv 2\ \ (\operatorname {mod} \ 7),$

會有唯一的解 _x_ = 3。因此，對任何質數 p，**Z**/_p_**Z**（亦標記為 **F**p）也會是個體，或更具體地說，是個有限體，因為該集合包含有限多（即 p）個元素。

許多定理可以透過從此一抽象的方式檢查 **F**p 而導出。例如，費馬小定理表示

　
: $a^{p-1}\equiv 1(\operatorname {mod} \ p)$

，其中 a 為任一不被 p 整除的整數。該定理即可使用這些概念證得。這意味著

　
: $\sum _{a=1}^{p-1}a^{p-1}\equiv (p-1)\cdot 1\equiv -1{\pmod {p}}$ 。

吾鄉 - 朱加猜想表示，上述公式亦是 p 為質數的必要條件。另一個費馬小定理的推論如下：若 p 為 2 與 5 之外的其他質數，1/p 總是個循環小數，其週期為 _p_ − 1 或 _p_ − 1 的因數。分數 1/p 依 q（10 以外的整數）為基底表示亦有類似的效果，只要 p 不是 q 的質因數的話。威爾遜定理表示，整數 _p_> 1 為質數，若且唯若階乘 (_p_− 1)! + 1 可被 p 整除。此外，整數 n > 4 為合數，若且唯若 (_n_− 1)! 可被 n 整除。

### 其他數學裡出現的質數

許多數學領域裡會大量使用到質數。舉有限群的理論為例，西羅定理即是一例。該定理表示，若 G 是個有限群，且 _pn_ 為質數 p 可整除 G 的階的最大冪次，則 G 會有個 _pn_ 階的子群。此外，任意質數階的群均為循環群（拉格朗日定理）。

### 公開金鑰加密

幾個公開金鑰加密演算法，如 RSA 與迪菲－赫爾曼金鑰交換，都是以大質數為其基礎（如 512 位元的質數常被用於 RSA 裡，而 1024 位元的質數則一般被迪菲 - 赫爾曼金鑰交換所採用）。RSA 依靠計算出兩個（大）質數的相乘會比找出相乘後的數的兩個質因數容易出許多這個假設。迪菲－赫爾曼金鑰交換依靠存在模冪次的有效演算法，但相反運算的離散對數仍被認為是個困難的問題此一事實。

### 自然裡的質數

週期蟬屬裡的蟬在其演化策略上使用到質數。蟬會在地底下以幼蟲的形態度過其一生中的大部分時間。週期蟬只會在 7 年、13 年或 17 年後化蛹，然後從洞穴裡出現、飛行、交配、產卵，並在至多數週後死亡。此一演化策略的原因據信是因為若出現的週期為質數年，掠食者就很難演化成以週期蟬為主食的動物。若週期蟬出現的週期為非質數年，如 12 年，則每 2 年、3 年、4 年、6 年或 12 年出現一次的掠食者就一定遇得到週期蟬。經過 200 年以後，假設 14 年與 15 年出現一次的週期蟬，其掠食者的平均數量，會比 13 年與 17 年出現一次的週期蟬，高出 2%。雖然相差不大，此一優勢似乎已足夠驅動天擇，選擇具質數年生命週期的這些昆蟲。

據猜測，ζ 函數的根與複數量子系統的能階有關。

## 推廣

質數的概念是如此的重要，以致此一概念被以不同方式推廣至數學的不同領域裡去。通常，「質」（prime）可在適當的意義下，用來表示具有最小性或不可分解性。例如，質體是指一個包含 0 與 1 的體 F 的最小子體。質體必為有理數或具有 p 個元素的有限體，這也是其名稱的緣由。若任一物件基本上均可唯一地分解成較小的部分，則這些較小的部分也會用「質」這個字來形容。例如，在紐結理論裡，質紐結是指不可分解的紐結，亦即該紐結不可寫成兩個非平凡紐結的連通和。任一紐結均可唯一地表示為質紐約的連通和。質模型與三維質流形亦為此類型的例子。

### 環內的質元素

質數應用於任一可交換環 R（具加法、減法與乘法的代數結構）的元素，可產生兩個更為一般的概念：「質元素」與「不可約元素」。R 的元素稱為質元素，若該元素不為 0 或單位元素，且給定 R 內的元素 x 與 y，若 p 可除以 xy，則 p 可除以 x 或 y。一元素稱為不可約元素，若該元素不為單位元素，且無法寫成兩個不是單位元素之環元素的乘積。在整數環 Z 裡，由質元素所組成的集合等於由不可約元素所組成的集合，為

　
: $\{\dots ,-11,-7,-5,-3,-2,2,3,5,7,11,\dots \}\,$ 。

在任一環 R 裡，每個質元素都是不可約元素。反之不一定成立，但在唯一分解整環裡會成立。

算術基本定理在唯一分解整環裡仍然成立。此類整環的一個例子為高斯整數 Z [i]，由具 a + bi（其中 a 與 b 為任意整數）形式的複數所組成之集合。其質元素稱之為「高斯質數」。不是所有的質數都是高斯質數：在這個較大的環 Z [i] 之中，2 可被分解成兩個高斯質數 (1 + i) 與 (1 - i) 之乘積。有理質數（即在有理數裡的質元素），具 4k+3 形式者為高斯質數；具 4k+1 形式者則不是。

### 質理想

在環論裡，數的概念一般被理想所取代。「質理想」廣義化了質元素的概念，為由質元素產生的主理想，是在交換代數、代數數論與代數幾何裡的重要工具與研究對象。整數環的質理想為理想 (0)、(2)、(3)、(5)、(7)、(11)、… 算術基本定理被廣義化成準素分解，可將每個在可交換諾特環裡的理想表示成準質理想（為質數冪次的一適合廣義化）的交集。

透過環的譜這個概念，質理想成為代數幾何物件的點。算術幾何也受益於這個概念，且許多概念會同時存在於幾何與數論之內。例如，對一擴張體的質理想分解（這是代數數論裡的一個基本問題），與幾何裡的分歧具有某些相似之處。此類分歧問題甚至在只關注整數的數論問題裡也會出現。例如，二次體的整數環內的質理想可被用來證明二次互反律。二次互反律討論下面二次方程式

　
: $x^{2}\equiv p\ \ ({\text{mod }}q),\,$

是否有整數解，其中 x 為整數，p 與 q 為（一般）質數。早期對費馬最後定理證明之嘗試，於恩斯特・庫默爾引入正則質數後達到了高潮。正則質數是指無法在由下列式子（其中 _a_0、…、_a_p−1 為整數，ζ 則是能使 ζp = 1 的複數）

　
: $a_{0}+a_{1}\zeta +\cdots +a_{p-1}\zeta ^{p-1}\,,$

組成的環裡，使得唯一分解定理失效的質數。

### 賦值

賦值理論研究由一個體 K 映射至實數 R 的某個函數（稱之為賦值）。每個此類賦值都能給出一個 K 上的拓撲，且兩個賦值被稱為等價，若兩者有相同拓撲。K 的質數為一賦值的等價類。例如，一個有理數 q 的 p 進賦值被定義為整數 _vp_(_q_)，使得

　
: $q=p^{v_{p}(q)}{\frac {r}{s}},$

其中 r 與 s 不被 p 所整除。例如，_v_3(18/7) = 2。p 進範數被定義為

　
: $\left|q\right|_{p}:=p^{-v_{p}(q)}.\,$

特別的是，當一個數字乘上 p 時，其範數會變小，與一般的絕對賦值（亦稱為無限質數）形成明顯的對比。當透過絕對賦值完備有理數會得出由實數所組成的體，透過 p 進範數完備有理數則會得出由 p 進數所組成的體。實際上，依據奧斯特洛夫斯基定理，上述兩種方法是完備有理數的所有方法。一些與有理數或更一般化之大域體有關的算術問題，可能可以被轉換至完備（或局部）體上。此一局部 - 全域原則再次地強調了質數對於數論的重要性。

## 在藝術與文學裡

質數也影響了許多的藝術家與作家。法國作曲家奧立佛・梅湘使用質數創造出無節拍音樂。在《La Nativite du Seigneur》與《Quatre etudes de rythme》等作品裡，梅湘同時採用由不同質數給定之長度的基調，創造出不可預測的節奏：第三個練習曲《Neumes rythmiques》中出現了質數 41、43、47 及 53。據梅湘所述，此類作曲方式是「由自然的運動，自由且不均勻的持續運動中獲得的靈感」。

NASA 科學家卡爾・薩根在他的科幻小說《接觸未來》（_Contact_）裡，認為質數可作為與外星人溝通的一種方式。這種想法是他與美國天文學家法蘭克・德雷克於 1975 年閒聊時形成的。

許多電影，如《異次元殺陣》（_Cube_）、《神鬼尖兵》（_Sneakers_）、《越愛越美麗》（_The Mirror Has Two Faces_）及《美麗境界》（_A Beautiful Mind_），均反映出大眾對質數與密碼學之神秘的迷戀。保羅・裘唐諾所著的小說《質數的孤獨》（The Solitude of Prime Numbers）裡，質數被用來比喻寂寞與孤獨，被描述成整數之間的「局外人」。

荒木飛呂彥所創作的日本漫畫《JoJo 的奇妙冒險》第六部《石之海》的反派普奇神父喜歡數質數，他認為質數是孤獨的數字，並透過數質數安撫他緊張的情緒。

## 另見

## 註記

## 參考資料

* Apostol, Thomas M., Introduction to Analytic Number Theory, New York: Springer, 1976, ISBN 0-387-90163-9
* Conway, John Horton; Guy, Richard K., The Book of Numbers, New York: Copernicus, 1996, ISBN 978-0-387-97993-9
* Crandall, Richard; Pomerance, Carl, Prime Numbers: A Computational Perspective 2nd, Berlin, New York: Springer-Verlag, 2005, ISBN 978-0-387-25282-7
* Derbyshire, John, Prime obsession, Joseph Henry Press, Washington, DC, 2003, ISBN 978-0-309-08549-6, MR 1968857
* Eisenbud, David, Commutative algebra, Graduate Texts in Mathematics **150**, Berlin, New York: Springer-Verlag, 1995, ISBN 978-0-387-94268-1, MR 1322960
* Fraleigh, John B., A First Course In Abstract Algebra 2nd, Reading: Addison-Wesley, 1976, ISBN 0-201-01984-1
* Furstenberg, Harry, On the infinitude of primes, The American Mathematical Monthly (Mathematical Association of America), 1955, **62** (5): 353, JSTOR 2307043, doi:10.2307/2307043
* Green, Ben; Tao, Terence, The primes contain arbitrarily long arithmetic progressions, Annals of Mathematics, 2008, **167** (2): 481–547, arXiv:math.NT/0404188 , doi:10.4007/annals.2008.167.481
* Gowers, Timothy, Mathematics: A Very Short Introduction, Oxford University Press, 2002, ISBN 978-0-19-285361-5
* Guy, Richard K., Unsolved Problems in Number Theory, Berlin, New York: Springer-Verlag, 1981, ISBN 978-0-387-90593-8
* Havil, Julian, Gamma: Exploring Euler's Constant, Princeton University Press, 2003, ISBN 978-0-691-09983-5
* Hardy, Godfrey Harold, A Course of Pure Mathematics, Cambridge University Press, 1908, ISBN 978-0-521-09227-2
* Hardy, Godfrey Harold, A Mathematician's Apology, Cambridge University Press, 1940, ISBN 978-0-521-42706-7
* Herstein, I. N., Topics In Algebra, Waltham: Blaisdell Publishing Company, 1964, ISBN 978-1114541016
* Hill, Peter Jensen (編), The Messiaen companion, Portland, Or: Amadeus Press, 1995, ISBN 978-0-931340-95-6
* Hua, L.K., Additive Theory of Prime Numbers, Translations of Mathematical Monographs **13**, Providence, RI: American Mathematical Society: 176–177, 2009 [1965], ISBN 978-0821849422, MR 0194404, OCLC 824812353
* Lehmer, D. H., Factor table for the first ten millions containing the smallest factor of every number not divisible by 2, 3, 5, or 7 between the limits 0 and 10017000, Washington, D.C.: Carnegie Institution of Washington, 1909
* McCoy, Neal H., Introduction To Modern Algebra, Revised Edition, Boston: Allyn and Bacon, 1968, LCCN 68-15225
* Narkiewicz, Wladyslaw, The development of prime number theory: from Euclid to Hardy and Littlewood, Springer Monographs in Mathematics, Berlin, New York: Springer-Verlag, 2000, ISBN 978-3-540-66289-1
* Ribenboim, Paulo, The little book of bigger primes, Berlin, New York: Springer-Verlag, 2004, ISBN 978-0-387-20169-6
* Riesel, Hans, Prime numbers and computer methods for factorization, Basel, Switzerland: Birkhäuser, 1994, ISBN 978-0-8176-3743-9
* Sabbagh, Karl, The Riemann hypothesis, Farrar, Straus and Giroux, New York, 2003, ISBN 978-0-374-25007-2, MR 1979664
* du Sautoy, Marcus, The music of the primes, HarperCollins Publishers, 2003 [2015-08-23], ISBN 978-0-06-621070-4, MR 2060134, （原始內容存檔於 2015-09-07）

## 外部連結

* Hazewinkel, Michiel (編), Prime number, 数学百科全书，Springer, 2001, ISBN 978-1-55608-010-4
* Caldwell, Chris, The Prime Pages at primes.utm.edu（頁面存檔備份，存於網際網路檔案館）.
* * Prime Numbers，In Our Time (BBC Radio 4) 的《In Our Time》節目。
* An Introduction to Analytic Number Theory, by Ilan Vardi and Cyril Banderier（頁面存檔備份，存於網際網路檔案館）
* Plus teacher and student package: prime numbers（頁面存檔備份，存於網際網路檔案館） from Plus, the free online mathematics magazine produced by the Millennium Mathematics Project at the University of Cambridge.
* 出現質數實驗 （頁面存檔備份，存於網際網路檔案館）
* 出現可以被整除的機率

### 質數產生器與計算器

* Prime Number Checker （頁面存檔備份，存於網際網路檔案館） identifies the smallest prime factor of a number.
* Fast Online primality test with factorization（頁面存檔備份，存於網際網路檔案館） makes use of the Elliptic Curve Method (up to thousand-digits numbers, requires Java).
* Huge database of prime numbers（頁面存檔備份，存於網際網路檔案館）
* Prime Numbers up to 1 trillion （頁面存檔備份，存於網際網路檔案館）
* 質數發生器和校驗器 （頁面存檔備份，存於網際網路檔案館）