55世纪,雷火电竞最新网址,雷火电竞APP下载

來源：互聯網

質數（Prime number），也稱素數，是指在大于1的自然數中，除了1和它本身以外不再有其他因數的自然數；否則稱為合數（規定1既不是質數也不是合數）。

質數的研究最早可追溯到古埃及。在公元前1550年左右的古埃及的萊因特紙草書中就有對素數與對合數完全不同類型的記錄。古希臘的畢達哥拉斯學派，歐幾里得，和埃拉托斯特尼等人對質數有不少研究。他們把“2”排除在質數之外，因為“2”不是“真正的數”。近現代數學中，皮埃爾·德·費馬，法國博學家馬林·梅森，德國數學家克里斯蒂安·哥德巴赫和瑞士數學家萊昂哈德·歐拉等人得到了一些關于質數的重要成果。法國數學家阿德里安-馬里·勒讓德與德國數學家約翰·卡爾·弗里德里希·高斯各自獨立證明了素數定理。法國數學家雅克·阿達馬和比利時數學家夏爾-讓·德拉瓦萊·普桑完成了素數定理的初等證明。不過質數依然有許多懸而未決的理論，比如著名的哥德巴赫猜想等。

質數有一些基本性質，如質數有無窮多個，用反證法和最小自然數原理可以證明質數有無窮多個。在質數范疇里，2是唯一的一個偶質數，其余質數都是奇數。設a為大于1的正整數，若p是a的大于1的最小正約數則p必為質數。質數的判定方法分為確定性和不確定性算法兩種，其中試除法是較為基礎常用的確定性算法。質數的篩選方法以埃拉托斯特尼篩法為代表。

質數作為數論中重要的概念之一，在數學、密碼學、生物學、量子力學等領域應用廣泛，如在密碼學中，質數在公鑰加密算法如RSA中起著關鍵作用。這些算法的安全性基于大質數的分解難度。此外，它也常出現在影視作品和文學作品中。

定義

質數又稱素數。一個大于1的自然數，除了1和它自身外，不能被其他自然數整除的數叫做質數；否則稱為合數（規定1既不是質數也不是合數）。

歷史

質數的發展歷程

質數也叫素數，它的歷史悠久。在公元前 1550 年左右的古埃及的萊因德數學紙草書中就有對素數與對合數完全不同類型的記錄。古希臘的畢達哥拉斯學派（英語：Pythagoras）對質數有不少研究。他們把“2”排除在質數之外，因為“2”不是“真正的數”。公元前300年左右的歐幾里得（希臘語：Ευκλειδη?）所著的《幾何原本》包含與素數有關的重要定理，如有無限多個素數，以及算術基本定理。埃拉托斯特尼（古希臘語：Eratosthenes Sieve）提出的埃拉托斯特尼篩法是用來計算素數的一個簡單方法。新畢達哥拉斯學派的學者尼科馬庫斯（英語：Nicomachus）的《算數導論》定義了素數、合數和完全數,包括對埃拉托斯特尼篩選法的描述,并列出了前4個完全數 (6、28、496 和 8128)。接下來一段時間關于質數的研究發展緩慢，公元6世紀印度數學家婆羅摩笈多（印度語：Brahmagupta）和公元9世紀阿拉伯數學家塔比·庫拉（阿拉伯語：Thglbit ibn Qurra）對質數有一些研究。

1640年，皮耶·德·費瑪（法語：Pierre de Fermat）敘述了費馬小定理，費馬還研究了費馬數的素數。法國博學家馬林·梅森（法語：Marin Mersenne）發現了一類素數，即梅森素數。?德國數學家克里斯蒂安·哥德巴赫（德語：Goldbach C）在 1742 年寫給歐拉的一封信中提出了哥德巴赫的猜想，即每個偶數都是兩個素數之和。瑞士數學家萊昂哈德·歐拉（德語：Leonhard Euler）有許多和質數有關的成果。他證明了素數倒數和的無窮級數會發散。19世紀初，法國數學家阿德里安-馬里·勒讓德（法語：Adrien-Marie Legendre）與德國數學家約翰·卡爾·弗里德里希·高斯（德語：Johann Carl Friedrich Gauss）獨立推測，當趨向無限大時，小于的素數數量會趨近于。德國數學家伯恩哈德·黎曼（德語：Bernhard Riemann）在1859年關于zeta函數的論文中提出了證明勒讓德和gaussian猜想的大綱。盡管黎曼假說仍未得到證實，但黎曼的大綱于 1896 年由法國數學家雅克·阿達馬（法語：Jacques Solomon Hadamard）和比利時數學家夏爾-讓·德拉瓦萊·普桑（法語：Charles-Jean de La Vallée Poussin）完成，論文的結果現在被稱為素數定理。

