素数

质数，又称素数，指在大于1的自然数中，除了$1$和该数自身外，无法被其他自然数整除的数（也可定义为只有1与该数本身两个正因数的数）。大于1的自然数若不是素数，则称之为合数（也称为合成数）。例如，5是个素数，因为其正约数只有1与5。7是个素数，因为其正约数只有1与7。而4则是个合数，因为除了1与4外，2也是其正约数。6也是个合数，因为除了1与6外，2与3也是其正约数。算术基本定理确立了素数于数论里的核心地位：任何大于1的整数均可被表示成一串唯一素数之乘积。为了确保该定理的唯一性，1被定义为不是素数，因为在因式分解中可以有任意多个1（如3、$1\times 3$、$1\times 1\times 3$等都是3的有效约数分解）。

古希腊数学家欧几里得于公元前300年前后证明有无限多个素数存在（欧几里得定理）。现时人们已发现多种验证素数的方法。其中试除法比较简单，但需时较长：设被测试的自然数为$n$，使用此方法者需逐一测试2与${\sqrt {n}}$之间的素数，确保它们无一能整除$n$。对于较大或一些具特别形式（如梅森数）的自然数，人们通常使用较有效率的算法测试其是否为素数（例如2^82589933-1是直至2024年4月为止已知最大的梅森素数，也是直至2024年4月为止已知最大的素数）。虽然人们仍未发现可以完全区别素数与合数的公式，甚至研究素数分布时相当有力的筛法也会碰到奇偶性问题（也就是多种筛法都无法区别素数跟两个素数相乘的合数的问题），但已建构了素数的分布模式（亦即素数在大数时的统计模式）。19世纪晚期得到证明的素数定理指出：一个任意自然数n为素数的概率反比于其数位（或$n$的对数）。

许多有关素数的问题依然未解，如哥德巴赫猜想（每个大于2的偶数可表示成两个素数之和）及孪生素数猜想（存在无穷多对相差2的素数）。这些问题促进了数论各个分支的发展，主要在于数字的解析或代数方面。素数被用于信息科技里的几个程序中，如公钥加密利用了难以将大数分解成其素因数之类的性质。素数亦在其他数学领域里形成了各种广义化的素数概念，主要出现在代数里，如素元及素理想。

定义和例子

一个自然数（如1、2、3、4、5、6等）若恰有两个正约数（1及此数本身），则称之为素数。大于1的自然数若不是素数，则称之为合数。

数字12不是素数，因为将12以每4个分成1组，恰可分成3组（也有其他分法）。11则无法分成数量都大于1且都相同的各组，而都会有剩余。因此，11为素数。

在数字1至6间，数字2、3与5为素数，1、4与6则不是素数。1不是素数，其理由见下文。2是素数，因为只有1与2可整除该数。接下来，3亦为素数，因为1与3可整除3，3除以2会余1。因此，3为素数。不过，4是合数，因为2是另一个（除1与4外）可整除4的数：

4 = 2 · 2

5又是个素数：数字2、3与4均不能整除5。接下来，6会被2或3整除，因为

6 = 2 · 3

因此，6不是素数。右图显示12不是素数：12 = 3 · 4。不存在大于2的偶数为素数，因为依据定义，任何此类数字$n$均至少有三个不同的约数，即1、2与$n$。这意指$n$不是素数。因此，“奇素数”系指任何大于2的素数。类似地，当使用一般的十进位制时，所有大于5的素数，其尾数均为1、3、7或9，因为尾数0、2、4、6、8为2的倍数，尾数为0或5的数字为5的倍数。

若$n$为一自然数，则1与$n$会整除$n$。因此，素数的条件可重新叙述为：一个数字为素数，若该数大于1，且没有

$2,3,\ldots ,n-1$

会整除$n$。另一种叙述方式为：一数$n>1$为素数，若不能写成两个整数$a$与$b$的乘积，其中这两数均大于1：

$n=a\cdot b$.

换句话说，$n$为素数，若$n$无法分成数量都大于1且都相同的各组。

由所有素数组成之集合通常标记为P或$\mathbb {P}$。

前168个素数（所有小于1000的素数）为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, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, ...（OEIS数列A000040）。

算术基本定理

主条目：算术基本定理

素数对于数论与一般数学的重要性来自于“算术基本定理”。该定理指出，每个大于1的整数均可写成一个以上的素数之乘积，且除了质约数的排序不同外是唯一的。素数可被认为是自然数的“基本建材”，例如：

23244	= 2 · 2 · 3 · 13 · 149
	= 22 · 3 · 13 · 149. （22表示2的平方或2次方。）

如同此例一般，相同的约数可能出现多次。一个数n的分解：

$n=p_{1}\cdot p_{2}\cdot \ldots \cdot p_{t}$

成（有限多个）素因数$p_{1}$、$p_{2}$、……、$p_{t}$，称之为$n$的“约数分解”。算术基本定理可以重新叙述为，任一素数分解除了约数的排序外，都是唯一的。因此，尽管实务上存在许多素数分解算法来分解较大的数字，但最后都会得到相同的结果。

若$p$为素数，且$p$可整除整数的乘积$ab$，则$p$可整除$a$或可整除$b$。此一命题被称为欧几里得引理，被用来证明素数分解的唯一性。

1是否为素数

最早期的希腊人甚至不将1视为是一个数字，因此不会认为1是素数。到了中世纪与文艺复兴时期，许多数学家将1纳入作为第一个素数。到18世纪中期，克里斯蒂安·哥德巴赫在他与李昂哈德·欧拉著名的通信里将1列为第一个素数，但欧拉不同意。然而，到了19世纪，仍有许多数学家认为数字1是个素数。例如，德里克·诺曼·雷默（Derrick Norman Lehmer）在他那最大达10,006,721的素数列表中，将1列为第1个素数。昂利·勒贝格据说是最后一个称1为素数的职业数学家。到了20世纪初，数学家开始认为1不是个素数，但反而作为“单位”此一特殊类别。

