質數檢視原始碼討論檢視歷史
| 質數 | |
|---|---|
質數，又稱素數，有無限個。 數學家把自然數按照乘法性質劃分為： 1，自然數1； 2，素數，大於1隻能被1和自身整除的自然數。例如，2,3,5,7，.....。 3，複合數，至少有兩個素數因子。例如，4,6,8,9,10，....。
根據算術基本定理，每一個比1大的整數，要麼本身是一個質數，要麼可以寫成一系列質數的乘積;而且如果不考慮這些質數在乘積中的順序，那麼寫出來的形式是唯一的。最小的質數是2。
按照埃拉特斯尼篩法，可以構造一個公式：
素數的埃拉特斯特尼篩法公式素數普遍公式
（清華大學出版社【品數學】第5頁）
西元前250年同樣是古希臘的數學家埃拉托塞尼提出一種篩法：
（一），「要得到不大於某個自然數N的所有素數，只要在2---N中將不大於√N的素數的倍數全部划去即可」。
（二），「如果自然數N是合數，則它有一個因子d滿足1<d≤√N.。
（三），如果自然數N是素數，當且僅當N不能被不大於√N的任何素數整除」。
見（代數學辭典[上海教育出版社]1985年。屜部貞世朗編。259頁）。
（四），對於（三）這句話的漢字可以等價轉換成為用英文字母表達的公式：
公式形式：
N=P₁M₁+A₁=P₂M₂+A₂=.....=Pr Mr +Ar ......(1)。
其中P₁，P₂，....，Pr 表示順序素數 2，3，5，......。Ai≠0。
這樣解得的N，若N＜P²r+1，則N是一個素數。
我們可以把（1）式內容等價轉換同餘式組表示：
N≡A₁(modP₁)，N≡A₂(modP₂)，.....N≡Ar(modPr)。。。。.（2）
由於（2）的模P₁，P₂，，.，Pr 都是素數，因此兩兩互素，根據孫子定理(中國剩餘定理）知，對於給定的A₁，A₂，，，Ar，（2）式在P₁P₂....Pr範圍內有唯一解。
範例
例如，r=1，N=2M₁+1,解得N=3,5,7。7﹤3²=9，求得了（3,3²）區間的全部素數。
r=2，
N=2M₁+1=3M₂+1,解得N=7,13,19;
N=2M₁+1=3M₂+2,解得N=5,11,17,23.
求得了（5,5²）區間的全部素數。
仿此下去，可以一個不漏地求得任意大的全部素數。
人類為了尋找這個公式，花費了2000多年
2016年1月，發現世界上迄今為止最大的質數，長達2233萬位，如果用普通字號將它打印出來長度將超過65公里。
質數個數
質數的個數是無窮的。歐幾里得的《幾何原本》中有一個經典的證明。它使用了證明常用的方法：反證法。具體證明如下：假設質數只有有限的n個，從小到大依次排列為p1，p2，……，pn，設N=p1×p2×……×pn，那麼，N+1是素數或者不是素數。[1] 如果N+1為素數，則N+1要大於p1，p2，……，pn，所以它不在那些假設的素數集合中。 如果N+1為合數，因為任何一個合數都可以分解為幾個素數的積；而N和N+1的最大公約數是1，所以N+1不可能被p1，p2，……，pn整除，所以該合數分解得到的素因數肯定不在假設的素數集合中。 因此無論該數是素數還是合數，都意味着在假設的有限個素數之外還存在着其他素數。所以原先的假設不成立。也就是說，素數有無窮多個。
其他數學家給出了一些不同的證明。歐拉利用黎曼函數證明了全部素數的倒數之和是發散的，恩斯特·庫默的證明更為簡潔，HillelFurstenberg則用拓撲學加以證明。
對於一定範圍內的素數數目的計算
儘管整個素數是無窮的，仍然有人會問「100，000以下有多少個素數？」，「一個隨機的100位數多大可能是素數？」。素數定理可以回答此問題。
相關定理
在一個大於1的數a和它2倍之間（即區間(a, 2a]中）必存在至少一個素數。
著名猜想
哥德巴赫猜想：是否每個大於2的偶數都可寫成兩個素數之和？https://factpedia.org/wiki/%E5%93%A5%E5%BE%B7%E5%B7%B4%E8%B5%AB%E7%8C%9C%E6%83%B3%E7%9C%9F%E7%9B%B8
孿生素數猜想：孿生素數就是差為2的素數對，例如11和13。是否存在無窮多的孿生素數？https://factpedia.org/wiki/%E5%AD%AA%E7%94%9F%E7%B4%A0%E6%95%B0%E7%8C%9C%E6%83%B3%E7%9C%9F%E7%9B%B8
斐波那契數列內是否存在無窮多的素數？是否有無窮多個的梅森素數？在n2與（n+1）2之間是否每隔n就有一個素數？是否存在無窮個形式如X2+1素數？
性質介紹
質數具有許多獨特的性質：
（1）質數p的約數只有兩個：1和p。
（2）初等數學基本定理：任一大於1的自然數，要麼本身是質數，要麼可以分解為幾個質數之積，且這種分解是唯一的。
（3）質數的個數是無限的。
（4）質數的個數公式π（n）是不減函數。
（5）若n為正整數，在n的2次方到（n+1）的2次方 之間至少有一個質數。
（6）若n為大於或等於2的正整數，在n到n!之間至少有一個質數。
（7）若質數p為不超過n(n大於等於4)的最大質數，則p>n/2 。
素性檢測
素性檢測一般用於數學或者加密學領域。用一定的算法來確定輸入數是否是素數。不同於整數分解，素性測試一般不能得到輸入數的素數因子，只說明輸入數是否是素數。大整數的分解是一個計算難題，而素性測試是相對更為容易（其運行時間是輸入數字大小的多項式關係）。有的素性測試證明輸入數字是素數，而其他測試，比如米勒 - 拉賓（Miller–Rabin ）則是證明一個數字是合數。因此，後者可以稱為合性測試。質數是因數只有1和它本身的數。
素性測試通常是概率測試（不能給出100%正確結果）。這些測試使用除輸入數之外，從一些樣本空間隨機出去的數；通常，隨機素性測試絕不會把素數誤判為合數，但它有可能為把一個合數誤判為素數。誤差的概率可通過多次重複試驗幾個獨立值a而減小；對於兩種常用的測試中，對任何合數n，至少一半的a檢測n的合性，所以k的重複可以減小誤差概率最多到2^{-k}，可以通過增加k來使得誤差儘量小。
隨機素性測試的基本結構：
1.隨機選取一個數字a。
2.檢測某個包含a和輸入n的等式（與所使用的測試方法有關）。如果等式不成立，則n是合數，a作為n是合數的證據，測試完成。
3.從1步驟重複整個過程直到達到所設定的精確程度。
在幾次或多次測試之後，如果n沒有被判斷為合數，那麼我們可以說n可能是素數。
常見的檢測算法：費馬素性檢驗（Fermat primality test），米勒拉賓測試（Miller–Rabin primality test） ，Solovay–Strassen測試（Solovay–Strassen primality test），盧卡斯-萊默檢驗法（英語：Lucas–Lehmer primality test）。
著名難題
歌德巴赫猜想
梅森質數
17世紀還有位法國數學家叫梅森，他曾經做過一個猜想：當2p-1 中的p是質數時，2p-1是質數。他驗算出：當p=2、3、5、7、17、19時，所得代數式的值都是質數，後來，歐拉證明p=31時，2p-1是質數。 p=2，3，5，7時，2p-1都是素數，但p=11時，所得2,047=23×89卻不是素數。
梅森去世250年後，美國數學家科勒證明，267-1=193,707,721×761,838,257,287，是一個合數。這是第九個梅森數。20世紀，人們先後證明：第10個梅森數是質數，第11個梅森數是合數。質數排列得雜亂無章，也給人們尋找質數規律造成了困難。
迄今為止，人類僅發現48個梅森質數。中央密蘇里大學在2013年1月25日協調世界時間23:30:26發現的質數，為迄今發現的最大質數，同時是一個梅森質數。由於這種質數珍奇而迷人，它被人們稱為「數學珍寶」。值得一提的是，中國數學家和語言學家周海中根據已知的梅森質數及其排列，巧妙地運用聯繫觀察法和不完全歸納法，於1992年正式提出了梅森素質分布的猜想，這一重要猜想被國際上稱為「周氏猜測」。[1]
2016年1月7日，美國密蘇里中央大學數學家柯蒂斯·庫珀（Curtis Cooper）找到了目前人類一直的最大素數——「2的74,207,281次方減1」（2^74207281-1），數值高達22,338,618位數。
柯蒂斯·庫珀是通過 Great Internet Mersenne Prime Search（GIMPS，互聯網梅森素數大搜索）找到該素數，這是第49個梅森素數，這一重大發現無疑為互聯網梅森素數大搜索誕生20周年獻了厚禮。
這也是柯蒂斯·庫珀第四次通過互聯網梅森素數大搜索發現新的梅森素數，刷新了他自己的記錄。[2]
應用領域
質數被利用在密碼學上，所謂的公鑰就是將想要傳遞的信息在編碼時加入質數，編碼之後傳送給收信人，任何人收到此信息後，若沒有此收信人所擁有的密鑰，則解密的過程中（實為尋找素數的過程），將會因為找質數的過程（分解質因數）過久，使即使取得信息也會無意義。
在汽車的設計上，相鄰的兩個大小齒輪齒數最好設計成質數，以增加兩齒輪內兩個相同的齒相遇嚙合次數的最小公倍數，可增強耐用度減少故障。
在害蟲的生物生長周期與殺蟲劑使用之間的關係上，殺蟲劑的質數次數的使用也得到了證明。實驗表明，質數次數地使用殺蟲劑是最合理的：都是使用在害蟲繁殖的高潮期，而且害蟲很難產生抗藥性。
以質數形式無規律變化的導彈和魚雷可以使敵人不易攔截。
多數生物的生命周期也是質數（單位為年），這樣可以最大程度地減少碰見天敵的機會。