質數

維基百科,自由的百科全書
前往: 導覽搜尋
各種各樣的
基本

\mathbb{N}\subseteq\mathbb{Z}\subseteq\mathbb{Q}\subseteq\mathbb{R}\subseteq\mathbb{C}

正數 \begin{smallmatrix} \mathbb{R}^+ \end{smallmatrix}
自然數 \begin{smallmatrix} \mathbb{N} \end{smallmatrix}
正整數 \begin{smallmatrix} \mathbb{Z}^+ \end{smallmatrix}
小數
有限小數
無限小數
循環小數
有理數 \begin{smallmatrix} \mathbb{Q} \end{smallmatrix}
代數數 \begin{smallmatrix} \mathbb{A} \end{smallmatrix}
實數 \begin{smallmatrix} \mathbb{R} \end{smallmatrix}
複數 \begin{smallmatrix} \mathbb{C} \end{smallmatrix}
高斯整數 \begin{smallmatrix} \mathbb{Z}[i] \end{smallmatrix}

負數 \begin{smallmatrix} \mathbb{R}^- \end{smallmatrix}
整數 \begin{smallmatrix} \mathbb{Z} \end{smallmatrix}
負整數 \begin{smallmatrix} \mathbb{Z}^- \end{smallmatrix}
分數
單位分數
二進分數
規矩數
無理數
超越數
虛數
二次無理數
艾森斯坦整數 \begin{smallmatrix} \mathbb{Z}[\omega] \end{smallmatrix}

延伸

雙複數
四元數 \begin{smallmatrix} \mathbb{H} \end{smallmatrix}
共四元數
八元數 \begin{smallmatrix} \mathbb{O} \end{smallmatrix}
超數
上超實數

超複數
十六元數 \begin{smallmatrix} \mathbb{S} \end{smallmatrix}
複四元數
大實數
超實數 \begin{smallmatrix} {}^\star\mathbb{R} \end{smallmatrix}
超現實數

其他

對偶數
雙曲複數
序數
質數
同餘
可計算數
艾禮富數

公稱值
超限數
基數
P進數
規矩數
整數數列
數學常數

圓周率 \begin{smallmatrix} \pi \end{smallmatrix}
 = 3.141592653…
自然對數的底 \begin{smallmatrix} e \end{smallmatrix}
 = 2.718281828…
虛數單位 \begin{smallmatrix} i \end{smallmatrix}
 = \begin{smallmatrix} +\sqrt{-1} \end{smallmatrix}
無窮大 \begin{smallmatrix} \infty \end{smallmatrix}

質數,又稱素數,指在大於1的自然數中,除了1和此整數自身外,無法被其他自然數整除的數(也可定義為只有1和本身兩個因數的數)。

比1大但不是質數的數稱為合數。1和0既非質數也非合數。質數在數論中有著非常重要的地位。

關於質數[編輯]

最小的質數是2,也是質數中唯一的偶數;其他質數都是奇數。質數有無限多個,所以不存在最大的質數。

圍繞著質數存在很多問題、猜想和定理。著名的有「孿生質數猜想」和「哥德巴赫猜想」。

質數序列的開頭是這樣的OEISA000040

23571113171923293137
414347535961677173798389
97101103107109113127131137139149151

質數集合有時表示成粗體\mathbb{P}

抽象代數的一個分支-環論中,素元素有特殊的含義,在這個含義下,任何質數的加法的逆轉也是質數。換句話說,將整數Z的集合看成是一個,-Z是一個素元素。但是在數學領域內,提到質數時通常指「正的質數」。

算術基本定理證明每個大於1的正整數都可以寫成質數的乘積,並且這種乘積的形式是唯一的。因此,質數也被稱為自然數的「建築的基石」。例如:

23244 = 2^2 \times 3 \times 13 \times 149

關於分解的詳細方法,可見於整數分解條目。

這個定理的重要一點是,將1排斥在質數集合以外。如果1被認為是質數,那麼這些嚴格的闡述就不得不加上一些限制條件。

0,由於可以被任何數整除(合數)(因餘數一定等於0),所以它不符合質數的定義。

質數的數目[編輯]

質數無窮性的證明[編輯]

質數有無窮多個。現在已知最早的證明方法是歐幾里得在他的《幾何原本》中提出的,該證明方法如下:

  • 假設只有有限個質數p_1,p_2,p_3\ldots p_n。令N=p_1\times p_2\times p_3\times \ldots \times p_n。那麼,N+1是質數或者不是質數。
  • 如果N+1為質數,則N+1要大於p_1,p_2,p_3\ldots p_n,所以它不在那些假設的質數集合中。
  • 如果N+1為合數,因為任何一個合數都可以分解為幾個質數的積;而N和N+1的最大公因數是1,所以N+1不可能被p_1,p_2,p_3\ldots p_n整除,所以該合數分解得到的質因數肯定不在假設的質數集合中。
  • 因此無論該數是質數還是合數,都意味著在假設的有限個質數之外還存在著其他質數。
  • 對任何有限個質數的集合來說,用上述的方法永遠可以得到有一個質數不在假設的質數集合中的結論。
  • 所以原先的假設不成立。也就是說,質數有無窮多個。