隨著質數的不斷研究，質數的檢驗成了重要的課題。許多數學家已經研究了比試除法實際適用的數字更大的數字的素數檢驗。包括皮耶·德·費瑪數檢驗、盧卡斯-萊默素數檢驗和廣義盧卡斯素數檢驗等。質數的應用也越來越廣，著名的RSA密碼系統就以質數的理論作為基礎。隨著現代計算機的發展，一些計算質數和檢驗質數的算法也不斷被提出。不過一些質數的理論仍然沒有得到完美地解決，一代一代的數學家正努力朝著最終的結果邁進。

“1”的素性

在古希臘早期，大多數人們甚至不認為“1”是一個數，自然也不會認為“1”是質數。到了中世紀與文藝復興時期，許多數學家將“1”考慮為第一個質數。到18世紀中葉，?德國數學家克里斯蒂安·哥德巴赫在他與瑞士數學家萊昂哈德·歐拉的通信里將“1”列為第一個質數，但歐拉持反對意見。到了19世紀，仍有許多數學家認為數字“1”是個質數，如美國數學家德里克·萊默（英語：Derrick Henry Lehmer）。

事實上，如果將質數的定義加入“1”，那么許多涉及質數的定理、概念等將需要重新措辭。例如，算術的基本定理需要根據因式分解重新表述為大于“1”的質數，因為每個數字都會有多個因式分解。如果埃拉托斯特尼篩法將“1”作為素數處理，它將無法正常工作，因為它會消除“1”的所有倍數（即所有其他數字）并僅輸出單個數字“1”。質數的其他一些更復雜性質也不適用于數字“1”，比如歐拉函數和除數函數之和的公式對于質數包含“1”與否的公式不同。到20世紀初，數學家們開始同意，“1”不應該被列為質數，而應該作為一個“單位”劃分為一個特殊的類別。

舉例

例1

5是個質數，數字2、3與4均不能整除5。6不是個質數，數字2、3均能整除6。

例2

前50個質數為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。

例3

第1000個質數是7919。

基本性質

性質1

質數有無窮多個。

證明：用反證法和最小自然數原理來證明。最小自然數原理指的是任何非空的自然數集中都有最小的自然數。假設只有有限個不可約數（注意：已約定質數一定是正的）,它們是，考慮，顯見，及，由假設知為合數。則知必有不可約數。由假設知必等于某個，因而一定整除，但不可約數，這是不可能的，矛盾。因此，假設是錯誤的，即不可約數必有無窮多個。證畢。

性質2

算術基本定理：任一大于1的自然數，要么本身是質數，要么可以分解為幾個質數之積，且這種分解是唯一的。

證明：使用反證法和最小自然數原理來證明。假設結論不成立，則存在正整數，它不可表示為質數的乘積。設所有這種正整數組成的集合為，它是非空的。設是中的最小正整數。顯見，一定是合數，所以必有。由假設及的最小性知，不屬于集合，所以都可表示為質數的乘積：

，這樣，就把表示為質數的乘積，這與假設矛盾，證畢。

算數基本定理

定理引理（英文：Fundamental lemma of arithmetic）：設是質數，，那么或至少有一個成立。一般地，若，則至少有一個成立。

算數基本定理（英文：fundamental theorem of arithmetic）：設，那么必有，其中是質數，且在不計次序的意義下，表達式是唯一的。

例子

。

算數基本定理不成立的情況

