素数

跳过字词转换说明

數學的數

基本

$\mathbb{N}\sub\mathbb{Z}\sub\mathbb{Q}\sub\mathbb{R}\sub\mathbb{C}$ 自然數 $\mathbb{N}$ 整數 $\mathbb{Z}$ 二进分数 有限小数 循环小数 有理數 $\mathbb{Q}$ 高斯整数 $\mathbb{Z}[i]$ 代數數 $\mathbb{A}$ 實數 $\mathbb{R}$ 複數 $\mathbb{C}$ 負數 分数 单位分数 无限小数 规矩数 無理數 超越數 二次无理数 虛數 艾森斯坦整数 $\mathbb{Z}[\omega]$

延伸

雙複數 四元數 $\mathbb{H}$ 共四元數 八元數 $\mathbb{O}$ 超數 上超實數 超現實數 超複數 十六元數 $\mathbb{S}$ 複四元數 Tessarine 大實數 超實數 ${}^\star\mathbb{R}$

其他

对偶数 雙曲複數 序數 質數 同餘 可計算數 阿列夫数 公稱值 超限數 基數 P進數 規矩數 整數序列 數學常數 圓周率 π = 3.141592653… 自然對數的底 e = 2.718281828… 虛數單位 i = $+\sqrt{-1}$ 無窮大量 ∞

质数，又稱素数，指在一個大於1的自然数中，除了1和此整数自身外，無法被其他自然数整除的数（也可定義為只有1和本身两个因数的数）。

比1大但不是素数的数称为合数。1和0既非素数也非合数。素数在数论中有着很重要的地位。

關於素数

最小的素数是2，也是素数中唯一的偶数（雙数）；其他素数都是奇数（單数）。質数有無限多個，所以不存在最大的質数。

围绕著素数存在很多问题、猜想和定理。著名的有孪生素数猜想和哥德巴赫猜想。

素数序列的开头是这样的：

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 (OEIS:A000040)

素数集合有时表示成粗体$\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則用拓撲學加以了證明。

对于一定范围内的素数数目的计算

尽管整个素数是无穷的，仍然有人会问“100000以下有多少个素数?”，“一个随机的100位数多大可能是素数?”。素数定理可以回答此问题。

寻找素数

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

数學家一直努力找尋產生質数的公式，利用一條定理，可以正確產生所有的質数（參見素数判定法则和質数公式）。歷史上有許多試驗的例子：17世紀初法國数學家梅森（Mersenne）在他的一個著作當中討論了這樣一種我們現在稱之為梅森質数的質数，M_p=2^p − 1，本來以為只要p是一個質数，n = 2^p − 1就會是一個質数，這在p = 3，p = 5，p = 7都是正確的，但是p = 11時$2^{11}-1=2047=23\times 89$就不是質数了。目前最大的已知質数是梅森質数2^43112609 − 1（此数字位長度是12978189），它是在2008年8月23日由GIMPS發現。這組織也在2008年9月6日發現了目前所知第二大的已知質数2^37156667 − 1（此数字位長度是11185272）。

素数算法

• 欲求出小於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) (中國陈景润)

未解之谜

• 哥德巴赫猜想：是否每個大於2的偶数都可寫成兩個素数之和？
• 孪生素数猜想：孪生素数就是差为2的素数对，例如11和13。是否存在无穷多的孪生素数？
• 斐波那契数列内是否存在无穷多的素数？
• 是否存在无穷多的梅森素数？
• 在n²与(n + 1)²之间是否每隔n就有一个素数？
• 是否存在无穷个形式如X²+1素数？
• 黎曼猜想

素数的应用

素数近来被利用在密码学上，所谓的公钥就是将想要传递的信息在编码时加入素数，编码之后传送给收信人，任何人收到此信息后，若没有此收信人所拥有的密钥，则解密的过程中（实为寻找素数的过程），将会因为找素数的过程（分解质因数）过久，使即使取得信息也會無意義。

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

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

以素数形式无规律变化的导弹和鱼雷可以使敌人不易拦截。

高斯素数

高斯素数是把素数在$\mathbb{Z}[i]$内的扩展。高斯素数是不能非平凡地表示为两个複整數的乘积的複整數，例如1+2i。

型如4k + 1的素数是$\mathbb{Z}$中的素数，但不是$\mathbb{Z}[i]$中的素数，例如13=(3-2i)(3+2i)。

参见

• 素数列表
• 幸运数
  • 幸运素数
• 素数判定法则
• 埃拉托斯特尼筛法
• 孪生素数
• 三胞胎素数
  • PrimeGrid — 隶属于BOINC平台的一个寻找质数的项目
  • GIMPS — 寻找梅森素数的项目

外部連結

• Determinación geométrica de los números primo
• 素数发生器和校验器