许多数学成果在称1为素数时，仍将有效，但欧几里何的算术基本定理（如上所述）则无法不重新叙述而仍然成立。例如，数字15可分解成3 · 5及 1 · 3 · 5；若1被允许为一个素数，则这两个表示法将会被认为是将15分解至素数的不同方法，使得此一定理的陈述必须被修正。同样地，若将1视为素数，埃拉托斯特尼筛法将无法正常运作：若将1视为素数，此一筛法将会排除掉所有1的倍数（即所有其他的数），只留下数字1。此外，素数有几个1所没有的性质，如欧拉函数的对应值，以及除数函数的总和。

历史

埃拉托斯特尼筛法是个找出在一特定整数以下的所有素数之简单算法，由古希腊数学家埃拉托斯特尼于公元前3世纪发明。

在古埃及人的幸存纪录中，有迹象显示他们对素数已有部分认识：例如，在莱因德数学纸草书中的古埃及分数展开时，对素数与对合数有着完全不同的类型。不过，对素数有过具体研究的最早幸存纪录来自古希腊。公元前300年左右的《几何原本》包含与素数有关的重要定理，如有无限多个素数，以及算术基本定理。欧几里得亦展示如何从梅森素数建构出完全数。埃拉托斯特尼提出的埃拉托斯特尼筛法是用来计算素数的一个简单方法，虽然今天使用电脑发现的大素数无法使用这个方法找出。

希腊之后，到17世纪之前，素数的研究少有进展。1640年，皮埃尔·德·费马叙述了费马小定理（之后才被莱布尼茨与欧拉证明）。费马亦推测，所有具$2^{2^{n}}+1$形式的数均为素数（称之为费马数），并验证至$n=4$（即2¹⁶ + 1）不过，后来由欧拉发现，下一个费马数2³² + 1即为合数，且实际上其他已知的费马数都不是素数。法国修道士马兰·梅森发现有的素数具$2^{p}-1$的形式，其中$p$为素数。为纪念他的贡献，此类素数后来被称为梅森素数。

欧拉在数论中的成果，许多与素数有关。他证明无穷级数${\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{5}}+{\frac {1}{7}}+{\frac {1}{11}}+\ldots$会发散。1747年，欧拉证明每个偶完全数都确实为$2^{p-1}(2^{p}-1)$的形式，其中第二个约数为梅森素数。

19世纪初，勒让德与高斯独立推测，当$x$趋向无限大时，小于$x$的素数数量会趋近于${\frac {x}{\ln x}}$，其中$\ln x$为$x$的自然对数。黎曼于1859年有关ζ函数的论文中勾勒出一个程式，导出了素数定理的证明。其大纲由雅克·阿达马与夏尔-让·德拉瓦莱·普桑所完成，他们于1896年独立证明出素数定理。

证明一个大数是否为素数通常无法由试除法来达成。许多数学家已研究过大数的素性测试，通常局限于特定的数字形式。其中包括费马数的贝潘测试（1877年）、普罗丝定理（约1878年）、卢卡斯-莱默素数判定法（1856年起）及广义卢卡斯素性测试。较近期的算法，如APRT-CL、ECPP及AKS等，均可作用于任意数字上，但仍慢上许多。

长期以来，素数被认为在纯数学以外的地方只有极少数的应用。到了1970年代，发明公共密钥加密这个概念之后，情况改变了，素数变成了RSA加密算法等一阶算法之基础。

自1951年以来，所有已知最大的素数都由电脑所发现。对更大素数的搜寻已在数学界以外的地方产生出兴趣。互联网梅森素数大搜索及其他用来寻找大素数的分散式运算计划变得流行，在数学家仍持续与素数理论奋斗的同时。

素数的数目

主条目：欧几里得定理

存在无限多个素数。另一种说法为，素数序列

2, 3, 5, 7, 11, 13, ...

永远不会结束。此一陈述被称为“欧几里得定理”，以古希腊数学家欧几里得为名，因为他提出了该陈述的第一个证明。已知存在其他更多的证明，包括欧拉的分析证明、哥德巴赫依据费马数的证明、弗斯滕伯格使用一般拓扑学的证明，以及库默尔优雅的证明。

欧几里得的证明

欧几里得的证明取任一个由素数所组成的有限集合$S$。该证明的关键想法为考虑$S$内所有素数相乘后加一的一个数字：

$N=1+\prod _{p\in S}p$。

如同其他自然数一般，$N$可被至少一个素数整除（即使N本身为素数亦同）。

任何可整除N的素数都不可能是有限集合$S$内的元素（素数），因为后者除N都会余1。所以，$N$可被其他素数所整除。因此，任一个由素数所组成的有限集合，都可以扩展为更大个由素数所组成之集合。

这个证明通常会被错误地描述为，欧几里得一开始假定一个包含所有素数的集合，并导致矛盾；或者是，该集合恰好包含n个最小的素数，而不任意个由素数所组成之集合。今日，$n$个最小素数相乘后加一的一个数字，被称为第$n$个欧几里得数。

欧拉的解析证明

欧拉的证明使用到素数倒数的总和

$S(p)={\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{5}}+{\frac {1}{7}}+\cdots +{\frac {1}{p}}$。

当$p$够大时，该和会大于任意实数。这可证明，存在无限多个素数，否则该和将只会增长至达到最大素数$p$为止。$S(p)$的增加率可使用梅滕斯第二定理来量化。比较总和

${\frac {1}{1^{2}}}+{\frac {1}{2^{2}}}+{\frac {1}{3^{2}}}+\cdots +{\frac {1}{n^{2}}}=\sum _{i=1}^{n}{\frac {1}{i^{2}}}$