其他數學家也給出了他們自己的證明。歐拉利用黎曼ζ函數證明了全部質數的倒數之和是發散的,恩斯特·庫默爾的證明更為簡潔,Hillel Furstenberg英語Hillel Furstenberg則用拓撲學加以證明Furstenberg's proof of the infinitude of primes英語Furstenberg's proof of the infinitude of primes

對於一定範圍內的質數數目的計算[編輯]

儘管整個質數是無窮的,仍然有人會問「100000以下有多少個質數?」,「一個隨機的100位數多大可能是質數?」。質數定理可以回答此問題。

尋找質數[編輯]

尋找在給定限度內的質數排列,埃拉托斯特尼篩法是個很好的方法。然而在實際中,我們往往是想知道一個給定數是否是質數,而不是生成一個質數排列。進而,知道是質數的機率有多大就是可以了。用質性測試迅速地檢查一個給定數(例如,有幾千位數的長度)是否是質數是可能的。典型的方法是隨機選取一個數,然後圍繞著這個數和可能的質數N檢查一些方程式。重複這個過程幾次後,它可以基本確定這個數是明顯的合數或者可能是質數。這種方法是不完美的:對某些測試而言,例如費馬測試,不論選取了多少隨機數都有可能將一些合數判斷成可能的質數,這就引出了偽質數。而像米勒-拉賓測試,雖然只要選取夠多的數字來檢驗方程式,就可以保證其檢驗出的質數性是正確的;但這個檢驗的數量太過龐大,甚至比試除法所需的\sqrt{N}還要多,在有限的時間內只能知道答案正確的機率很高,不能保證一定正確。

數學家一直努力找尋產生質數的公式,利用一條定理,可以正確產生所有的質數(參見質數判定法則質數公式)。歷史上有許多試驗的例子:17世紀初法國數學家梅森(Mersenne)在他的一個著作當中討論了這樣一種我們現在稱之為梅森質數的質數,Mp=2^p-1,本來以為只要p是一個質數,n=2^{p}-1就會是一個質數,這在p=3p=5p=7都是正確的,但是p=112^{11}-1=2047=23\times 89就不是質數了。目前最大的已知質數是2^{57885161}-1(此數字位長度是17 425 170),它是在2013年1月25日由GIMPS發現。這組織也在2008年8月23日發現了目前所知第二大的已知質數2^{43112609}-1(此數字位長度是12 978 189)。

質數演算法[編輯]

  • 欲求出小於x的質數個數,參見「質數公式」。

檢驗質數[編輯]

檢查一個正整數N是否為質數,最簡單的方法就是試除法,將該數N用小於等於\sqrt{N}的所有質數去試除,若均無法整除,則N為質數,參見質數判定法則

2002年,印度人M. Agrawal、N. Kayal以及N. Saxena提出了AKS質數測試演算法,證明了可以在多項式時間內檢驗是否為質數。

已經證明的定理[編輯]

  • 在一個大於1的數a和它的2倍之間(即區間(a, 2a]中)必存在一個質數。
  • 存在任意長度的質數等差數列。(格林和陶哲軒,2004年)
  • 一個偶數可以寫成兩個數字之和,其中每一個數字都最多祇有9個質因數。(挪威數學家布朗,1920年)
  • 一個偶數必定可以寫成一個質數p加上一個合成數c,其中c的因子個數有上界。(瑞尼,1948年)
  • 一個偶數必定可以寫成一個質數加上一個最多由5個因子所組成的合成數。後來,有人簡稱這結果為 (1 + 5) (中國潘承洞,1968年)
  • 一個充分大偶數必定可以寫成一個質數加上一個最多由2個質因子所組成的合成數。簡稱為 (1 + 2) (中國陳景潤)

未解之謎[編輯]

質數的應用[編輯]

質數近來被利用在密碼學上,所謂的公鑰就是將想要傳遞的信息在編碼時加入質數,編碼之後傳送給收信人,任何人收到此信息後,若沒有此收信人所擁有的密鑰,則解密的過程中(實為尋找質數的過程),將會因為找質數的過程(分解質因數)過久,使即使取得信息也會無意義。

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

在害蟲的生物生長周期與殺蟲劑使用之間的關係上,殺蟲劑的質數次數的使用也得到了證明。實驗表明,質數次數地使用殺蟲劑是最合理的:都是使用在害蟲繁殖的高潮期,而且害蟲很難産生抗藥性。

以質數形式無規律變化的飛彈和魚雷可以使敵人不易攔截。

高斯質數[編輯]

高斯質數是把質數在\mathbb{Z}[i]內的擴展。高斯質數是不能非平凡地表示為兩個複整數的乘積的複整數,例如1+2i

型如4k+1的質數是\mathbb{Z}中的質數,但不是\mathbb{Z}[i]中的質數,例如13=(3-2i)(3+2i)

參見[編輯]

外部連結[編輯]


腳注[編輯]

Wikibooks-logo.svg
您可以在維基教科書中查找此百科條目的相關電子教程:
Wikibooks-logo.svg
您可以在維基教科書中查找此百科條目的相關電子教程:
Wikibooks-logo.svg
您可以在維基教科書中查找此百科條目的相關電子教程: