质数

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

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

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

定義和例子

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

數字12不是質數，因為將12以每4個分成1組，恰可分成3組（也有其他分法）。11則無法分成數量都大於1且都相同的各組，而都會有剩餘。因此，11為質數。

在數字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的整數均可寫成一個以上的質數之乘積，且除了質因數的排序不同外是唯一的。質數可被認為是自然數的「基本建材」，例如：

23244	= 2 · 2 · 3 · 13 · 149
	= 22 · 3 · 13 · 149. （22表示2的平方或2次方。）

如同此例一般，相同的因數可能出現多次。一個數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所沒有的性質，如歐拉函數的對應值，以及除數函數的總和。

歷史

埃拉托斯特尼篩法是個找出在一特定整數以下的所有質數之簡單演算法，由古希臘數學家埃拉托斯特尼於公元前3世紀發明。

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

希臘之後，到17世紀之前，質數的研究少有進展。1640年，皮埃爾·德·費馬敘述了費馬小定理（之後才被萊布尼茨與歐拉證明）。費馬亦推測，所有具$2^{2^{n}}+1$形式的數均為質數（稱之為費馬數），並驗證至$n=4$（即2¹⁶ + 1）不過，後來由歐拉發現，下一個費馬數2³² + 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億，對許多實際應用而言都太過龐大。

篩法

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

質數測試與質數證明

主条目：素性測試

現代測試一般的數字$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無關，但會與ε有關）乘於log^5+ε(n)。

測試	發明於	類型	運算時間	註記
AKS質數測試	2002	確定性	$O(\log ^{6+\varepsilon }(n))$
橢圓曲線質數證明	1977	確定性	$O(\log ^{5+\varepsilon }(n))$「實務分析」
貝利-PSW質數測試	1980	隨機	$O(\log ^{3}n)$	無已知反例
米勒-拉賓質數判定法	1980	隨機	$O(k\cdot \log ^{2+\varepsilon }(n))$	錯誤機率$4^{-k}$
Solovay-Strassen質數	1977	隨機	$O(k\cdot \log ^{3}n)$	錯誤機率$2^{-k}$
費馬質數判定法		隨機	$O(k\cdot \log ^{2+\varepsilon }(n))$	遇到卡邁克爾數時會失敗

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

更多信息：質數列表

建構正五邊形。5是個費馬質數。

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

n! ± 1 = 1 · 2 · 3 · ... · n ± 1

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

費馬質數具下列形式

F_k = 2^2k + 1,

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

n = 2ⁱ · m

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

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

類型	質數	數位	日期	發現者
梅森質數	282589933 − 1	23,249,425	2018年12月21日	網際網路梅森質數大搜索
非梅森質數（普羅斯數）	19,249×213,018,586 + 1	3,918,990	2007年3月26日	十七或者破產
階乘質數	150209! + 1	712,355	2011年10月	PrimeGrid
質數階乘質數	1098133# - 1	476,311	2012年3月	PrimeGrid
孿生質數s	3756801695685×2666669 ± 1	200,700	2011年12月	PrimeGrid

整數分解

主条目：整數分解

給定一合數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 < 2n − 2，其中n為大於3的任一自然數。第一個公式可由威爾遜定理導出，每個不同的n會對應到不同的質數，除了數字2會有多個n對應到外。不過，這兩個公式都需要先計算出A或μ的值來。

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

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

主条目：質數定理和質數計算函數

圖中的曲線分別表示π(n)（藍）、n / ln (n)（綠）與Li(n)（紅）。

質數計算函數π(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個質數p_n（如p₁ = 2、p₂ = 3等）的大小之估算：當數字大到某一程度時，p_n的值會變得約略為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 + 9n = 3(1 + 3n)，所以此一數列裡的其他數字均為合數。（一般來所有大於q的質數都具有q#·n + m的形式，其中0 < m < q#，且m沒有不大於q的質因數。）因此，數列

a, a + q, a + 2q, a + 3q,…

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

質數（以紅底標計）在模9的等差數列中。

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

二次多項式的質數值

烏嵐螺旋。紅點表示質數。具4n² − 2n + 41形式的質數則以藍點標記。

歐拉指出函數

$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)的圖。在s=1時，該函數會有極點，亦即會趨近於無限大。

黎曼ζ函數ζ(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/π²，是兩個隨機選定的數字會互質的機率。

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

其他猜想

更多信息：分類:素數猜想

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

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

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

應用

長期以來，數論，尤其是對質數的研究，一般都會被認為是典型的純數學，除了求知的趣味之外，沒有其他應用。特別是，一些數論學家，如英國數學家戈弗雷·哈羅德·哈代即對其工作絕對不會有任何在軍事上的重大性感到自豪。然而，此一觀點在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/pZ（亦標記為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之外的其他質數，¹/_p總是個循環小數，其週期為p − 1或p − 1的因數。分數¹/_p依q（10以外的整數）為基底表示亦有類似的效果，只要p不是q的質因數的話。威爾遜定理表示，整數p > 1為質數，若且唯若階乘 (p − 1)! + 1可被p整除。此外，整數n > 4為合數，若且唯若 (n − 1)!可被n整除。

其他數學裡出現的質數

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

公開金鑰加密

主条目：公開金鑰加密

幾個公開金鑰加密演算法，如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₀、…、a_p−1為整數，ζ則是能使ζ^p = 1的複數）

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

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

賦值

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

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

其中r與s不被p所整除。例如，v₃(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的奇妙冒險》第六部《石之海》的反派普奇神父喜歡數質數，他認為質數是孤獨的數字，並透過數質數安撫他緊張的情緒。

另見

• 阿德曼-波門倫斯-魯梅利質數測試
• Bonse不等式
• 布朗篩法
• 伯恩賽德定理
• 契博塔耶夫密度定理
• 中國餘數定理
• 卡倫數
• 非法質數
• 質數列表
• 梅森質數
• 可乘數論
• 普通數域篩選法
• 貝潘測試
• 實際數
• 質k元組
• 自由黎曼氣體
• 二次剩餘問題
• RSA數
• 光滑數
• 超質數
• 胡道爾數
• 幸运素数
• 素数判定法则
• 埃拉托斯特尼筛法
• 孪生素数
• 三胞胎素数
• PrimeGrid
• GIMPS
• 質數大富豪

參考資料

• 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 （页面存档备份，存于互联网档案馆）
• 素数发生器和校验器 （页面存档备份，存于互联网档案馆）