当$n$趋向无限大时，此和不会变成无限大（见巴塞尔问题）。这意味着，素数比自然数的平方更常出现。布朗定理指出，孪生素数倒数的总和

$\left({{\frac {1}{3}}+{\frac {1}{5}}}\right)+\left({{\frac {1}{5}}+{\frac {1}{7}}}\right)+\left({{\frac {1}{11}}+{\frac {1}{13}}}\right)+\cdots =\sum \limits _{\begin{smallmatrix}p{\text{ prime, }}\\p+2{\text{ prime}}\end{smallmatrix}}{\left({{\frac {1}{p}}+{\frac {1}{p+2}}}\right)},$

是有限的。

测试素数与整数分解

确认一个数$n$是否为素数有许多种方法。最基本的程序为试除法，但因为速率很慢，没有什么实际用处。有一类现代的素性测试可适用于任意数字之上，另有一类更有效率的测试方法，则只能适用于特定的数字之上。大多数此类方法只能辨别$n$是否为素数。也能给出$n$的一个（或全部）素因数之程序称之为约数分解算法。

试除法

主条目：试除法

测试$n$是否为素数的最基本方法为试除法。此一程序将n除以每个大于1且小于等于$n$的平方根之整数$m$。若存在一个相除为整数的结果，则$n$不是素数；反之则是个素数。实际上，若$n=ab$是个合数（其中$a$与$b\neq 1$），则其中一个约数$a$或$b$必定至大为${\sqrt {n}}$。例如，对$n=37$使用试除法，将37除以$m=2,3,4,5,6$，没有一个数能整除37，因此37为素数。此一程序若能知道直至${\sqrt {n}}$的所有素数列表，则可以只检查$m$为素数的状况，以提升效率。例如，为检查37是否为素数，只有3个相除是必要的（$m=2,3,5$），因为4与6为合数。

作为一个简单的方法，试除法在测试大整数时很快地会变得不切实际，因为可能的约数数量会随着n的增加而迅速增加。依据下文所述之素数定理，小于${\sqrt {n}}$的素数之数量约为${\frac {\sqrt {n}}{\ln {\sqrt {n}}}}$，因此使用试除法测试$n$是否为素数时，大约会需要用到这么多的数字。对$n=10^{20}$，此一数值约为4.5亿，对许多实际应用而言都太过庞大。

筛法

一个能给出某个数值以下的所有素数之算法，称之为素数筛法，可用于只使用素数的试除法内。最古老的一个例子为埃拉托斯特尼筛法（见上文），至今仍最常被使用。阿特金筛法为另外一例。在电脑出现之前，筛法曾被用来给出10⁷以下的素数列表。

素性测试与素数证明

主条目：素性测试

现代测试一般的数字$n$是否为素数的方法可分成两个主要类型，随机（或“蒙特卡洛”）与确定性算法。确定性算法可肯定辨别一个数字是否为素数。例如，试除法即是个确定性算法，因为若正确执行，该方法总是可以辨别一个素数为素数，一个合数为合数。随机算法一般比较快，但无法完全证明一个数是否为素数。这类测试依靠部分随机的方法来测试一个给定的数字。例如，一测试在应用于素数时总是会通过，但在应用于合数时通过的概率为$p$。若重复这个测试$n$次，且每次都通过，则该数为合数的概率为${\frac {1}{(1-p)^{n}}}$，会随着测试次数呈指数下滑，因此可越来越确信（虽然总是无法完全确信）该数为素数。另一方面，若测试曾失败过，则可知该数为合数。

随机测试的一个特别简单的例子为费马素数判定法，使用到对任何整数$a$，$n^{p}\equiv n(\mod p)$，其中$p$为素数的这个事实（费马小定理）。若想要测试一个数字$b$是否为素数，则可随机选择$n$来计算$n^{b}(\mod b)$的值。这个测试的缺点在于，有些合数（卡迈克尔数）即使不是素数，也会符合费马恒等式，因此这个测试无法辨别素数与卡迈克尔数，最小的三个卡迈克尔数为561，1105，1729。卡迈克尔数比素数还少上许多，所以这个测试在实际应用上还是有用的。费马素数判定法更强大的延伸方法，包括贝利-PSW、米勒-拉宾与Solovay-Strassen素性测试，都保证至少在应用于合数时，有部分时候会失败。

确定性算法不会将合数错误判定为素数。在实务上，最快的此类方法为椭圆曲线素数证明。其运算时间是透过实务分析出来的，不像最新的AKS素性测试，有已被严格证明出来的复杂度。确定性算法通常较随机算法来得慢，所以一般会先使用随机算法，再采用较费时的确定性算法。

下面表格列出一些素性测试。运算时间以被测试的数字$n$来表示，并对随机算法，以$k$表示其测试次数。此外，$\varepsilon$是指一任意小的正数，$\log$是指一无特定基数的对数。大O符号表示，像是在椭圆曲线素数证明里，所需之运算时间最长为一常数（与n无关，但会与ε有关）乘于log^5+ε(n)。

测试	发明于	类型	运算时间	注记
AKS素性测试	2002	确定性	$O(\log ^{6+\varepsilon }(n))$
椭圆曲线素数证明	1977	确定性	$O(\log ^{5+\varepsilon }(n))$“实务分析”
贝利-PSW素性测试	1980	随机	$O(\log ^{3}n)$	无已知反例
米勒-拉宾素数判定法	1980	随机	$O(k\cdot \log ^{2+\varepsilon }(n))$	错误概率$4^{-k}$
Solovay-Strassen素数	1977	随机	$O(k\cdot \log ^{3}n)$	错误概率$2^{-k}$
费马素数判定法		随机	$O(k\cdot \log ^{2+\varepsilon }(n))$	遇到卡迈克尔数时会失败

专用目的算法与最大已知素数

更多信息：素数列表

建构正五边形。5是个费马素数。

