素数

维基百科，自由的百科全书

素數，又称質數，一個大於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是一个素元素。不管怎样，数学领域内，提到素数通常是指正素数。

算术基本定理說明每个正整数都可以写成素数的乘积，因此素数也被称为自然数的“建筑的基石”例如：

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

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

这个定理的重要一点是，将1排斥在素数集合以外。如果1被认为是素数，那么这些严格的阐述就不得不加上一些限制条件了。

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

[编辑] 素数的數目

素数是无穷多的，对这个论断，现在所已知的最古老的检验方法是欧几里德在他的几何原本中提出来的。他的检验方法可以简单地总结如下：

取有限个数的素数，因为要做自变量我们假设全部的素数都存在，将这些素数相乘然后加1，得到的数是不会被这些素数中的任何一个整除的，因为无论除哪个总会余1。因此这个数要么本身就是个素数，要么存在不在这个有限集合内的约数。因此我们开始用的集合不包含所有的素数。

别的数学家也给出了他们自己的证明。歐拉證明了全部素数的倒数和发散到无穷的。恩斯特·库默的证明尤其简洁，Furstenberg用一般拓扑证明。

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

[编辑] 寻找素数

寻找在给定限度内的素数排列，埃拉托斯特尼筛法法是个很好的方法。然而在实际中，我们往往是想知道一个给定数是否是素数，而不是生成一个素数排列。进而，知道答案是很高的概率就是已经很满意的了，用素性测试迅速地检查一个给定数（例如，有几千位数的长度）是否是素数是可能的。典型的方法是随机选取一个数，然后围绕着这个数和可能的素数N检查一些方程式。重複這個過程幾次後，它宣布这个数是明显的合数或者可能是素数。这种方法是不完美的：對某些测试而言，例如費馬測試，不论选取了多少随机数都有可能将一些合数判断成可能的素数，这就引出了另一种数伪素数。而像米勒-拉賓測試，雖然只要選取夠多數字來檢驗方程式，就可以保證其檢驗出的質數性是正確的，但這個保證門檻的數量太過龐大，甚至比試除法所需的 $\sqrt{N}$ 還要多，在有限時間內運行起來只能知道答案正確的機率很高，不能保證一定正確。

目前最大的已知素数是 $230402457 - 1$ （此数字位长度是 $9,152,052$ ），它是在2005年 12月15日由GIMPS发现。这组织也在2005年 2月18日发现了目前所知第二大的已知素数 $225964951 - 1$ （此数字位长度是 $7,816,230$ ）。

数学家一直努力找寻产生素数的公式，但截至目前为止，并没有一个基本函数或是多项式可以正确产生所有的素数。历史上有许多试验的例子：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$ 就不是素数了。