設集合，則該集合內算數基本定理不成立。原因為，該集合可以引入整除、不可約數、質數等概念，但它們的整除性質本質上是不同的，進一步地，該集合很難引入最大公約數的概念。

數論性質

概念

模：設，若，即，則稱為模。

既約剩余系：先給出剩余類的定義。把全體整數分為這樣的若干個兩兩不相交的集合，使得在同一個集合中的任意兩個數對模一定同余，而屬于不同集合中的兩個數對模一定不同余。每一個這樣的集合稱為模的剩余類。一組數稱為模的既約（或互素）剩余系，如果，以及對任意的，有且僅有一個是對模的剩余，即同余于模。

互素：若，則稱和是既約的，或是互素的。一般地，若，則稱是既約的，或是互素的。

歐拉函數

模的既約剩余系的元素個數就是歐拉函數（英文：Euler function），以下介紹歐拉函數的性質。

性質1

設，若與有相同的素因素，那么，特別地，若，，則。若，則。

性質2

對任意正整數有。

性質3

費馬-歐拉定理（英文：Fermat-Euler's theorem）：設，則有，特別當為質數時，對任意的有。通常把后式稱為費馬小定理（英文：Fermat's little theorem），前式稱為歐拉定理（英文：Euler's theorem）。

威爾遜定理

設是質數，是模的既約剩余系，就有，特別地，有。

p進數

p進數（英文：p-adic number）也稱作局部數域，是有理數域拓展成的完備數域的一種。p進數的距離概念建立在整數的整除性質上。給定素數p，若兩個數之差被p的高次冪整除，那么這兩個數距離就“接近”，冪次越高，距離越近。這種定義在數論性質上的“距離”能夠反映同余的信息。

分析學性質

素數定理

設是給定的實數，以表示不超過的素數個數。素數定理是指以下的漸進公式：

和。上述兩式可簡寫為：。

素數定理直到1896年才為法國數學家雅克·阿達馬（法語：J. Hadamard）和比利時數學家德·拉·瓦·布桑（法語：Charles Jean de la Vallée Poussin），利用十分高深的復變函數理論所各自獨立證明。直到1949年，美籍挪威數學家阿特勒·塞爾伯格（英文：A.Selberg）和匈牙利數學家愛爾特希（英文： P.Erdos）才各自獨立地給出了這個定理的初等證明，但證明十分復雜。

狄利克雷算術級數定理

狄利克雷算術級數定理（英文：Dirichlet's theorem on arithmetic progressions）：對于任意兩個正的互質整數和?，存在無限多形式的的質數，其中也是一個正整數。的級數形式為：

狄利克雷算術級數定理的更強形式指出，對于任何這樣的算術級數，級數中素數的倒數之和是發散的，并且具有相同模數的不同算術級數具有大致相同的素數比例。等效地，素數均勻分布（漸近）在包含與的互質的同余類模中。

Zeta 函數和黎曼假設

黎曼假設（英文：Riemann hypothesis）是1859年數學中最著名的未解問題之一，也是千禧年獎問題之一。它是伯恩哈德·黎曼Zeta函數的零點分布的猜想。黎曼猜想提出，Zeta函數非平凡零點的實數部分是，即所有的非平凡零點都應該位于直線（“臨界線”）上。為一實數，而為虛數的基本單位。Zeta函數定義為：

。

質數在自然數中的分布問題在純粹數學和應用數學上都很重要，但它的分布沒有什么規律。伯恩哈德·黎曼發現質數出現的頻率與黎曼Zeta函數緊密相關。如果黎曼假設成立，那么由素數定理給出的質數的漸近分布將在更短的區間內成立。

二次多項式的素值

歐拉指出函數在時均產生質數。在時會產生合數。對這種現象的解釋導致了黑格納數（英文：Heegner number）問題和類數問題（英文：Class number problem）。哈代-利特爾伍德猜想（英文：Hardy-Littlewood conjecture F）根據對數積分和多項式系數預測了具有整數系數的二次多項式值中的素數密度。沒有二次多項式被證明可以取無限多的素數。

質數的判定