除了前述可应用于任何自然数n之上的测试外，一些更有效率的素性测试适用于特定数字之上。例如，卢卡斯素性测试需要知道n − 1的素因数，而卢卡斯-莱默素性测试则需要以n + 1的素因数作为输入。例如，这些测试可应用在检查

n! ± 1 = 1 · 2 · 3 · ... · n ± 1

是否为一素数。此类形式的素数称之为阶乘素数。其他具p+1或p-1之类形式的素数还包括索菲·热尔曼素数（具2p+1形式的素数，其中p为素数）、素数阶乘素数、费马素数与梅森素数（具2^p − 1形式的素数，其中p为素数）。卢卡斯-雷默素性测试对这类形式的数特别地快。这也是为何自电脑出现以来，最大已知素数总会是梅森素数的原因。

费马素数具下列形式

F_k = 2^2k + 1,

其中，k为任意自然数。费马素数以皮埃尔·德·费马为名，他猜想此类数字F_k均为素数。费马认为F_k均为素数的理由为此串列的前5个数字（3、5、17、257及65537）为素数。不过，F₅却为合数，且直至2015年发现的其他费马数字也全都是合数。一个正n边形可用尺规作图，当且仅当

n = 2ⁱ · m

其中，m为任意个不同费马素数之乘积，及i为任一自然数，包括0。

下列表格给出各种形式的最大已知素数。有些素数使用分散式计算找到。2009年，互联网梅森素数大搜索因为第一个发现具至少1,000万个数位的素数，而获得10万美元的奖金。电子前哨基金会亦为具至少1亿个数位及10亿个数位的素数分别提供15万美元及25万美元的奖金。

类型	素数	数位	日期	发现者
梅森素数	282589933 − 1	23,249,425	2018年12月21日	互联网梅森素数大搜索
非梅森素数（普罗斯数）	19,249×213,018,586 + 1	3,918,990	2007年3月26日	十七或者破产
阶乘素数	150209! + 1	712,355	2011年10月	PrimeGrid
素数阶乘素数	1098133# - 1	476,311	2012年3月	PrimeGrid
孪生素数s	3756801695685×2666669 ± 1	200,700	2011年12月	PrimeGrid

整数分解

主条目：整数分解

给定一合数n，给出一个（或全部）素因数的工作称之为n的约数分解。椭圆曲线分解是一个依靠椭圆曲线上的运算来分解素因数的算法。

素数分布

1975年，数论学家唐·察吉尔评论素数

像生长于自然数间的杂草，似乎不服从概率之外的法则，（但又）表现出惊人的规律性，并有规范其行为之法则，且以军事化的精准度遵守着这些法则。

大素数的分布，如在一给定数值以下有多少素数这个问题，可由素数定理所描述；但有效描述第n个素数的公式则仍未找到。

存在任意长的连续非素数数列，如对每个正整数$n$，从$(n+1)!+2$至$(n+1)!+n+1$的$n$个连续正整数都会是合数（因为若$k$为2至$n+1$间的一整数，$(n+1)!+k$就可被k整除）。

狄利克雷定理表示，取两个互素的整数a与b，其线性多项式

$p(n)=a+bn\,$

会有无限多个素数值。该定理亦表示，这些素数值的倒数和会发散，且具有相同b的不同多项式会有差不多相同的素数比例。

有关二次多项式的相关问题则尚无较好之理解。

素数的公式

主条目：素数公式

对于素数，还没有一个已知的有效公式。例如，米尔斯定理与赖特所提的一个定理表示，存在实常数A>1与μ，使得

$\left\lfloor A^{3^{n}}\right\rfloor {\text{ and }}\left\lfloor 2^{\dots ^{2^{2^{\mu }}}}\right\rfloor$

对任何自然数n而言，均为素数。其中，$\lfloor -\rfloor$为高斯符号，表示不大于符号内数字的最大整数。第二个公式可使用伯特兰-切比雪夫定理得证（由切比雪夫第一个证得）。该定理表示，总是存在至少一个素数p，使得 n < p < 2n − 2，其中n为大于3的任一自然数。第一个公式可由威尔逊定理导出，每个不同的n会对应到不同的素数，除了数字2会有多个n对应到外。不过，这两个公式都需要先计算出A或μ的值来。

不存在一个只会产生素数值的非常数多项式，即使该多项式有许多个变量。不过，存在具9个变量的丢番图方程，其参数具备以下性质：该参数为素数，当且仅当其方程组有自然数解。这可被用来获得其所有“正值”均为素数的一个公式。

一特定数以下的素数之数量

主条目：素数定理和素数计算函数

图中的曲线分别表示π(n)（蓝）、n / ln (n)（绿）与Li(n)（红）。

素数计算函数π(n)被定义为不大于n的素数之数量。例如，π(11) = 5，因为有5个素数小于或等于11。已知有算法可比去计算每个不大于n的素数更快的速率去计算π(n)的值。素数定理表示，π(n)的可由下列公式近似给出：

$\pi (n)\approx {\frac {n}{\ln n}},$

亦即，π(n)与等式右边的值在n趋近于无限大时，会趋近于1。这表示，小于n的数字为素数的可能性（大约）与n的数位呈正比。对π(n)更精确的描述可由对数积分给出：

$\operatorname {Li} (n)=\int _{2}^{n}{\frac {dt}{\ln t}}$。

素数定理亦蕰涵著对第n个素数p_n（如p₁ = 2、p₂ = 3等）的大小之估算：当数字大到某一程度时，p_n的值会变得约略为n log(n)。特别的是，素数间隙，即两个连续素数p_n与p_n+1间的差会变得任意地大。后者可由数列 n! + 2, n! + 3,…, n! + n（其中n为任一自然数）看出。

等差数列

等差数列是指由被一固定数（模）q除后会得到同一余数的自然数所组成之集合。例如：

