查看“︁质数”︁的源代码

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

古希臘數學家[[欧几里得]]於公元前300年前後證明有無限多個質數存在（[[欧几里得定理]]）。現時人們已發現多種驗證質數的方法。其中[[试除法]]比較簡單，但需時較長：設被測試的自然數為<math>n</math>，使用此方法者需逐一測試2與<math>\sqrt{n}</math>之間的質數，確保它們無一能整除<math>n</math>。對於較大或一些具特別形式（如梅森數）的自然數，人們通常使用較有效率的[[算法|演算法]]測試其是否為質數（例如2<sup>82589933</sup>-1是直至2024年4月為止已知最大的[[梅森質數]]<ref>{{Cite web|url=http://www.mersenne.org/primes/?press=M74207281|title=GIMPS Project Discovers Largest Known Prime Number: 2<sup>74,207,281</sup>-1|accessdate=|author=|date=|publisher=[[互联网梅森素数大搜索]]计划|archive-date=2019-04-07|archive-url=https://web.archive.org/web/20190407203531/https://www.mersenne.org/primes/?press=M74207281|dead-url=no}}</ref>，也是直至2024年4月為止已知最大的質數）。雖然人們仍未發現可以完全區別質數與合數的公式，甚至研究質數分布時相當有力的[[篩法]]也會碰到[[篩法的奇偶性問題|奇偶性問題]]（也就是多種篩法都無法區別質數跟兩個質數相乘的合數的問題），但已建構了質數的分佈模式（亦即質數在[[大数 (数学)|大數]]時的統計模式）。19世紀晚期得到證明的[[質數定理]]指出：一個任意自然數n為質數的機率反比於其[[数位 (数学)|數位]]（或<math>n</math>的[[对数]]）。

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

==定義和例子==
一個[[自然數]]（如1、2、3、4、5、6等）若恰有兩個正[[因數]]（1及此數本身），則稱之為'''質數'''<ref>{{Citation | last1=Dudley| first1=Underwood | title=Elementary number theory | publisher=W. H. Freeman and Co. | edition=2nd | isbn=978-0-7167-0076-0 | year=1978}}, p. 10, section 2</ref>。大於1的自然數若不是質數，則稱之為[[合數]]。

[[File:Prime rectangles.svg|thumb|300px|數字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不是質數：{{nowrap|12 {{=}} 3 · 4}}。不存在大於2的偶數為質數，因為依據定義，任何此類數字<math>n</math>均至少有三個不同的因數，即1、2與<math>n</math>。這意指<math>n</math>不是質數。因此，「奇質數」係指任何大於2的質數。類似地，當使用一般的十進位制時，所有大於5的質數，其尾數均為1、3、7或9，因為尾數0、2、4、6、8為2的倍數，尾數為0或5的數字為5的倍數。

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

:<math>2,3,\ldots,n-1</math>

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

:<math>n=a\cdot b</math>.

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

由所有質數組成之集合通常標記為{{math|'''P'''}}或<math>\mathbb{P}</math>。

前168個質數（所有小於1000的質數）為{{數列|{{Ifexist not redirect{{!}}${{!}}[[$]]{{!}}$}}, |1|168|質數(x)|preprocess=1}}...{{OEIS|id=A000040}}。

==算術基本定理==
{{Main|算術基本定理}}
質數對於[[數論]]與一般數學的重要性來自於「算術基本定理」。該定理指出，每個大於1的整數均可寫成一個以上的質數之乘積，且除了質[[因數]]的排序不同外是唯一的<ref>{{Harvard citations|author=Dudley|year=1978|nb=yes|loc=Section 2, Theorem 2}}</ref>。質數可被認為是自然數的「基本建材」，例如：

:{|
|-
|23244 ||= 2 · 2 · 3 · 13 · 149
|-
|||= 2<sup>2</sup> · 3 · 13 · 149. （2<sup>2</sup>表示2的[[平方]]或2次方。）
|}

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

:<math>n=p_1\cdot p_2 \cdot \ldots \cdot p_t</math>

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

若<math>p</math>為質數，且<math>p</math>可整除整數的乘積<math>ab</math>，則<math>p</math>可整除<math>a</math>或可整除<math>b</math>。此一命題被稱為歐幾里得引理<ref>{{Harvard citations|author=Dudley|year=1978|nb=yes|loc=Section 2, Lemma 5}}</ref>，被用來證明質數分解的唯一性。

===1是否為質數===
最早期的希臘人甚至不將1視為是一個數字<ref>如見David E. Joyce對[[幾何原本]]的註記，[http://aleph0.clarku.edu/~djoyce/java/elements/bookVII/defVII1.html Book VII, definitions 1 and 2] {{Wayback|url=http://aleph0.clarku.edu/~djoyce/java/elements/bookVII/defVII1.html |date=20110805002110 }}</ref>，因此不會認為1是質數。到了中世紀與[[文藝復興時期]]，許多數學家將1納入作為第一個質數<ref name="autogenerated1">{{Cite web |url=https://primes.utm.edu/notes/faq/one.html |title=存档副本 |accessdate=2015-08-23 |archive-date=2015-04-19 |archive-url=https://web.archive.org/web/20150419070108/http://primes.utm.edu/notes/faq/one.html |dead-url=no }}</ref>。到18世紀中期，[[克里斯蒂安·哥德巴赫]]在他與[[李昂哈德·歐拉]]著名的通信裡將1列為第一個質數，但歐拉不同意<ref>Weisstein, Eric W., "Goldbach Conjecture," MathWorld</ref>。然而，到了19世紀，仍有許多數學家認為數字1是個質數。例如，德里克·諾曼·雷默（Derrick Norman Lehmer）在他那最大達10,006,721的質數列表<ref>{{Harvard citations | last1=Riesel | year=1994|loc=p. 36|nb=yes}}</ref>中，將1列為第1個質數<ref>{{Harvard citations | last1=Conway | last2=Guy | year=1996|loc=pp. 129–130|nb=yes }}</ref>。[[昂利·勒貝格]]據說是最後一個稱1為質數的職業數學家<ref>
{{Citation |last1=Derbyshire |first1=John  |title=Prime  Obsession: Bernhard Riemann and the Greatest  Unsolved Problem in  Mathematics  |accessdate=2008-03-11 |year=2003  |publisher=Joseph Henry Press |location=Washington,  D.C.  |isbn=978-0-309-08549-6 |oclc=249210614  |page=33  |chapter=The  Prime Number Theorem }}</ref>。到了20世紀初，數學家開始認為1不是個質數，但反而作為「單位」此一特殊類別<ref name="autogenerated1"/>。

許多數學成果在稱1為質數時，仍將有效，但歐幾里何的算術基本定理（如上所述）則無法不重新敘述而仍然成立。例如，數字15可分解成{{nowrap|3 · 5}}及{{nowrap| 1 · 3 · 5}}；若1被允許為一個質數，則這兩個表示法將會被認為是將15分解至質數的不同方法，使得此一定理的陳述必須被修正。同樣地，若將1視為質數，[[埃拉托斯特尼篩法]]將無法正常運作：若將1視為質數，此一篩法將會排除掉所有1的倍數（即所有其他的數），只留下數字1。此外，質數有幾個1所沒有的性質，如歐拉函數的對應值，以及[[除數函數]]的總和<ref>"[http://primefan.tripod.com/Prime1ProCon.html "Arguments for and against the primality of 1] {{Wayback|url=http://primefan.tripod.com/Prime1ProCon.html |date=20210224130159 }}".</ref><ref>{{Cite web |url=http://primes.utm.edu/notes/faq/one.html |title="Why is the number one not prime?" |access-date=2015-08-23 |archive-date=2008-05-09 |archive-url=https://web.archive.org/web/20080509162105/http://primes.utm.edu/notes/faq/one.html |dead-url=no }}</ref>。

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

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

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

19世紀初，[[阿德里安-馬里·勒壤得|勒壤得]]與[[高斯]]獨立推測，當<math>x</math>趨向無限大時，小於<math>x</math>的質數數量會趨近於<math>\frac{x}{\ln x}</math>，其中<math>\ln x</math>為<math>x</math>的[[自然對數]]。黎曼於{{le|關于小於給定值的質數|On the Number of Primes Less Than a Given Magnitude|1859年有關ζ函數的論文}}中勾勒出一個程式，導出了質數定理的證明。其大綱由[[雅克·阿達馬]]與[[夏尔-让·德拉瓦莱·普桑]]所完成，他們於1896年獨立證明出[[質數定理]]。

證明一個大數是否為質數通常無法由試除法來達成。許多數學家已研究過大數的[[質數判定法則|質數測試]]，通常侷限於特定的數字形式。其中包括費馬數的{{le|貝潘測試|Pépin's test}}（1877年）、[[普羅絲定理]]（約1878年）、[[卢卡斯-莱默检验法|盧卡斯-萊默質數判定法]]（1856年起）<ref>[http://primes.utm.edu/notes/by_year.html The Largest Known Prime by Year: A Brief History] {{Wayback|url=http://primes.utm.edu/notes/by_year.html |date=20130808055216 }} [http://primes.utm.edu/curios/page.php?number_id=135 Prime Curios!: 17014…05727 (39-digits)] {{Wayback|url=http://primes.utm.edu/curios/page.php?number_id=135 |date=20210226031048 }}</ref>及廣義{{le|盧卡斯質數測試|Lucas primality test}}。較近期的演算法，如{{le|APRT-CL|Adleman–Pomerance–Rumely primality test}}、{{le|橢圓曲線質數證明|Elliptic curve primality|ECPP}}及[[AKS質數測試|AKS]]等，均可作用於任意數字上，但仍慢上許多。

長期以來，質數被認為在[[純數學]]以外的地方只有極少數的應用<ref>例如，Beiler寫道，數論學家[[恩斯特·庫默爾]]熱愛他的[[理想數]]，該數與質數密切相關，「因為這些數沒有被任何實際應用所玷污」。Katz則寫道，[[愛德蒙·蘭道]]（他最為人所知的是對質數分佈的相關研究）「厭惡數學的實際應用」，且因為這個理由，規避[[幾何]]等已知有所用途之學科。{{citation|title=Recreations in the Theory of Numbers: The Queen of Mathematics Entertains|first=Albert H.|last=Beiler|publisher=Dover|year=1966|isbn=9780486210964|page=2|url=https://books.google.com/books?id=NbbbL9gMJ88C&pg=PA2|accessdate=2015-08-23|archive-date=2021-04-17|archive-url=https://web.archive.org/web/20210417055438/https://books.google.com/books?id=NbbbL9gMJ88C&pg=PA2|dead-url=no}}. {{citation|last=Katz|first=Shaul|doi=10.1017/S0269889704000092|issue=1-2|journal=Science in Context|mr=2089305|pages=199–234|title=Berlin roots—Zionist incarnation: the ethos of pure mathematics and the beginnings of the Einstein Institute of Mathematics at the Hebrew University of Jerusalem|volume=17|year=2004|issn=0269-8897}}</ref>。到了1970年代，發明[[公共密鑰加密]]這個概念之後，情況改變了，質數變成了[[RSA加密演算法]]等一階演算法之基礎。

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

==素数的数目==
{{Main|歐幾里得定理}}

存在[[無窮|無限多]]個質數。另一種說法為，質數序列
:2, 3, 5, 7, 11, 13, ...
永遠不會結束。此一陳述被稱為「歐幾里得定理」，以古希臘數學家[[歐幾里得]]為名，因為他提出了該陳述的第一個證明。已知存在其他更多的證明，包括[[歐拉]]的[[數學分析|分析]]證明、[[哥德巴赫]]依據[[費馬數]]的證明<ref>[http://www.math.dartmouth.edu/~euler/correspondence/letters/OO0722.pdf Letter] {{Wayback|url=http://www.math.dartmouth.edu/~euler/correspondence/letters/OO0722.pdf |date=20150611112920 }} in [[Latin]] from Goldbach to Euler, July 1730.</ref>、[[希勒尔·弗斯滕伯格|弗斯滕伯格]]使用一般[[拓撲學]]的證明<ref>{{Harvard citations | last1=Furstenberg | year=1955 | nb=yes}}</ref>，以及[[恩斯特·庫默爾|庫默爾]]優雅的證明<ref>{{Harvard citations | last1=Ribenboim |year=2004|nb=yes|loc=p. 4}}</ref>。

===歐幾里得的證明===
歐幾里得的證明<ref>James Williamson (translator and commentator), ''The Elements of Euclid, With Dissertations'', [[Clarendon Press]], Oxford, 1782, page 63, [http://aleph0.clarku.edu/~djoyce/java/elements/bookIX/propIX20.html English translation of Euclid's proof] {{Wayback|url=http://aleph0.clarku.edu/~djoyce/java/elements/bookIX/propIX20.html|date=20110123034101}}</ref>取任一個由質數所組成的有限集合<math>S</math>。該證明的關鍵想法為考慮<math>S</math>內所有質數相乘後加一的一個數字：

: <math> N = 1 + \prod_{p\in S} p</math>。

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

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

這個證明通常會被錯誤地描述為，歐幾里得一開始假定一個包含所有質數的集合，並導致[[反證法|矛盾]]；或者是，該集合恰好包含n個最小的質數，而不任意個由質數所組成之集合<ref>{{cite journal |first=Michael |last=Hardy |first2=Catherine |last2=Woodgold |title=Prime Simplicity |url=https://archive.org/details/sim_mathematical-intelligencer_fall-2009_31_4/page/44 |journal=[[Mathematical Intelligencer]] |volume=31 |issue=4 |year=2009 |pages=44–52 |doi= 10.1007/s00283-009-9064-8}}</ref>。今日，<math>n</math>個最小質數相乘後加一的一個數字，被稱為第<math>n</math>個[[歐幾里得數]]。

===歐拉的解析證明===
歐拉的證明使用到質數[[倒數]]的總和

:<math>S(p) = \frac 1 2 + \frac 1 3 + \frac 1 5 + \frac 1 7 + \cdots + \frac 1 p</math>。

當<math>p</math>夠大時，該和會大於任意[[實數]]<ref>{{Citation | last1=Apostol | first1=Tom M. | author1-link=Tom M. Apostol | title=Introduction to Analytic Number Theory | publisher=[[Springer-Verlag]] | location=Berlin, New York | isbn=978-0-387-90163-3 | year=1976}}, Section 1.6, Theorem 1.13</ref>。這可證明，存在無限多個質數，否則該和將只會增長至達到最大質數<math>p</math>為止。<math>S(p)</math>的增加率可使用[[梅滕斯定理|梅滕斯第二定理]]來量化<ref>{{Harvard citations|year=1976|last1=Apostol|nb=yes|loc=Section 4.8, Theorem 4.12}}</ref>。比較總和

:<math>\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}</math>

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

:<math> \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)}, </math>
是有限的。

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

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

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

===篩法===
一個能給出某個數值以下的所有質數之演算法，稱之為質數[[篩論|篩法]]，可用於只使用質數的試除法內。最古老的一個例子為[[埃拉托斯特尼篩法]]（見上文），至今仍最常被使用。[[阿特金篩法]]為另外一例。在電腦出現之前，篩法曾被用來給出10<sup>7</sup>以下的質數列表<ref>{{Harvard citations|last=Lehmer|year=1909}}.</ref>。

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

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

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

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

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

===專用目的演算法與最大已知質數===
{{Further|質數列表}}
[[File:Pentagon construct.gif|建構正五邊形。5是個費馬質數。|right|thumb]]
除了前述可應用於任何[[自然數]]n之上的測試外，一些更有效率的質數測試適用於特定數字之上。例如，[[盧卡斯質數測試]]需要知道{{nowrap|''n'' − 1}}的質因數，而[[盧卡斯-萊默質數判定法|盧卡斯-萊默質數測試]]則需要以{{nowrap|''n'' + 1}}的質因數作為輸入。例如，這些測試可應用在檢查
:[[階乘|''n''!]] ± 1 = 1 · 2 · 3 · ... · ''n'' ± 1
是否為一質數。此類形式的質數稱之為[[階乘質數]]。其他具p+1或p-1之類形式的質數還包括[[索菲·熱爾曼質數]]（具2p+1形式的質數，其中p為質數）、[[質數階乘質數]]、[[費馬質數]]與[[梅森質數]]（具{{nowrap|2<sup>''p''</sup> − 1}}形式的質數，其中p為質數）。盧卡斯-雷默質數測試對這類形式的數特別地快。這也是為何自電腦出現以來，[[最大已知質數]]總會是梅森質數的原因。

費馬質數具下列形式
:{{nowrap|''F''<sub>''k''</sub> {{=}} 2<sup>2<sup>''k''</sup></sup> + 1}},
其中，k為任意自然數。費馬質數以[[皮埃爾·德·費馬]]為名，他猜想此類數字''F<sub>k</sub>''均為質數。費馬認為''F<sub>k</sub>''均為質數的理由為此串列的前5個數字（3、5、17、257及65537）為質數。不過，''F''<sub>5</sub>卻為合數，且直至2015年發現的其他費馬數字也全都是合數。一個[[正多邊形|正n邊形]]可用[[可作圖多邊形|尺規作圖]]，若且唯若
:''n'' = 2<sup>''i''</sup> · ''m''
其中，m為任意個不同費馬質數之乘積，及i為任一自然數，包括0。

下列表格給出各種形式的最大已知質數。有些質數使用[[分散式計算]]找到。2009年，[[網際網路梅森質數大搜索]]因為第一個發現具至少1,000萬個數位的質數，而獲得10萬美元的獎金<ref>{{cite web | url= http://www.eff.org/press/archives/2009/10/14-0 | title= Record 12-Million-Digit Prime Number Nets $100,000 Prize | date= 2009-10-14 | publisher= Electronic Frontier Foundation | accessdate= 2010-01-04 | archive-date= 2021-01-20 | archive-url= https://web.archive.org/web/20210120014937/https://www.eff.org/press/archives/2009/10/14-0 | dead-url= no }}</ref>。[[電子前哨基金會]]亦為具至少1億個數位及10億個數位的質數分別提供15萬美元及25萬美元的獎金<ref>{{cite web | url= http://www.eff.org/awards/coop | title= EFF Cooperative Computing Awards | date=  | publisher= Electronic Frontier Foundation | accessdate= 2010-01-04 | archive-date= 2010-04-02 | archive-url= https://web.archive.org/web/20100402083042/http://www.eff.org/awards/coop | dead-url= no }}</ref>。

{| class="wikitable"
|-
! 類型
! 質數
! 數位
! 日期
! 發現者
|-
| [[梅森質數]]
| 2<sup>82589933</sup> − 1
| style="text-align:right;"| 23,249,425
| 2018年12月21日
| [[網際網路梅森質數大搜索]]
|-
| 非梅森質數（[[普羅斯數]]）
| 19,249×2<sup>13,018,586</sup> + 1
| style="text-align:right;"| 3,918,990
| 2007年3月26日
| [[十七或者破產]]
|-
| [[階乘質數]]
| 150209! + 1
| style="text-align:right;"| 712,355
| 2011年10月
| [[PrimeGrid]]<ref>{{cite web |author=Chris K. Caldwell |url=http://primes.utm.edu/top20/page.php?id=30 |title=The Top Twenty: Factorial |publisher=Primes.utm.edu |date= |accessdate=2013-02-05 |archive-date=2013-04-10 |archive-url=https://web.archive.org/web/20130410122813/http://primes.utm.edu/top20/page.php?id=30 |dead-url=no }}</ref>
|-
| [[質數階乘質數]]
| 1098133# - 1
| style="text-align:right;"| 476,311
| 2012年3月
| [[PrimeGrid]]<ref>{{cite web |author=Chris K. Caldwell |url=http://primes.utm.edu/top20/page.php?id=5 |title=The Top Twenty: Primorial |publisher=Primes.utm.edu |date= |accessdate=2013-02-05 |archive-date=2021-05-06 |archive-url=https://web.archive.org/web/20210506094747/https://primes.utm.edu/top20/page.php?id=5 |dead-url=no }}</ref>
|-
| [[孿生質數]]s
| 3756801695685×2<sup>666669</sup> ± 1
| style="text-align:right;"| 200,700
| 2011年12月
| [[PrimeGrid]]<ref>{{cite web |author=Chris K. Caldwell |url=http://primes.utm.edu/top20/page.php?id=1 |title=The Top Twenty: Twin Primes |publisher=Primes.utm.edu |date= |accessdate=2013-02-05 |archive-date=2013-01-27 |archive-url=https://web.archive.org/web/20130127020012/http://primes.utm.edu/top20/page.php?id=1 |dead-url=no }}</ref>
|}

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

==質數分佈==
1975年，數論學家[[唐·察吉爾]]評論質數
{{quote|像生長於自然數間的雜草，似乎不服從機率之外的法則，（但又）表現出驚人的規律性，並有規範其行為之法則，且以軍事化的精準度遵守著這些法則<ref>{{Harvard citations | last1=Havil |year=2003|loc=p. 171|nb=yes}}</ref>。}}

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

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

[[狄利克雷定理]]表示，取兩個[[互質]]的整數a與b，其線性多項式
:<math>p(n) = a + bn\,</math>
會有無限多個質數值。該定理亦表示，這些質數值的倒數和會發散，且具有相同b的不同多項式會有差不多相同的質數比例。

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

===質數的公式===
{{main|質數公式}}
對於質數，還沒有一個已知的有效公式。例如，[[米爾斯常數|米爾斯定理]]與[[愛德華·梅特蘭·賴特|賴特]]所提的一個定理表示，存在實常數A>1與μ，使得
:<math>\left \lfloor A^{3^{n}}\right \rfloor \text{ and } \left \lfloor 2^{\dots^{2^{2^\mu}}} \right \rfloor</math>
對任何自然數n而言，均為質數。其中，<math>\lfloor - \rfloor</math>為[[高斯符號]]，表示不大於符號內數字的最大整數。第二個公式可使用[[伯特蘭-切比雪夫定理]]得證（由[[切比雪夫]]第一個證得）。該定理表示，總是存在至少一個質數p，使得  ''n''&nbsp;<&nbsp;''p''&nbsp;<&nbsp;2''n''&nbsp;−&nbsp;2，其中n為大於3的任一自然數。第一個公式可由[[威爾遜定理]]導出，每個不同的n會對應到不同的質數，除了數字2會有多個n對應到外。不過，這兩個公式都需要先計算出A或μ的值來<ref name="Tabachnikov1999">{{cite book|author=Serge Tabachnikov|title=Kvant Selecta Algebra and Analysis|url=http://books.google.com/books?id=oLKlk5o6WroC&pg=PA13|date=1999-01-01|publisher=American Mathematical Society|isbn=978-0-8218-1915-9|pages=13–|access-date=2015-08-25|archive-date=2021-04-17|archive-url=https://web.archive.org/web/20210417044816/https://books.google.com/books?id=oLKlk5o6WroC&pg=PA13|dead-url=no}}</ref>。

不存在一個只會產生質數值的非常數[[多項式]]，即使該多項式有許多個變數。不過，存在具9個變數的[[丟番圖方程]]，其參數具備以下性質：該參數為質數，若且唯若其方程組有自然數解。這可被用來獲得其所有「正值」均為質數的一個公式<ref>{{citation | last = Matiyasevich | first = Yuri V. | authorlink = Yuri Matiyasevich | year = 1999 | chapter = Formulas for Prime Numbers | url = https://books.google.com/books?id=oLKlk5o6WroC&pg=PA13 | editor1-first = Serge | editor1-last = Tabachnikov | editorlink1 = Sergei Tabachnikov | title = Kvant Selecta: Algebra and Analysis, | volume = II | publisher = [[American Mathematical Society]] | isbn = 978-0-8218-1915-9 | pages = 13–24 | accessdate = 2015-08-23 | archive-date = 2021-04-17 | archive-url = https://web.archive.org/web/20210417044816/https://books.google.com/books?id=oLKlk5o6WroC&pg=PA13 | dead-url = no }}</ref>。

===一特定數以下的質數之數量===
{{Main|質數定理|質數計算函數}}
[[File:PrimeNumberTheorem.svg|圖中的曲線分別表示π(''n'')（藍）、''n'' / ln (''n'')（綠）與Li(''n'')（紅）。|thumb|300px]]
[[質數計算函數]]π(n)被定義為不大於n的質數之數量。例如，π(11) = 5，因為有5個質數小於或等於11。已知有[[演算法]]可比去計算每個不大於n的質數更快的速率去計算π(n)的值。[[質數定理]]表示，π(n)的可由下列公式近似給出：
:<math>\pi(n) \approx \frac n {\ln n},</math>
亦即，π(n)與等式右邊的值在n趨近於無限大時，會趨近於1。這表示，小於n的數字為質數的可能性（大約）與n的數位呈正比。對π(n)更精確的描述可由[[對數積分]]給出：
:<math>\operatorname{Li}(n) = \int_2^n \frac{dt}{\ln t}</math>。

質數定理亦薀涵著對第n個質數''p<sub>n</sub>''（如''p''<sub>1</sub> = 2、''p''<sub>2</sub> = 3等）的大小之估算：當數字大到某一程度時，''p<sub>n</sub>''的值會變得約略為{{nowrap|''n'' log(''n'')}}<ref>{{Harvard citations | last1=Apostol | first1=Tom M. | year=1976}}, Section 4.6, Theorem 4.7</ref>。特別的是，[[質數間隙]]，即兩個連續質數''p''<sub>''n''</sub>與''p''<sub>''n''+1</sub>間的差會變得任意地大。後者可由數列{{nowrap| ''n''! + 2, ''n''! + 3,…, ''n''! + ''n''}}（其中n為任一自然數）看出。

===等差數列===
[[等差数列]]是指由被一固定數（[[模算數|模]]）q除後會得到同一餘數的自然數所組成之集合。例如：
:3, 12, 21, 30, 39, ...,
是一個等差數列，模q = 9。除了3以外，其中沒有一個數會是質數，因為{{nowrap|3 + 9''n'' {{=}} 3(1 + 3''n'')}}，所以此一數列裡的其他數字均為合數。（一般來所有大於q的質數都具有[[質數階乘|''q''#]]·''n''&nbsp;+&nbsp;''m''的形式，其中0&nbsp;<&nbsp;''m''&nbsp;<&nbsp;''q''#，且m沒有不大於q的質因數。）因此，數列
:''a'', {{nowrap|''a'' + ''q'',}} {{nowrap|''a'' + 2''q'',}} {{nowrap|''a'' + 3''q'',…}}
只在a與q [[互質]]（其[[最大公因數]]為1）之時，可以有無限多個質數。若滿足此一必要條件，[[狄利克雷定理]]表示，該數列含有無限多個質數。下圖描述{{nowrap|''q'' {{=}} 9}}時的情形：數字每遇到9的倍數就會再再由下往上纏一次。質數以紅底標記。行（數列）開始於a = 3, 6, 9者至多只包含一個質數。其他行（a = 1, 2, 4, 5, 7, 8）則均包含無限多個質數。更甚之，質數以長期來看，會均勻分佈於各行之中，亦即每個質數模9會與6個數其中一數同餘的機率均為1/6。
[[File:Prime numbers in arithmetic progression mod&nbsp;9 zoom in.png|center|質數（以紅底標計）在模9的等差數列中。]]
[[格林-陶定理]]證明，存在由任意多個質數組成的等差數列<ref>{{Harvard citations|first1=Ben|last1=Green|author1-link=Ben J. Green|first2=Terence|last2=Tao|author2-link=陶哲軒|arxiv=math.NT/0404188|title=The primes contain arbitrarily long arithmetic progressions|journal=[[Annals of Mathematics]]|volume=167|year=2008|pages=481–547}}</ref>。一個奇質數p可表示成兩個平方數之和{{nowrap|''p'' {{=}} ''x''<sup>2</sup> + ''y''<sup>2</sup>}}，若且唯若p同餘於1模4（[[费马平方和定理]]）。

===二次多項式的質數值===
[[File:Ulam 2.png|right|[[烏嵐螺旋]]。紅點表示質數。具4''n''<sup>2</sup>&nbsp;−&nbsp;2''n''&nbsp;+&nbsp;41形式的質數則以藍點標記。|200px|thumb]]
歐拉指出函數
:<math>n^2 + n + 41\,</math>
於　{{nowrap|0 ≤ ''n'' < 40}}時會給出質數{{sfn|Hua|2009|p=176-177}}<ref>{{cite wolframalpha|title=evaluate x^2−x+41 for x from 0..40|access-date=2021-05-18 |archive-date=2020-03-21 |archive-url=https://web.archive.org/web/20200321032430/https://www.wolframalpha.com/input/?i=evaluate+x%5E2%E2%88%92x%2B41+for+x+from+0..40 |dead-url=no }}</ref>，此一事實導致了艱深的[[代數數論]]，或更具體地說為[[黑格納數]]。當n更大時，該函數會給出合數值。[[哈代- 李特伍德猜想]]（Hardy-Littlewood conjecture）能給出一個有關具整數[[系数|係數]]a、b與c的[[二次函数|二次多項式]]
:<math>f(n) = a x^2 + bx + c\, </math>
的值為質數之機率的一個漸近預測，並能以對數積分Li(n)及係數a、b、c來表示。不過，該程式已被證實難以取得：仍未知是否存在一個二次多項式（{{nowrap|''a'' ≠ 0}}）能給出無限多個質數。[[烏嵐螺旋]]將所有自然數以螺旋的方法描繪。令人驚訝的是，質數會群聚在某些對角線上，表示有些二次多項式會比其他二次多項式給出更多個質數值來。

==未解決的問題==

===ζ函數與黎曼猜想===
{{Main|黎曼猜想}}
[[File:Riemann zeta function absolute value.png|thumb|ζ函數ζ(''s'')的圖。在''s''=1時，該函數會有[[極點 (複分析)|極點]]，亦即會趨近於[[無窮|無限大]]。]]

[[黎曼ζ函數]]ζ(s)被定義為一[[無窮級數]]
:<math>\zeta(s)=\sum_{n=1}^\infin \frac{1}{n^s},</math>
其中，s為實數部分大於1的一個[[复数 (数学)|複數]]。由算術基本定理可證得，該級數會等於下面的[[無窮乘積]]
:<math>\prod_{p \text{ prime}} \frac{1}{1-p^{-s}}</math>。
ζ函數與質數密切相關。例如，存在無限多個質數這個事實也可以使用ζ函數看出：若只有有限多個質數，則ζ(1)將會是個有限值。不過，[[調和級數]]{{nowrap|1 + 1/2 + 1/3 + 1/4 + ...}}會[[發散]]，所以必須有無限多個質數。另一個能看見ζ函數的豐富性，並一瞥現代[[代數數論]]的例子為下面的恆等式（[[巴塞爾問題]]，由歐拉給出）：
:<math>\zeta(2) = \prod_{p} \frac{1}{1-p^{-2}}= \frac{\pi^2}{6}</math>。
ζ(2)的倒數6/π<sup>2</sup>，是兩個隨機選定的數字會[[互質]]的[[機率]]<ref>{{cite web|last=Caldwell|first=Chris|title=What is the probability that gcd(n,m)=1?|url=http://primes.utm.edu/notes/relprime.html|work=The [[Prime Pages]]|accessdate=2013-09-06|archive-date=2021-04-21|archive-url=https://web.archive.org/web/20210421055044/https://primes.utm.edu/notes/relprime.html|dead-url=no}}</ref><ref>[[C. Stanley Ogilvy|C. S. Ogilvy]] & J. T. Anderson ''Excursions in Number Theory'', pp. 29–35, Dover Publications Inc., 1988 ISBN 978-0-486-25778-5</ref>。

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

===其他猜想===
{{Further|分類:素數猜想}}
除了黎曼猜想之外，還有許多其他的猜想存在。雖然這些猜想的陳述大多很簡單，但許多猜想經過了數十年仍提不出證明，如4個[[蘭道問題]]，從1912年提出至今仍然未解。其中一個為[[哥德巴赫猜想]]，該猜想認為每個大於2的偶數n都可表示成兩個質數之和。至於2011年2月，這個猜想對最大達{{nowrap|''n'' {{=}} 2 · 10<sup>17</sup>}}的所有數字都會成立<ref>{{cite web |author=Tomás Oliveira e Silva |url=http://www.ieeta.pt/~tos/goldbach.html |title=Goldbach conjecture verification |publisher=Ieeta.pt |date=2011-04-09 |accessdate=2011-05-21 |archive-date=2013-04-21 |archive-url=https://web.archive.org/web/20130421031308/http://www.ieeta.pt/~tos/goldbach.html |dead-url=yes }}</ref>。較弱形式的哥德巴赫猜想已被證明，如[[維諾格拉多夫定理]]，該定理表示每個足夠大的奇數都可表示成三個質數之和。[[陈氏定理]]表示，每個足夠大的偶數都可表示成一個質數與一個[[半素数|半質數]]（兩個質數的乘積）之和。此外，任一個偶數均可寫成六個質數之和<ref>{{Citation | first=O. | last=Ramaré | authorlink=Olivier Ramaré | title=On šnirel'man's constant | journal=Annali della Scuola Normale Superiore di Pisa. Classe di Scienze. Serie IV | volume=22 | year=1995 | issue=4 | pages=645–706 | url=http://www.numdam.org/item?id=ASNSP_1995_4_22_4_645_0 | accessdate=2008-08-22 | ref=harv | postscript=. | archive-date=2020-09-19 | archive-url=https://web.archive.org/web/20200919191448/http://www.numdam.org/item/?id=ASNSP_1995_4_22_4_645_0 | dead-url=no }}</ref>。數論研究這些問題的分支稱之為[[加法數論]]。反哥德巴赫猜想，所有的正偶數n都可以表示成兩個質數之差，但此猜想可由波利尼亞克猜想類推證明。

其他猜想處理是否有無限多個具某些限制的質數這類問題。據猜想，存在無限多個[[費波那契質數]]<ref>Caldwell, Chris, [http://primes.utm.edu/top20/page.php?id=48 ''The Top Twenty: Lucas Number''] {{Wayback|url=http://primes.utm.edu/top20/page.php?id=48|date=20210427055335}} at The [[Prime Pages]].</ref>與無限多個[[梅森素数|梅森質數]]，但沒有無限多個[[費馬數|費馬質數]]<ref>E.g., see {{Harvard citations | last1=Guy | year=1981|loc=problem A3, pp. 7–8|nb=yes}}</ref>。還不知道是否存在無限多個[[維費里希素數|維費里希質數]]與[[歐幾里得數|歐幾里得質數]]。

第三種類型的猜想涉及到質數的分佈情形。據猜想，存在無限多對[[孪生素数|孿生質數]]，即有無限多對相差2的質數（[[孪生素数猜想|孿生質數猜想]]）。[[波利尼亞克猜想]]是比孿生質數猜想更強的一個猜想，該猜想表示存在無限多對相差2n的連續質數<ref>{{Citation | last1=Tattersall | first1=J.J. | title=Elementary number theory in nine chapters | url=https://books.google.com/books?id=QGgLbf2oFUYC | publisher=[[Cambridge University Press]] | isbn=978-0-521-85014-8 | year=2005 | accessdate=2015-08-23 | archive-date=2020-03-21 | archive-url=https://web.archive.org/web/20200321032456/https://books.google.com/books?id=QGgLbf2oFUYC | dead-url=no }}, p. 112</ref>。據猜想，存在無限多個具''n''<sup>2</sup>&nbsp;+&nbsp;1形式的質數<ref>{{cite mathworld|urlname=LandausProblems|title=Landau's Problems}}</ref>。上述猜想都是[[申策爾猜想]]的特例。[[布羅卡猜想]]表示，在兩個大於2的連續質數之平方數之間，總是會有至少4個質數。[[勒讓德猜想]]表示，對每個正整數n，''n''<sup>2</sup>與(''n''&nbsp;+&nbsp;1)<sup>2</sup>間總會存在一個質數。[[克拉梅爾猜想]]可導出勒讓德猜想。

==應用==
長期以來，數論，尤其是對質數的研究，一般都會被認為是典型的純數學，除了求知的趣味之外，沒有其他應用。特別是，一些數論學家，如[[英國]]數學家[[戈弗雷·哈羅德·哈代]]即對其工作絕對不會有任何在軍事上的重大性感到自豪<ref>{{Harvard citations | last1=Hardy |year=1940|nb=yes}} "No one has yet discovered any warlike purpose to be served by the theory of numbers or relativity, and it seems unlikely that anyone will do so for many years."</ref>。然而，此一觀點在1970年代時遭到粉碎，當質數被公開宣布可以作為產生[[公鑰加密]]演算法的基礎之時。質數現在也被用在[[雜湊表]]與{{le|偽亂數產生器|Pseudo-random number generator}}裡。

{{Citation needed|[[旋轉機]]被設計成在每個轉片上有不同數目的銷，在每個轉片上的銷的數量都會是質數，亦或是會與其他轉片上的銷的數量[[互質]]。這有助於在重復所有的組合之前，讓所有轉片的可能組合都能出現過一次。|time=2022-07-11T04:36:09+00:00}}

[[國際標準書號]]的最後一碼為[[校驗碼]]，其演算法使用到了11是個質數的這個事實{{citation needed|date=2019年1月}}。

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

在害蟲的生物生長周期與殺蟲劑使用之間的關係上，殺蟲劑的素数次数的使用也得到了證明。實驗表明，素数次数地使用殺蟲劑是最合理的：都是使用在害蟲繁殖的高潮期，而且害蟲很難産生抗藥性{{citation needed|date=2015年8月}}。

以素数形式无规律变化的导弹和鱼雷可以使敌人不易拦截{{citation needed|date=2015年8月}}。

===模一質數與有限體之運算===
{{Main|模運算}}
「模運算」使用下列數字修改了一般的運算
:<math>\{0, 1, 2, \dots, n-1 \}, \,</math>
其中n是個固定的自然數，稱之為「模」。計算加法、減法及乘法都與一般的運算一樣，不過負數或大於''n''&nbsp;−&nbsp;1的數字出現時，會被除以n所得的[[餘數]]取代。例如，對n=7，3+5為1，而不是8，因為8除以7餘1。這通常念為「3+5同餘於1模7」，並標記為
:<math>3 + 5 \equiv 1 \pmod 7</math>。
同樣地，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，方程

:<math>3 \cdot x \equiv 2 \pmod 6,</math>

的解x會類比於2/3，無解，亦可透過計算3 · 0、...、3 · 5模6看出。不過，有關質數的不同性質如下：除法在模運算裡是可行的，[[若且唯若]]n為質數。等價地說，n為質數，若且唯若所有滿足{{nowrap|2 ≤ ''m'' ≤ ''n'' − 1}}的整數m都會與n [[互質]]，亦即其[[最大公因數|公因數]]只有1。實際上，對n=7，方程
:<math>3 \cdot x \equiv 2 \ \ (\operatorname{mod}\ 7),</math>
會有唯一的解{{nowrap|''x'' {{=}} 3}}。因此，對任何質數p，'''Z'''/''p'''''Z'''（亦標記為'''F'''<sub>''p''</sub>）也會是個[[體 (數學)|體]]，或更具體地說，是個[[有限體]]，因為該集合包含有限多（即p）個元素。

許多定理可以透過從此一抽象的方式檢查'''F'''<sub>''p''</sub>而導出。例如，[[費馬小定理]]表示
:<math>a^{p-1} \equiv 1 (\operatorname{mod}\ p)</math>
，其中a為任一不被p整除的整數。該定理即可使用這些概念證得。這意味著
:<math>\sum_{a=1}^{p-1} a^{p-1} \equiv (p-1) \cdot 1 \equiv -1 \pmod p</math>。
[[吾鄉-朱加猜想]]表示，上述公式亦是p為質數的必要條件。另一個費馬小定理的推論如下：若p為2與5之外的其他質數，<sup>1</sup>/<sub>''p''</sub>總是個[[循環小數]]，其週期為{{nowrap|''p'' − 1}}或{{nowrap|''p'' − 1}}的因數。分數<sup>1</sup>/<sub>''p''</sub>依q（10以外的整數）為基底表示亦有類似的效果，只要p不是q的質因數的話。[[威爾遜定理]]表示，整數''p''&nbsp;>&nbsp;1為質數，若且唯若[[階乘]] (''p''&nbsp;−&nbsp;1)!&nbsp;+&nbsp;1可被p整除。此外，整數n > 4為合數，若且唯若 (''n''&nbsp;−&nbsp;1)<nowiki>!</nowiki>可被n整除。

===其他數學裡出現的質數===
許多數學領域裡會大量使用到質數。舉[[有限群]]的理論為例，[[西羅定理]]即是一例。該定理表示，若G是個有限群，且''p<sup>n</sup>''為質數p可整除G的[[階 (群論)|階]]的最大冪次，則G會有個''p<sup>n</sup>''階的子群。此外，任意質數階的群均為循環群（[[拉格朗日定理 (群論)|拉格朗日定理]]）。
<!--* If ''G'' is a finite group and ''p'' is a prime number dividing the order of ''G'', then ''G'' contains an element of order ''p''. ([[Cauchy's theorem (group theory)|Cauchy Theorem]])-->

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

===自然裡的質數===
[[周期蟬]]屬裡的[[蟬]]在其演化策略上使用到質數<ref>{{cite journal |last=Goles |first=E. |last2=Schulz |first2=O. |first3=M. |last3=Markus |year=2001 |title=Prime number selection of cycles in a predator-prey model |journal=[[Complexity (journal)|Complexity]] |volume=6 |issue=4 |pages=33–38 |doi=10.1002/cplx.1040 }}</ref>。蟬會在地底下以[[幼蟲]]的形態度過其一生中的大部分時間。周期蟬只會在7年、13年或17年後化蛹，然後從洞穴裡出現、飛行、交配、產卵，並在至多數週後死亡。此一演化策略的原因據信是因為若出現的週期為質數年，掠食者就很難演化成以周期蟬為主食的動物<ref>{{Citation | author = Paulo R. A. Campos, Viviane M. de Oliveira, Ronaldo Giro, and Douglas S. Galvão. | journal = [[Physical Review Letters]] | title = Emergence of Prime Numbers as the Result of Evolutionary Strategy | volume = 93 | doi = 10.1103/PhysRevLett.93.098107 | issue = 9 | year = 2004 | accessdate = 2006-11-26 | page = 098107 | postscript = . | bibcode=2004PhRvL..93i8107C|arxiv = q-bio/0406017 }}</ref>。若周期蟬出現的週期為非質數年，如12年，則每2年、3年、4年、6年或12年出現一次的掠食者就一定遇得到周期蟬。經過200年以後，假設14年與15年出現一次的周期蟬，其掠食者的平均數量，會比13年與17年出現一次的周期蟬，高出2%<ref>{{cite news|work=[[The Economist]]|url=http://economist.com/PrinterFriendly.cfm?Story_ID=2647052|title=Invasion of the Brood|date=2004-05-06|accessdate=2006-11-26|archive-date=2009-01-25|archive-url=https://web.archive.org/web/20090125102335/http://www.economist.com/PrinterFriendly.cfm?Story_ID=2647052|dead-url=no}}</ref>。雖然相差不大，此一優勢似乎已足夠驅動天擇，選擇具質數年生命週期的這些昆蟲。

據猜測，[[黎曼ζ函數|ζ函數]]的根與複數量子系統的能階有關<ref>{{cite web |author=Ivars Peterson |work=[[MAA Online]] |url=http://www.maa.org/mathland/mathtrek_6_28_99.html |title=The Return of Zeta |date=1999-06-28 |accessdate=2008-03-14 |deadurl=yes |archiveurl=https://web.archive.org/web/20071020141624/http://maa.org/mathland/mathtrek_6_28_99.html |archivedate=2007-10-20 }}</ref>。

==推廣==
質數的概念是如此的重要，以致此一概念被以不同方式推廣至數學的不同領域裡去。通常，「質」（prime）可在適當的意義下，用來表示具有最小性或不可分解性。例如，[[特徵 (代數)|質體]]是指一個包含0與1的體F的最小子體。質體必為有理數或具有p個元素的有限體，這也是其名稱的緣由<ref>{{Citation | last1=Lang | first1=Serge | author1-link=Serge Lang | title=Algebra | publisher=[[Springer-Verlag]] | location=Berlin, New York | series=Graduate Texts in Mathematics | isbn=978-0-387-95385-4 | mr=1878556 | year=2002 | volume=211}}, Section II.1, p. 90</ref>。若任一物件基本上均可唯一地分解成較小的部分，則這些較小的部分也會用「質」這個字來形容。例如，在[[紐結理論]]裡，[[素紐結|質紐結]]是指不可分解的紐結，亦即該紐結不可寫成兩個非平凡紐結的[[連通和]]。任一紐結均可唯一地表示為質紐約的連通和<ref>Schubert, H. "Die eindeutige Zerlegbarkeit eines Knotens in Primknoten". ''S.-B Heidelberger Akad. Wiss. Math.-Nat. Kl.'' 1949 (1949), 57–104.</ref>。[[質模型]]與[[三維質流形]]亦為此類型的例子。

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

:<math>\{ \dots, -11, -7, -5, -3, -2, 2, 3, 5, 7, 11, \dots \}\, </math>。

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

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

===質理想===
{{Main|質理想}}
在[[環論]]裡，數的概念一般被[[理想 (環論)|理想]]所取代。「質理想」廣義化了質元素的概念，為由質元素產生的[[主理想]]，是在[[交換代數]]、[[代數數論]]與[[代數幾何]]裡的重要工具與研究對象。整數環的質理想為理想 (0)、(2)、(3)、(5)、(7)、(11)、…算術基本定理被廣義化成[[準素分解]]，可將每個在[[可交換環|可交換]][[諾特環]]裡的理想表示成[[準素理想]]（為[[質數冪次]]的一適合廣義化）的交集<ref>{{Harvard citations | last1=Eisenbud | year=1995 |nb=yes|loc=section 3.3.}}</ref>。

透過[[環的譜]]這個概念，質理想成為代數幾何物件的點<ref>Shafarevich, Basic Algebraic Geometry volume 2 (Schemes and Complex Manifolds), p. 5, section V.1</ref>。[[算術幾何]]也受益於這個概念，且許多概念會同時存在於幾何與數論之內。例如，對一[[體擴張|擴張體]]的質理想[[伽羅瓦擴張內之質理想分解|分解]]（這是代數數論裡的一個基本問題），與[[分歧覆疊|幾何裡的分歧]]具有某些相似之處。此類分歧問題甚至在只關注整數的數論問題裡也會出現。例如，[[二次體]]的[[整數環]]內的質理想可被用來證明[[二次互反律]]。二次互反律討論下面二次方程
:<math>x^2 \equiv p \ \ (\text{mod } q),\,</math>
是否有整數解，其中x為整數，p與q為（一般）質數<ref>Neukirch, Algebraic Number theory, p. 50, Section I.8</ref>。早期對[[費馬最後定理]]證明之嘗試，於[[恩斯特·庫默爾]]引入[[正則素數]]後達到了高潮。正則質數是指無法在由下列式子（其中''a''<sub>0</sub>、…、''a''<sub>''p''−1</sub>為整數，ζ則是能使[[單位根|{{nowrap|ζ<sup>''p''</sup> {{=}} 1}}]]的複數）
:<math>a_0 + a_1 \zeta + \cdots + a_{p-1} \zeta^{p-1}\, , </math>
組成的環裡，使得唯一分解定理失效的質數<ref>Neukirch, Algebraic Number theory, p. 38, Section I.7</ref>。

===賦值===
[[賦值|賦值理論]]研究由一個體K映射至實數R的某個函數（稱之為[[賦值]]）<ref>Endler, Valuation Theory, p. 1</ref>。每個此類賦值都能給出一個[[拓撲環| K上的拓撲]]，且兩個賦值被稱為等價，若兩者有相同拓撲。K的質數為一賦值的[[等價類]]。例如，一個有理數q的[[p進賦值]]被定義為整數''v<sub>p</sub>''(''q'')，使得
:<math>q = p^{v_p(q)} \frac {r}{s},</math>
其中r與s不被p所整除。例如，{{nowrap|''v''<sub>3</sub>(18/7) {{=}} 2}}。p進範數被定義為<ref group="nb">Some sources also put <math>\left| q \right|_p := e^{-v_p(q)}. \,</math>.</ref>
:<math>\left| q \right|_p := p^{-v_p(q)}. \,</math>
特別的是，當一個數字乘上p時，其範數會變小，與一般的[[絕對賦值]]（亦稱為[[無限質數]]）形成明顯的對比。當透過絕對賦值[[完備化 (環論)|完備]]有理數會得出由[[實數]]所組成的[[體 (數學)|體]]，透過p進範數完備有理數則會得出由[[p進數]]所組成的[[體 (數學)|體]]<ref>Gouvea: p-adic numbers: an introduction, Chapter 3, p. 43</ref>。實際上，依據[[奧斯特洛夫斯基定理]]，上述兩種方法是完備有理數的所有方法。一些與有理數或更一般化之[[大域體]]有關的算術問題，可能可以被轉換至完備（或[[局部體|局部]]）體上。此一[[哈瑟原則|局部-全域原則]]再次地強調了質數對於數論的重要性。

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

[[NASA]]科學家[[卡爾·薩根]]在他的科幻小說《[[接觸未來]]》（''Contact''）裡，認為質數可作為與外星人溝通的一種方式。這種想法是他與美國天文學家[[法蘭克·德雷克]]於1975年閒聊時形成的<ref>{{cite web |last=Carl Pomerance |url=http://www.math.dartmouth.edu/~carlp/PDF/extraterrestrial.pdf |title=Prime Numbers and the Search for Extraterrestrial Intelligence |accessdate=2007-12-22 |archive-date=2021-05-06 |archive-url=https://web.archive.org/web/20210506145925/https://math.dartmouth.edu/~carlp/PDF/extraterrestrial.pdf |dead-url=no }}</ref>。

許多電影，如《[[異次元殺陣]]》（''Cube''）、《[[神鬼尖兵]]》（''Sneakers''）、《[[越愛越美麗]]》（''The Mirror Has Two Faces''）及《[[美麗境界]]》（''A Beautiful Mind''），均反映出大眾對質數與密碼學之神秘的迷戀<ref>{{cite web |url=http://www.musicoftheprimes.com/films.htm |title=The music of primes |access-date=2015-08-23 |archive-url=https://web.archive.org/web/20151009135943/http://www.musicoftheprimes.com/films.htm |archive-date=2015-10-09 |dead-url=yes }}</ref>。[[保羅·裘唐諾]]所著的小說《[[質數的孤獨]]》（The Solitude of Prime Numbers）裡，質數被用來比喻寂寞與孤獨，被描述成整數之間的「局外人」{{fact}}。

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

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

==註記==
<references group=nb/>
{{reflist|30em}}

==參考資料==
* {{Citation | last1=Apostol | first1=Thomas M. | author1-link=Thomas M. Apostol | title=Introduction to Analytic Number Theory | publisher=Springer | location=New York | isbn=0-387-90163-9 | year=1976}}
* {{Citation | last1=Conway | first1=John Horton | author1-link=John Horton Conway | last2=Guy | first2=Richard K. | author2-link=Richard K. Guy | title=The Book of Numbers | publisher=Copernicus | location=New York | isbn=978-0-387-97993-9 | year=1996}}
* {{Citation | last1=Crandall | first1=Richard | author1-link=Richard Crandall | last2=Pomerance | first2=Carl | author2-link=Carl Pomerance | title=Prime Numbers: A Computational Perspective | publisher=[[Springer-Verlag]] | location=Berlin, New York | edition=2nd | isbn=978-0-387-25282-7 | year=2005}}
* {{Citation | last1=Derbyshire | first1=John | author1-link=John Derbyshire | title=Prime obsession | publisher=Joseph Henry Press, Washington, DC | isbn=978-0-309-08549-6 | mr=1968857 | year=2003}}
* {{Citation | last1=Eisenbud | first1=David | author1-link= David Eisenbud | title=Commutative algebra | publisher=Springer-Verlag | location=Berlin, New York | series=Graduate Texts in Mathematics | isbn=978-0-387-94268-1| mr=1322960 | year=1995 | volume=150}}
* {{ citation | first1 = John B. | last1 = Fraleigh | year = 1976 | isbn = 0-201-01984-1 | title = A First Course In Abstract Algebra | edition = 2nd | publisher = [[Addison-Wesley]] | location = Reading }}
* {{Citation | last1=Furstenberg | first1=Harry | author1-link=Hillel Furstenberg | title=On the infinitude of primes | doi=10.2307/2307043 | year=1955 | journal=[[American Mathematical Monthly|The American Mathematical Monthly]]   | volume=62 | page=353 | jstor=2307043 | issue=5 | publisher=Mathematical Association of America}}
* {{citation|first1=Ben|last1=Green|author1-link=Ben J. Green|first2=Terence|last2=Tao|author2-link=陶哲軒|title=The primes contain arbitrarily long arithmetic progressions|journal=[[Annals of Mathematics]]|volume=167|issue=2|year=2008|pages=481–547|doi=10.4007/annals.2008.167.481|arxiv=math.NT/0404188}}
* {{Citation | last1=Gowers | first1=Timothy | author1-link=William Timothy Gowers | title=Mathematics: A Very Short Introduction | publisher=[[Oxford University Press]] | isbn=978-0-19-285361-5 | year=2002}}
* {{Citation | last1=Guy | first1=Richard K. | author1-link=Richard K. Guy | title=Unsolved Problems in Number Theory | publisher=Springer-Verlag | location=Berlin, New York | isbn=978-0-387-90593-8 | year=1981}}
* {{Citation | last1=Havil | first1=Julian | title=Gamma: Exploring Euler's Constant | publisher=[[Princeton University Press]] | isbn=978-0-691-09983-5 | year=2003}}
* {{Citation | last1=Hardy | first1=Godfrey Harold | author1-link=G. H. Hardy | title=A Course of Pure Mathematics | publisher=[[Cambridge University Press]] | isbn=978-0-521-09227-2 | year=1908}}
* {{Citation | last1=Hardy | first1=Godfrey Harold | author1-link=G. H. Hardy | title=[[A Mathematician's Apology]] | publisher=Cambridge University Press | isbn=978-0-521-42706-7 | year=1940}}
* {{ citation | first1 = I. N. | last1 = Herstein | year = 1964 | isbn = 978-1114541016 | title = Topics In Algebra | publisher = [[Blaisdell Publishing Company]] | location = Waltham | author1-link=Israel Nathan Herstein }}
* {{Citation | editor1-last=Hill | editor1-first=Peter Jensen | title=The Messiaen companion | publisher=Amadeus Press | location=Portland, Or | isbn=978-0-931340-95-6 | year=1995}}
* {{Citation|title=Additive Theory of Prime Numbers|last1=Hua|first1=L.K.|publisher=American Mathematical Society|year=2009|isbn=978-0821849422|series=Translations of Mathematical Monographs|volume=13|location=Providence, RI|pages=176–177|mr=0194404|oclc=824812353|orig-year=1965}}
* {{Citation | last1=Lehmer | first1=D. H. | author1-link=D. H. Lehmer | title=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 | publisher=Carnegie Institution of Washington | location=Washington, D.C. | year=1909}}
* {{ citation | first1 = Neal H. | last1 = McCoy | year = 1968 | title = Introduction To Modern Algebra, Revised Edition | publisher = [[Allyn and Bacon]] | location = Boston | lccn = 68-15225 }}
* {{Citation | last1=Narkiewicz | first1=Wladyslaw | title=The development of prime number theory: from Euclid to Hardy and Littlewood | publisher=Springer-Verlag | location=Berlin, New York | isbn=978-3-540-66289-1 | year=2000 |series=Springer Monographs in Mathematics}}
* {{Citation | last1=Ribenboim | first1=Paulo | author1-link=Paulo Ribenboim | title=The little book of bigger primes | publisher=Springer-Verlag | location=Berlin, New York | isbn=978-0-387-20169-6 | year=2004}}
* {{Citation | last1=Riesel | first1=Hans | title=Prime numbers and computer methods for factorization | publisher=Birkhäuser | location=Basel, Switzerland | isbn=978-0-8176-3743-9 | year=1994}}
* {{Citation | last1=Sabbagh | first1=Karl | title=The Riemann hypothesis | publisher=Farrar, Straus and Giroux, New York | isbn=978-0-374-25007-2 | mr=1979664 | year=2003}}
* {{Citation | last1=du Sautoy | first1=Marcus | title=The music of the primes | publisher=HarperCollins Publishers | isbn=978-0-06-621070-4 | mr=2060134 | year=2003 | url=http://www.musicoftheprimes.com/ | access-date=2015-08-23 | archive-url=https://web.archive.org/web/20150907212920/http://www.musicoftheprimes.com/ | archive-date=2015-09-07 | dead-url=yes }}

==外部連結==
{{Wiktionary}}
{{wikibooks|小学数学/质数与合数}}
*{{springer|title=Prime number|id=p/p074530}}
*Caldwell, Chris, The [[Prime Pages]] at [http://primes.utm.edu/ primes.utm.edu]{{Wayback|url=http://primes.utm.edu/ |date=20090527080907 }}.
*{{In Our Time|Prime Numbers|p003hyf5}}
*[http://www.maths.ex.ac.uk/~mwatkins/zeta/vardi.html An Introduction to Analytic Number Theory, by Ilan Vardi and Cyril Banderier]{{Wayback|url=http://www.maths.ex.ac.uk/~mwatkins/zeta/vardi.html |date=20060925090553 }}
*[http://plus.maths.org/issue49/package/index.html Plus teacher and student package: prime numbers]{{Wayback|url=http://plus.maths.org/issue49/package/index.html |date=20090704042640 }} from Plus, the free online mathematics magazine produced by the Millennium Mathematics Project at the University of Cambridge.
*[https://www.mersenneforum.org/attachment.php?attachmentid=24152&d=1610368418 出現質數實驗] {{Wayback|url=https://www.mersenneforum.org/attachment.php?attachmentid=24152&d=1610368418 |date=20210330125451 }}
*[http://www.khanacademy.org/cs/random-space-for-probability/1356370731 出現可以被整除的機率]

===質數產生器與計算器===
*[http://www.had2know.com/academics/prime-composite.html Prime Number Checker] {{Wayback|url=http://www.had2know.com/academics/prime-composite.html |date=20210503055339 }} identifies the smallest prime factor of a number.
*[http://www.alpertron.com.ar/ECM.HTM Fast Online primality test with factorization]{{Wayback|url=http://www.alpertron.com.ar/ECM.HTM |date=20090910074733 }} makes use of the Elliptic Curve Method (up to thousand-digits numbers, requires Java).
*[http://www.bigprimes.net/ Huge database of prime numbers]{{Wayback|url=http://www.bigprimes.net/ |date=20090924111721 }}
*[http://www.primos.mat.br/indexen.html Prime Numbers up to 1 trillion] {{Wayback|url=http://www.primos.mat.br/indexen.html |date=20210227001026 }}
* [http://zh.numberempire.com/primenumbers.php 素数发生器和校验器] {{Wayback|url=http://zh.numberempire.com/primenumbers.php |date=20210119040247 }}

{{質數}}
{{Divisor classes navbox}}

{{Authority control}}

[[Category:素数| ]]
[[Category:整数数列|S]]