質數的判定有確定性算法和不確定性算法兩類方法，確定性是指可以肯定地給出一個數是不是質數，不確定性算法則有可能出錯。

確定性算法

試除法

這是判斷質數的最基本方法。試除法將該數除以每個大于1且小于等于的數。若存在一個相除為整數的結果，則不是質數。反之則是個質數。試除法在數字較小的時候可以使用，但當數字較大時運算極慢，需要面對指數爆炸的情況。

AKS素性測試

AKS素性測試由三個來自印度坎普爾理工學院的計算機科學家，曼寧德拉·阿格拉瓦爾（英文：Manindra Agrawal）、尼拉吉·卡亞爾（英文：Neeraj Kayal）和尼汀·沙克謝納（英文：Nitin Saxena）提出的計算機算法。它的計算時間復雜度為。

橢圓曲線素性證明

橢圓曲線素性證明（英文：Elliptic curve primality proving）簡稱ECPP，是素數證明中最快、使用最廣泛的方法之一。它的計算時間復雜度為。

不確定性算法

費馬素數判定法

費馬素數判別法使用到如下的費馬小定理：如果是質數，，那么。若想要測試一個數字b是否為素數，則可隨機選擇n來計算的值。這個測試的缺點在于，有些合數即使不是素數，也會符合上述等式。這些數叫卡邁克爾數，比如561,1105,1729。

質數的篩選

埃拉托斯特尼篩法

對給定的正整數，從已知不超過的所有素數出發，找出不超過的所有素數的方法，就稱為埃拉托斯特尼篩法（古希臘語：Eratosthenes Sieve）。這是篩選素數的十分有效的方法，至今構造素數表仍是利用這個方法。埃拉托斯特尼篩法通常指下列兩個等價的公式：

或，

這里表示序列中所有與既約的數的個數。

埃拉托斯特尼篩法可以經公式推導為下述公式：

這就給出了計算的一個有效算法。

以下是一個例子：

例：求不超過100的質數個數。

解：取，不超過的質數是2,3,5,7，所以得

即不超過100的質數個數有25個。

質數個數與大小的弱估計

先介紹一個重要函數，莫比烏斯函數（英文：Mobius 函數）記作，定義為：

莫比烏斯函數可以推出埃拉托斯特尼篩法的公式。它也可以推出一個重要定理：

設，表示不超過，且其素因數都大于的所有正整數的個數，那么

。

上述定理可以得到的很弱的下界估計及第個質數的很弱的上界估計，共兩個：

結論1：設，一定存在正常數，使得這里表示第個質數。

結論2：設全體質數按大小排列排成的序列是，有及。

質數個數與大小的強估計

切比雪夫不等式（俄語：Чебышев）是依靠的素因數分解式來給出從階來說最好的上下界估計。不等式形式如下：

設，有及，這里表示第個質數。

質數的猜想

關于質數的猜想有非常多，這里介紹幾個著名猜想。

哥德巴赫猜想

哥德巴赫猜想（英文：Goldbach's conjecture）：是否每一個大于2的偶數都可以寫成兩個素數之和？

哥德巴赫猜想最早出現在1742年普魯士數學家哥德巴赫（英文：Goldbach）與歐拉的通信中。哥德巴赫原初猜想的現代陳述為：任一大于5的整數都可寫成三個質數之和。歐拉在回信中注明此一猜想可以有另一個等價的版本：任一大于2的偶數都可寫成兩個質數之和。從關于偶數的哥德巴赫猜想可推出：任一大于5的奇數都可寫成三個素數之和。后者被稱為弱哥德巴赫猜想。弱哥德巴赫猜想已于1937年蘇聯數學家列夫·杰里科維奇·史尼爾曼證明。而哥德巴赫猜想的證明難度比弱哥德巴赫猜想難度大得多，很長時間以來都沒有什么實質性的進展。