3, 12, 21, 30, 39, ...,

是一个等差数列，模q = 9。除了3以外，其中没有一个数会是素数，因为3 + 9n = 3(1 + 3n)，所以此一数列里的其他数字均为合数。（一般来所有大于q的素数都具有q#·n + m的形式，其中0 < m < q#，且m没有不大于q的素因数。）因此，数列

a, a + q, a + 2q, a + 3q,…

只在a与q 互素（其最大公约数为1）之时，可以有无限多个素数。若满足此一必要条件，狄利克雷定理表示，该数列含有无限多个素数。下图描述q = 9时的情形：数字每遇到9的倍数就会再再由下往上缠一次。素数以红底标记。行（数列）开始于a = 3, 6, 9者至多只包含一个素数。其他行（a = 1, 2, 4, 5, 7, 8）则均包含无限多个素数。更甚之，素数以长期来看，会均匀分布于各行之中，亦即每个素数模9会与6个数其中一数同余的概率均为1/6。

素数（以红底标计）在模9的等差数列中。

格林-陶定理证明，存在由任意多个素数组成的等差数列。一个奇素数p可表示成两个平方数之和p = x² + y²，当且仅当p同余于1模4（费马平方和定理）。

二次多项式的素数值

乌岚螺旋。红点表示素数。具4n² − 2n + 41形式的素数则以蓝点标记。

欧拉指出函数

$n^{2}+n+41\,$

于　0 ≤ n < 40时会给出素数，此一事实导致了艰深的代数数论，或更具体地说为黑格纳数。当n更大时，该函数会给出合数值。哈代- 李特伍德猜想（Hardy-Littlewood conjecture）能给出一个有关具整数系数a、b与c的二次多项式

$f(n)=ax^{2}+bx+c\,$

的值为素数之概率的一个渐近预测，并能以对数积分Li(n)及系数a、b、c来表示。不过，该程式已被证实难以取得：仍未知是否存在一个二次多项式（a ≠ 0）能给出无限多个素数。乌岚螺旋将所有自然数以螺旋的方法描绘。令人惊讶的是，素数会群聚在某些对角线上，表示有些二次多项式会比其他二次多项式给出更多个素数值来。

未解决的问题

ζ函数与黎曼猜想

主条目：黎曼猜想

ζ函数ζ(s)的图。在s=1时，该函数会有极点，亦即会趋近于无限大。

黎曼ζ函数ζ(s)被定义为一无穷级数

$\zeta (s)=\sum _{n=1}^{\infty }{\frac {1}{n^{s}}},$

其中，s为实数部分大于1的一个复数。由算术基本定理可证得，该级数会等于下面的无穷乘积

$\prod _{p{\text{ prime}}}{\frac {1}{1-p^{-s}}}$。

ζ函数与素数密切相关。例如，存在无限多个素数这个事实也可以使用ζ函数看出：若只有有限多个素数，则ζ(1)将会是个有限值。不过，调和级数1 + 1/2 + 1/3 + 1/4 + ...会发散，所以必须有无限多个素数。另一个能看见ζ函数的丰富性，并一瞥现代代数数论的例子为下面的恒等式（巴塞尔问题，由欧拉给出）：

$\zeta (2)=\prod _{p}{\frac {1}{1-p^{-2}}}={\frac {\pi ^{2}}{6}}$。

ζ(2)的倒数6/π²，是两个随机选定的数字会互素的概率。

未被证明的“黎曼猜想”，于1859年提出，表示除s = −2, −4, ...,外，ζ函数所有的根，其实数部分均为1/2。此一猜想与素数间的关连在于，该猜想实际上是在说，素数在正整数中出现频率和统计学的随机不同；若假设为真，素数计算函数便可有效掌握，在大数时不再需要近似求值。从物理的观点来看，这大约是在说，素数分布的不规则性仅来自于随机的噪声。从数学的观点来看，则大约是在说，素数的渐近分布（素数定理表示小于x的素数约有x/log x个）在x周围的区间内，于区间长度远小于x的平方根时亦成立。此一猜想一般认为是正确的。

其他猜想

更多信息：分类:素数猜想

除了黎曼猜想之外，还有许多其他的猜想存在。虽然这些猜想的陈述大多很简单，但许多猜想经过了数十年仍提不出证明，如4个兰道问题，从1912年提出至今仍然未解。其中一个为哥德巴赫猜想，该猜想认为每个大于2的偶数n都可表示成两个素数之和。至于2011年2月，这个猜想对最大达n = 2 · 10¹⁷的所有数字都会成立。较弱形式的哥德巴赫猜想已被证明，如维诺格拉多夫定理，该定理表示每个足够大的奇数都可表示成三个素数之和。陈氏定理表示，每个足够大的偶数都可表示成一个素数与一个半素数（两个素数的乘积）之和。此外，任一个偶数均可写成六个素数之和。数论研究这些问题的分支称之为加法数论。反哥德巴赫猜想，所有的正偶数n都可以表示成两个素数之差，但此猜想可由波利尼亚克猜想类推证明。

其他猜想处理是否有无限多个具某些限制的素数这类问题。据猜想，存在无限多个费波那契素数与无限多个梅森素数，但没有无限多个费马素数。还不知道是否存在无限多个维费里希素数与欧几里得素数。

第三种类型的猜想涉及到素数的分布情形。据猜想，存在无限多对孪生素数，即有无限多对相差2的素数（孪生素数猜想）。波利尼亚克猜想是比孪生素数猜想更强的一个猜想，该猜想表示存在无限多对相差2n的连续素数。据猜想，存在无限多个具n² + 1形式的素数。上述猜想都是申策尔猜想的特例。布罗卡猜想表示，在两个大于2的连续素数之平方数之间，总是会有至少4个素数。勒让德猜想表示，对每个正整数n，n²与(n + 1)²间总会存在一个素数。克拉梅尔猜想可导出勒让德猜想。

