质数

质数（prime number或prime），又称素数，指在大于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$。对于较大或一些具特别形式（如梅森数）的自然数，人们通常使用较有效率的算法测试其是否为质数（例如282589933-1是直至2024年4月为止已知最大的梅森质数，也是直至2024年4月为止已知最大的质数）。虽然人们仍未发现可以完全区别质数与合数的公式，甚至研究质数分布时相当有力的筛法也会碰到奇偶性问题（也就是多种筛法都无法区别质数跟两个质数相乘的合数的问题），但已建构了质数的分布模式（亦即质数在大数时的统计模式）。19世纪晚期得到证明的质数定理指出：一个任意自然数n为质数的几率反比于其数位（或$n$的对数）。

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

## 定义和例子

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

<image>

在数字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不是质数。不存在大于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的质数）为...。

## 算术基本定理

质数对于数论与一般数学的重要性来自于“算术基本定理”。该定理指出，每个大于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视为质数时，许多与质数有关的叙述将不得不以拗口的方式重新表达。像是算术基本定理需要表述成分解为大于1的质数积，否则分解不再唯一。同样地，埃拉托斯特尼筛法将无法正常运作，若将1视为质数，此一筛法将会排除掉所有1的倍数（即所有其他的数），只留下数字1。此外尚有与质数有关的公式，对1不成立，如欧拉函数以及除数函数。

## 历史

<image>

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

希腊之后，到17世纪之前，质数的研究少有进展。1640年，皮埃尔·德·费马叙述了费马小定理（之后才被莱布尼茨与欧拉证明）。费马亦推测，所有具$2^{2^n}+1$形式的数均为质数（称之为费马数），并验证至$n=4$（即216 + 1）不过，后来由欧拉发现，下一个费马数232 + 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$的自然对数。黎曼于论小于某一给定量的素数之个数中勾勒出一个程式，导出了质数定理的证明。其大纲由雅克·阿达马与夏尔-让·德拉瓦莱·普桑所完成，他们于1896年独立证明出质数定理。

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

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

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

## 素数的数量

<image>

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

$$2, 3, 5, 7, 11, 13, \dotsc$$

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

### 欧几里得的证明

欧几里得的证明取任一个由质数所组成的有限集合$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=a b$是个合数（其中$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亿，对许多实际应用而言都太过庞大。

### 筛法

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

### 质数测试与质数证明

现代测试一般的数字$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无关，但会与ε有关）乘于log5+ε(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))$｜遇到卡迈克尔数时会失败

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

<image>

除了前述可应用于任何自然数 $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^{2^k} +1$,

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

$$n=2^i \cdot m$$

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

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

类型｜质数｜数位｜日期｜发现者

梅森质数｜$2^{136279841} - 1$｜$41,024,320$｜2024年10月12日｜互联网梅森质数大搜索

普罗斯数｜$10223 \cdot 2^{31172165} + 1$｜$9,383,761$｜2016年10月31日｜Szabolcs Péter

阶乘质数｜$632760! - 1$｜$3,395,992$｜2024年10月｜PrimeGrid

质数阶乘质数｜$9562633 \# + 1$｜$4,151,498$｜2025年6月｜PrimeGrid

孪生质数｜$2996863034895 \cdot 2^{1290000} \pm 1$｜$388,342$｜2016年9月｜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$ 与 $\mu$，使得

$$\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$ 或 $\mu$ 的值来。

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

### 一特定数以下的质数之数量

<image>

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

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

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

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

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

### 等差数列

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

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

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

$$a, a+q, a+2q, a+3q, \cdots$$

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

<image>

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

### 二次多项式的质数值

<image>

欧拉指出函数

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

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

$$f(n) = a x^2 + bx + c\,$$

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

## 未解决的问题

### ζ函数与黎曼猜想

<image>

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

$$\zeta(s)=\sum_{n=1}^\infin \frac{1}{n^s},$$

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

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

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

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

$\zeta (2)$的倒数$\frac{6}{\pi^2}$，是两个随机选定的数字会互质的几率。

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

### 其他猜想

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

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

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

## 应用

长期以来，数论，尤其是对质数的研究，一般都会被认为是典型的纯数学，除了求知的趣味之外，没有其他应用。特别是，一些数论学家，如英国数学家戈弗雷·哈罗德·哈代即对其工作绝对不会有任何在军事上的重大性感到自豪。然而，此一观点在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 \equiv 0 (\bmod 7)$、$2 - 5 \equiv 4 (\bmod 7)$，因为 $-3 + 7 = 4$，以及$3 \cdot 4 \equiv 5 (\bmod 7)$，因为12除以7余5。加法与乘法在整数里常见的标准性质在模运算里也依然有效。使用抽象代数的说法，由上述整数所组成之集合，亦标记为$\mathbb{Z}/n\mathbb{Z}$，且因此为一可交换环。不过，除法在模运算里不一定都是可行的。例如，对$n=6$，方程

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

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

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

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

许多定理可以透过从此一抽象的方式检查 $\mathbb{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之外的其他质数，$\frac{1}{p}$总是个循环小数，其周期为 $p-1$ 或 $p-1$ 的因数。分数 $\frac{1}{p}$ 依 $q$（10以外的整数）为基底表示亦有类似的效果，只要 $p$ 不是 $q$ 的质因数的话。威尔逊定理表示，整数 $p>1$ 为质数，当且仅当阶乘 $(p-1)!+1$可被 $p$ 整除。此外，整数 $n > 4$ 为合数，当且仅当 $(n-1)!$ 可被 $n$ 整除。

### 其他数学里出现的质数

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

### 公开金钥加密

几个公开金钥加密算法，如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_0, \cdots, a_{p-1}$ 为整数，$\zeta$ 则是能使ζp = 1的复数）

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

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

### 赋值

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

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

其中 $r$ 与 $s$ 不被 $p$ 所整除。例如，$\nu_3 \left( \frac{18}{7} \right) = 2$。$p$ 进范数被定义为

$\left| q \right|_p := e^{-\nu_p(q)}. \,$

$$\left| q \right|_p := p^{-\nu_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的奇妙冒险》第六部《石之海》的反派普奇神父喜欢数质数，他认为质数是孤独的数字，并透过数质数安抚他紧张的情绪。

## 外部链接

- Caldwell, Chris, The Prime Pages at primes.utm.edu.
- Prime Numbers
- 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
- 素数发生器和校验器