挪威數學家布朗（法語：Brun）于1919年使用推廣后的埃拉托斯特尼篩法證明了：所有充分大的偶數都能表示成兩個數之和，并且兩個數的素因數個數都不超過9個。這個方法的思路是：如果能將其中的“9個”縮減到“1個”，就證明了哥德巴赫猜想。布朗證明的命題可以被記作“9+9”，以此類推，哥德巴赫猜想就是“1+1”。1966 年，陳景潤宣布他證明了“陳氏定理”，并于1973 年發表了“1+2”的全部證明。這在國際數學界引起了強烈的反響，并且一致地將這一結果稱為陳景潤定理。時至今日，這也是哥德巴赫猜想所得到的最好結果。

梅森猜想

梅森猜想（英文：Mersenne's conjecture）：對于任何奇自然數p，若以下其中兩句敘述成立，剩下的一句就會成立：

1.或。

2.是質數。

3.是質數。

其中，就是著名的梅森素數。梅森猜想最開始是法國博學家馬林·梅森（法語：Marin Mersenne）提出的，但他最先的猜想存在錯誤。最后由美國數學家貝特曼（英語：?P. T.?Bateman）等人提出了新梅森猜想，就是上述形式。新梅森猜想更被視作是一種已證實的規律，而不是未解決的難題。

波利尼亞克猜想

波利尼亞克猜想（英文：Polignac's conjecture）：對于任何正偶數?n，存在無限多大小為 n?的素數間隙。換句話說：有兩個連續的素數有無窮多的情況，差值為n。

應用

數學

質數可用于構造多邊形和多邊形分區。對于費馬質數，其中為自然數。時3，5，17，257和65537為質數，時則為合數。在幾何的尺規作圖中，正多邊形可尺規做圖當且僅當正多邊形的邊數的奇質數因子是費馬數。當是質數冪時，就可以將一個正多邊形劃分成個周長、面積相等的多邊形分區。

密碼學

質數在密碼學中起著關鍵作用，特別是在公鑰加密算法如RSA中。這些算法的安全性基于大質數的分解難度。RSA系統是三位計算機科學家羅納德·林·里維斯特（英文：R.L. Rivest），阿迪·薩莫爾（英文：A. Shamir）及萊納德·阿德爾曼（英文：L.Adleman）于1978年提出的基于歐拉定理及大數的素因子分解所提出的公開加密方式的密碼系統。下面簡介RSA的理論原理。

設是兩個不同的大質數，再設正整數滿足，這樣對任一整數A，，必有唯一的整數B滿足，從而對任意整數必有，因此，有。這樣，如果某甲知道了數(但不知道)，他為了把A發送給知道的某乙而不讓別人知道，就可以公開把確定的B發送給某乙，因為乙可以利用式子確定的來由B得到A。由于大數要分解為這兩個素數的乘積是十分困難的，所以，不知道的人很難獲得正確的數A。這就是RSA系統的基本原理。這樣，任何一個信息都可以先數字化，然后以這樣的方式發送。這就是乙為自己建立了一個公開加密方式——公開數及轉換方式-——的密碼系統。任何人可以公開向乙這樣發送信息，而難以被他人破解。

生物學

Magicicada?屬蟬使用的進化策略利用了質數。這些昆蟲一生中的大部分時間都是作為蠐螬在地下度過的。它們只會在 7 年、13 年或 17 年后化蛹，然后從洞穴中出來，此時它們會飛來飛去，繁殖，然后最多幾周后死亡。生物學家推測，這些質數繁殖周期長度已經進化，以防止捕食者與這些周期同步。

量子力學

質數在量子信息科學中也很重要，質數的一些數學結構例如互無偏基和對稱信息完備的正算子值測度對于構建量子信息有著重要的作用。在不等于 3 的素數維數中，每個組協變對稱信息完全正算子值測度（碳化硅 POVM）相對于唯一的海森伯格赫爾曼·外爾（HW）群是協變的。此外，SIC POVM 的對稱群是Clifford群的一個子群。因此，當且僅當兩個SIC POVM相對于HW群的協變在擴展的 Clifford 群的同一軌道上時，它們在酉或反酉等價。也有數學家和物理學家推測伯恩哈德·黎曼 zeta 函數的零點與量子系統的能級有關。

必威电竞|足球世界杯竞猜平台

定義

相關概念

素因數

公約數

歷史