应用

长期以来，数论，尤其是对素数的研究，一般都会被认为是典型的纯数学，除了求知的趣味之外，没有其他应用。特别是，一些数论学家，如英国数学家戈弗雷·哈罗德·哈代即对其工作绝对不会有任何在军事上的重大性感到自豪。然而，此一观点在1970年代时遭到粉碎，当素数被公开宣布可以作为产生公钥加密算法的基础之时。素数现在也被用在杂凑表与伪乱数产生器里。

旋转机被设计成在每个转片上有不同数目的销，在每个转片上的销的数量都会是素数，亦或是会与其他转片上的销的数量互素。这有助于在重复所有的组合之前，让所有转片的可能组合都能出现过一次。

国际标准书号的最后一码为校验码，其算法使用到了11是个素数的这个事实。

在汽车变速箱齿轮的设计上，相邻的两个大小齿轮齿数最好设计成素数，以增加两齿轮内两个相同的齿相遇啮合次数的最小公倍数，可增强耐用度减少故障。

在害虫的生物生长周期与杀虫剂使用之间的关系上，杀虫剂的素数次数的使用也得到了证明。实验表明，素数次数地使用杀虫剂是最合理的：都是使用在害虫繁殖的高潮期，而且害虫很难产生抗药性。

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

模一素数与有限域之运算

主条目：模运算

“模运算”使用下列数字修改了一般的运算

$\{0,1,2,\dots ,n-1\},\,$

其中n是个固定的自然数，称之为“模”。计算加法、减法及乘法都与一般的运算一样，不过负数或大于n − 1的数字出现时，会被除以n所得的余数取代。例如，对n=7，3+5为1，而不是8，因为8除以7余1。这通常念为“3+5同余于1模7”，并标记为

$3+5\equiv 1{\pmod {7}}$。

同样地，6 + 1 ≡ 0 (mod 7)、2 - 5 ≡ 4 (mod 7)，因为 -3 + 7 = 4，以及3 · 4 ≡ 5 (mod 7)，因为12除以7余5。加法与乘法在整数里常见的标准性质在模运算里也依然有效。使用抽象代数的说法，由上述整数所组成之集合，亦标记为Z/nZ，且因此为一可交换环。不过，除法在模运算里不一定都是可行的。例如，对n=6，方程

$3\cdot x\equiv 2{\pmod {6}},$

的解x会类比于2/3，无解，亦可透过计算3 · 0、...、3 · 5模6看出。不过，有关素数的不同性质如下：除法在模运算里是可行的，当且仅当n为素数。等价地说，n为素数，当且仅当所有满足2 ≤ m ≤ n − 1的整数m都会与n 互素，亦即其公约数只有1。实际上，对n=7，方程

$3\cdot x\equiv 2\ \ (\operatorname {mod} \ 7),$

会有唯一的解x = 3。因此，对任何素数p，Z/pZ（亦标记为F_p）也会是个体，或更具体地说，是个有限域，因为该集合包含有限多（即p）个元素。

许多定理可以透过从此一抽象的方式检查F_p而导出。例如，费马小定理表示

$a^{p-1}\equiv 1(\operatorname {mod} \ p)$

，其中a为任一不被p整除的整数。该定理即可使用这些概念证得。这意味着

$\sum _{a=1}^{p-1}a^{p-1}\equiv (p-1)\cdot 1\equiv -1{\pmod {p}}$。

吾乡-朱加猜想表示，上述公式亦是p为素数的必要条件。另一个费马小定理的推论如下：若p为2与5之外的其他素数，¹/_p总是个循环小数，其周期为p − 1或p − 1的约数。分数¹/_p依q（10以外的整数）为基底表示亦有类似的效果，只要p不是q的素因数的话。威尔逊定理表示，整数p > 1为素数，当且仅当阶乘 (p − 1)! + 1可被p整除。此外，整数n > 4为合数，当且仅当 (n − 1)!可被n整除。

其他数学里出现的素数

许多数学领域里会大量使用到素数。举有限群的理论为例，西罗定理即是一例。该定理表示，若G是个有限群，且pⁿ为素数p可整除G的阶的最大幂次，则G会有个pⁿ阶的子群。此外，任意素数阶的群均为循环群（拉格朗日定理）。

公开金钥加密

主条目：公开金钥加密

几个公开金钥加密算法，如RSA与迪菲－赫尔曼金钥交换，都是以大素数为其基础（如512位元的素数常被用于RSA里，而1024位元的素数则一般被迪菲-赫尔曼金钥交换所采用）。RSA依靠计算出两个（大）素数的相乘会比找出相乘后的数的两个素因数容易出许多这个假设。迪菲－赫尔曼金钥交换依靠存在模幂次的有效算法，但相反运算的离散对数仍被认为是个困难的问题此一事实。

自然里的素数

周期蝉属里的蝉在其演化策略上使用到素数。蝉会在地底下以幼虫的形态度过其一生中的大部分时间。周期蝉只会在7年、13年或17年后化蛹，然后从洞穴里出现、飞行、交配、产卵，并在至多数周后死亡。此一演化策略的原因据信是因为若出现的周期为素数年，掠食者就很难演化成以周期蝉为主食的动物。若周期蝉出现的周期为非素数年，如12年，则每2年、3年、4年、6年或12年出现一次的掠食者就一定遇得到周期蝉。经过200年以后，假设14年与15年出现一次的周期蝉，其掠食者的平均数量，会比13年与17年出现一次的周期蝉，高出2%。虽然相差不大，此一优势似乎已足够驱动天择，选择具素数年生命周期的这些昆虫。

据猜测，ζ函数的根与复数量子系统的能阶有关。

推广

