質數檢視原始碼討論檢視歷史
| 質數 | |
|---|---|
質數，又稱素數，有無限個。一個大於1的自然數，除了1和它本身外，不能被其他自然數整除，換句話說就是該數除了1和它本身以外不再有其他的因數;否則稱為合數。
根據算術基本定理，每一個比1大的整數，要麼本身是一個質數，要麼可以寫成一系列質數的乘積;而且如果不考慮這些質數在乘積中的順序，那麼寫出來的形式是唯一的。最小的質數是2。
目前為止，人們未找到一個公式可求出所有質數。[1] 2016年1月，發現世界上迄今為止最大的質數，長達2233萬位，如果用普通字號將它打印出來長度將超過65公里。
質數個數
質數的個數是無窮的。歐幾里得的《幾何原本》中有一個經典的證明。它使用了證明常用的方法：反證法。具體證明如下：假設質數只有有限的n個，從小到大依次排列為p1，p2，……，pn，設N=p1×p2×……×pn，那麼，N+1是素數或者不是素數。[2] 如果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]中）必存在至少一個素數。 存在任意長度的素數等差數列。（格林和陶哲軒，2004年） 一個偶數可以寫成兩個數字之和，其中每一個數字都最多只有9個質因數。（挪威布朗，1920年） 一個偶數必定可以寫成一個質數加上一個合成數，其中的因子個數有上界。（瑞尼，1948年） 一個偶數必定可以寫成一個質數加上一個最多由5個因子所組成的合成數。後來，有人簡稱這結果為 (1 + 5) (中國，1968年) 一個充分大偶數必定可以寫成一個素數加上一個最多由2個質因子所組成的合成數。簡稱為 (1 + 2) (中國陳景潤)
著名猜想
哥德巴赫猜想：是否每個大於2的偶數都可寫成兩個素數之和？
孿生素數猜想：孿生素數就是差為2的素數對，例如11和13。是否存在無窮多的孿生素數？
斐波那契數列內是否存在無窮多的素數？是否有無窮多個的梅森素數？在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）。
著名難題
歌德巴赫猜想
在1742年給歐拉的信中哥德巴赫提出了以下猜想：任一大於2的整數都可寫成三個質數之和。因現今數學界已經不使用「1也是素數」這個約定，原初猜想的現代陳述為：任一大於5的整數都可寫成三個質數之和。歐拉在回信中也提出另一等價版本，即任一大於2的偶數想陳述為歐拉的版本。把命題"任一充分大的偶數都可以表示成為一個素因子個數不超過a個的數與另一個素因子不超過b個的數之和"記作"a+b"。1966年陳景潤證明了"1+2"成立，即"任一充分大的偶數都可以表示成二個素數的和，或是一個素數和一個半素數的和"。 今日常見的猜想陳述為歐拉的版本，即任一大於2的偶數都可寫成兩個素數之和，亦稱為「強哥德巴赫猜想」或「關於偶數的哥德巴赫猜想」。
從關於偶數的哥德巴赫猜想，可推出任一大於7的奇數都可寫成三個質數之和的猜想。後者稱為「弱哥德巴赫猜想」或「關於奇數的哥德巴赫猜想」。
若關於偶數的哥德巴赫猜想是對的，則關於奇數的哥德巴赫猜想也會是對的。1937年時前蘇聯數學家維諾格拉多夫已經證明充分大的奇質數都能寫成三個質數的和，也稱為「哥德巴赫-維諾格拉朵夫定理」或「三素數定理」。
黎曼猜想
黎曼猜想是關於黎曼ζ函數ζ(s)的零點分布的猜想，由數學家波恩哈德·黎曼（1826～1866）於1859年提出。德國數學家希爾伯特列出23個數學問題。其中第8問題中便有黎曼假設。素數在自然數中的分布並沒有簡單的規律。黎曼發現素數出現的頻率與黎曼ζ函數緊密相關。黎曼猜想提出：黎曼ζ函數ζ(s)非平凡零點（在此情況下是指s不為-2、-4、-6等點的值）的實數部份是1/2。即所有非平凡零點都應該位於直線1/2 + ti（「臨界線」（critical line））上。t為一實數，而i為虛數的基本單位。至今尚無人給出一個令人信服的關於黎曼猜想的合理證明。
在黎曼猜想的研究中，數學家們把複平面上 Re(s)=1/2 的直線稱為 critical line。 運用這一術語，黎曼猜想也可以表述為：黎曼ζ 函數的所有非平凡零點都位於 critical line 上。
黎曼猜想是黎曼在 1859 年提出的。在證明素數定理的過程中，黎曼提出了一個論斷：Zeta函數的零點都在直線Res(s) = 1/2上。他在作了一番努力而未能證明後便放棄了，因為這對他證明素數定理影響不大。但這一問題至今仍然未能解決，甚至於比此假設簡單的猜想也未能獲證。而函數論和解析數論中的很多問題都依賴於黎曼假設。在代數數論中的廣義黎曼假設更是影響深遠。若能證明黎曼假設，則可帶動許多問題的解決。
孿生質數
1849年，波林那克提出孿生質數猜想（the conjecture of twin primes），即猜測存在無窮多對孿生質數。猜想中的「孿生」是指一對質數，它們之間相差2。例如3和5，5和7，11和13，10,016,957和10,016,959等等都是孿生質數。
例如3和5 ，5和7，11和13，…，10016957和10016959等等都是孿生質數。孿生質數有一個十分精確的普遍公式，是根據一個定理：「若自然數Q與Q+2都不能被不大於根號Q+2的任何質數整除，則Q與Q+2是一對質數，稱為相差2的孿生質數。這一句話可以用公式表達：Q=p1m1+a1=p2m2+a2=....=pkmk+ak其中p1，p2，...，pk表示順序質數2，3，5，....。an≠0，an≠pn-2。若Q<P(k+1)的平方減2，則Q與Q+2是一對孿生質數。 所以，只要按着公式計算，理論上有無數個孿生質數。
英國數學家戈弗雷·哈代和約翰·李特爾伍德曾提出一個「強孿生素數猜想」。這一猜想不僅提出孿生素數有無窮多對，而且還給出其漸近分布形式。2013年5月，華人數學家張益唐在孿生素數研究方面所取得的突破性進展，他證明了孿生素數猜想的一個弱化形式。在最新研究中，張益唐在不依賴未經證明推論的前提下，發現存在無窮多個之差小於7000萬的素數對，從而在孿生素數猜想這個重要問題的道路上前進了一大步。
梅森質數
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]
應用領域
質數被利用在密碼學上，所謂的公鑰就是將想要傳遞的信息在編碼時加入質數，編碼之後傳送給收信人，任何人收到此信息後，若沒有此收信人所擁有的密鑰，則解密的過程中（實為尋找素數的過程），將會因為找質數的過程（分解質因數）過久，使即使取得信息也會無意義。
在汽車的設計上，相鄰的兩個大小齒輪齒數最好設計成質數，以增加兩齒輪內兩個相同的齒相遇嚙合次數的最小公倍數，可增強耐用度減少故障。
在害蟲的生物生長周期與殺蟲劑使用之間的關係上，殺蟲劑的質數次數的使用也得到了證明。實驗表明，質數次數地使用殺蟲劑是最合理的：都是使用在害蟲繁殖的高潮期，而且害蟲很難產生抗藥性。
以質數形式無規律變化的導彈和魚雷可以使敵人不易攔截。
多數生物的生命周期也是質數（單位為年），這樣可以最大程度地減少碰見天敵的機會。