素数的概念是如此的重要，以致此一概念被以不同方式推广至数学的不同领域里去。通常，“质”（prime）可在适当的意义下，用来表示具有最小性或不可分解性。例如，质体是指一个包含0与1的体F的最小子域。质体必为有理数或具有p个元素的有限域，这也是其名称的缘由。若任一对象基本上均可唯一地分解成较小的部分，则这些较小的部分也会用“质”这个字来形容。例如，在纽结理论里，质纽结是指不可分解的纽结，亦即该纽结不可写成两个非平凡纽结的连通和。任一纽结均可唯一地表示为质纽约的连通和。质模型与三维质流形亦为此类型的例子。

环内的素元

主条目：素元和不可约元素

素数应用于任一可交换环R（具加法、减法与乘法的代数结构）的元素，可产生两个更为一般的概念：“素元”与“不可约元素”。R的元素称为素元，若该元素不为0或单位元，且给定R内的元素x与y，若p可除以xy，则p可除以x或y。一元素称为不可约元素，若该元素不为单位元，且无法写成两个不是单位元之环元素的乘积。在整数环Z里，由素元所组成的集合等于由不可约元素所组成的集合，为

$\{\dots ,-11,-7,-5,-3,-2,2,3,5,7,11,\dots \}\,$。

在任一环R里，每个素元都是不可约元素。反之不一定成立，但在唯一分解整环里会成立。

算术基本定理在唯一分解整环里仍然成立。此类整环的一个例子为高斯整数Z[i]，由具a + bi（其中a与b为任意整数）形式的复数所组成之集合。其素元称之为“高斯素数”。不是所有的素数都是高斯素数：在这个较大的环Z[i]之中，2可被分解成两个高斯素数 (1 + i)与 (1 - i)之乘积。有理素数（即在有理数里的素元），具4k+3形式者为高斯素数；具4k+1形式者则不是。

素理想

主条目：素理想

在环论里，数的概念一般被理想所取代。“素理想”广义化了素元的概念，为由素元产生的主理想，是在交换代数、代数数论与代数几何里的重要工具与研究对象。整数环的素理想为理想 (0)、(2)、(3)、(5)、(7)、(11)、…算术基本定理被广义化成准素分解，可将每个在可交换诺特环里的理想表示成准素理想（为素数幂次的一适合广义化）的交集。

透过环的谱这个概念，素理想成为代数几何对象的点。算术几何也受益于这个概念，且许多概念会同时存在于几何与数论之内。例如，对一扩张域的素理想分解（这是代数数论里的一个基本问题），与几何里的分歧具有某些相似之处。此类分歧问题甚至在只关注整数的数论问题里也会出现。例如，二次域的整数环内的素理想可被用来证明二次互反律。二次互反律讨论下面二次方程

$x^{2}\equiv p\ \ ({\text{mod }}q),\,$

是否有整数解，其中x为整数，p与q为（一般）素数。早期对费马最后定理证明之尝试，于恩斯特·库默尔引入正则素数后达到了高潮。正则素数是指无法在由下列式子（其中a₀、…、a_p−1为整数，ζ则是能使ζ^p = 1的复数）

$a_{0}+a_{1}\zeta +\cdots +a_{p-1}\zeta ^{p-1}\,,$

组成的环里，使得唯一分解定理失效的素数。

赋值

赋值理论研究由一个体K映射至实数R的某个函数（称之为赋值）。每个此类赋值都能给出一个 K上的拓扑，且两个赋值被称为等价，若两者有相同拓扑。K的素数为一赋值的等价类。例如，一个有理数q的p进赋值被定义为整数v_p(q)，使得

$q=p^{v_{p}(q)}{\frac {r}{s}},$

其中r与s不被p所整除。例如，v₃(18/7) = 2。p进范数被定义为

$\left|q\right|_{p}:=p^{-v_{p}(q)}.\,$

特别的是，当一个数字乘上p时，其范数会变小，与一般的绝对赋值（亦称为无限素数）形成明显的对比。当透过绝对赋值完备有理数会得出由实数所组成的体，透过p进范数完备有理数则会得出由p进数所组成的体。实际上，依据奥斯特洛夫斯基定理，上述两种方法是完备有理数的所有方法。一些与有理数或更一般化之整体域有关的算术问题，可能可以被变换至完备（或局部）体上。此一局部-全域原则再次地强调了素数对于数论的重要性。

在艺术与文学里

素数也影响了许多的艺术家与作家。法国作曲家奥立佛·梅湘使用素数创造出无节拍音乐。在《La Nativite du Seigneur》与《Quatre etudes de rythme》等作品里，梅湘同时采用由不同素数给定之长度的基调，创造出不可预测的节奏：第三个练习曲《Neumes rythmiques》中出现了素数41、43、47及53。据梅湘所述，此类作曲方式是“由自然的运动，自由且不均匀的持续运动中获得的灵感”。

NASA科学家卡尔·萨根在他的科幻小说《接触未来》（Contact）里，认为素数可作为与外星人沟通的一种方式。这种想法是他与美国天文学家法兰克·德雷克于1975年闲聊时形成的。

许多电影，如《异次元杀阵》（Cube）、《神鬼尖兵》（Sneakers）、《越爱越美丽》（The Mirror Has Two Faces）及《美丽境界》（A Beautiful Mind），均反映出大众对素数与密码学之神秘的迷恋。保罗·裘唐诺所著的小说《素数的孤独》（The Solitude of Prime Numbers）里，素数被用来比喻寂寞与孤独，被描述成整数之间的“局外人”。

荒木飞吕彦所创作的日本漫画《JoJo的奇妙冒险》第六部《石之海》的反派普奇神父喜欢数素数，他认为素数是孤独的数字，并透过数素数安抚他紧张的情绪。

另见

• 阿德曼-波门伦斯-鲁梅利素性测试
• Bonse不等式
• 布朗筛法
• 伯恩赛德定理
• 契博塔耶夫密度定理
• 中国余数定理
• 卡伦数
• 非法素数
• 素数列表
• 梅森素数
• 可乘数论
• 普通数域筛选法
• 贝潘测试
• 实际数
• 质k元组
• 自由黎曼气体
• 二次剩余问题
• RSA数
• 光滑数
• 超素数
• 胡道尔数
• 幸运素数
• 素数判定法则
• 埃拉托斯特尼筛法
• 孪生素数
• 三胞胎素数
• PrimeGrid
• GIMPS
• 素数大富豪

参考资料

• Apostol, Thomas M., Introduction to Analytic Number Theory, New York: Springer, 1976, ISBN 0-387-90163-9 
• Conway, John Horton; Guy, Richard K., The Book of Numbers, New York: Copernicus, 1996, ISBN 978-0-387-97993-9 
• Crandall, Richard; Pomerance, Carl, Prime Numbers: A Computational Perspective 2nd, Berlin, New York: Springer-Verlag, 2005, ISBN 978-0-387-25282-7 
• Derbyshire, John, Prime obsession, Joseph Henry Press, Washington, DC, 2003, ISBN 978-0-309-08549-6, MR 1968857 
• Eisenbud, David, Commutative algebra, Graduate Texts in Mathematics 150, Berlin, New York: Springer-Verlag, 1995, ISBN 978-0-387-94268-1, MR 1322960 
• Fraleigh, John B., A First Course In Abstract Algebra 2nd, Reading: Addison-Wesley, 1976, ISBN 0-201-01984-1 
• Furstenberg, Harry, On the infinitude of primes, The American Mathematical Monthly (Mathematical Association of America), 1955, 62 (5): 353, JSTOR 2307043, doi:10.2307/2307043 
• Green, Ben; Tao, Terence, The primes contain arbitrarily long arithmetic progressions, Annals of Mathematics, 2008, 167 (2): 481–547, arXiv:math.NT/0404188 , doi:10.4007/annals.2008.167.481 
• Gowers, Timothy, Mathematics: A Very Short Introduction, Oxford University Press, 2002, ISBN 978-0-19-285361-5 
• Guy, Richard K., Unsolved Problems in Number Theory, Berlin, New York: Springer-Verlag, 1981, ISBN 978-0-387-90593-8 
• Havil, Julian, Gamma: Exploring Euler's Constant, Princeton University Press, 2003, ISBN 978-0-691-09983-5 
• Hardy, Godfrey Harold, A Course of Pure Mathematics, Cambridge University Press, 1908, ISBN 978-0-521-09227-2 
• Hardy, Godfrey Harold, A Mathematician's Apology, Cambridge University Press, 1940, ISBN 978-0-521-42706-7 
• Herstein, I. N., Topics In Algebra, Waltham: Blaisdell Publishing Company, 1964, ISBN 978-1114541016 
• Hill, Peter Jensen (编), The Messiaen companion, Portland, Or: Amadeus Press, 1995, ISBN 978-0-931340-95-6 
• Hua, L.K., Additive Theory of Prime Numbers, Translations of Mathematical Monographs 13, Providence, RI: American Mathematical Society: 176–177, 2009 [1965], ISBN 978-0821849422, MR 0194404, OCLC 824812353 
• Lehmer, D. H., Factor table for the first ten millions containing the smallest factor of every number not divisible by 2, 3, 5, or 7 between the limits 0 and 10017000, Washington, D.C.: Carnegie Institution of Washington, 1909 
• McCoy, Neal H., Introduction To Modern Algebra, Revised Edition, Boston: Allyn and Bacon, 1968, LCCN 68-15225 
• Narkiewicz, Wladyslaw, The development of prime number theory: from Euclid to Hardy and Littlewood, Springer Monographs in Mathematics, Berlin, New York: Springer-Verlag, 2000, ISBN 978-3-540-66289-1 
• Ribenboim, Paulo, The little book of bigger primes, Berlin, New York: Springer-Verlag, 2004, ISBN 978-0-387-20169-6 
• Riesel, Hans, Prime numbers and computer methods for factorization, Basel, Switzerland: Birkhäuser, 1994, ISBN 978-0-8176-3743-9 
• Sabbagh, Karl, The Riemann hypothesis, Farrar, Straus and Giroux, New York, 2003, ISBN 978-0-374-25007-2, MR 1979664 
• du Sautoy, Marcus, The music of the primes, HarperCollins Publishers, 2003 [2015-08-23], ISBN 978-0-06-621070-4, MR 2060134, （原始内容存档于2015-09-07） 

外部链接

• Hazewinkel, Michiel (编), Prime number, 数学百科全书, Springer, 2001, ISBN 978-1-55608-010-4 
• Caldwell, Chris, The Prime Pages at primes.utm.edu（页面存档备份，存于互联网档案馆）.
• Prime Numbers，In Our Time (BBC Radio 4)的《In Our Time》节目。
• An Introduction to Analytic Number Theory, by Ilan Vardi and Cyril Banderier（页面存档备份，存于互联网档案馆）
• Plus teacher and student package: prime numbers（页面存档备份，存于互联网档案馆） from Plus, the free online mathematics magazine produced by the Millennium Mathematics Project at the University of Cambridge.
• 出现素数实验 （页面存档备份，存于互联网档案馆）
• 出现可以被整除的概率

素数产生器与计算器

• Prime Number Checker （页面存档备份，存于互联网档案馆） identifies the smallest prime factor of a number.
• Fast Online primality test with factorization（页面存档备份，存于互联网档案馆） makes use of the Elliptic Curve Method (up to thousand-digits numbers, requires Java).
• Huge database of prime numbers（页面存档备份，存于互联网档案馆）
• Prime Numbers up to 1 trillion （页面存档备份，存于互联网档案馆）
• 素数发生器和校验器 （页面存档备份，存于互联网档案馆）