数学中质数是什么 质数有什么含义
数学合集开篇我们认识了《「数学」数学中的次方》，本篇认识质数。
一、什么是质数
质数（Prime number，又称素数），指在大于 1 的自然数中，除了 1 和该数自身外，无法被其他自然数整除的数（也可定义为只有1与该数本身两个正因数的数）。
例如：在数字 1 至 6 间，数字 2、3 与 5 为素数，1、4 与 6 则不是素数。
1 不是素数，其理由见下文，先放放稍后立马讲解。2 是素数，因为只有 1 与 2 可整除该数。3 是素数，因为 1 与 3 可整除 3，3 除以 2 会余 1。4 是合数，因为 2 是另一个（除 1 与 4 外）可整除 4 的数：4 = 2 × 2。5 是素数，数字 2、3 与 4 均不能整除 5。6 是合数，会被 2 或 3 整除（同数字 4），因为 6 = 2 × 3。
二、质数历史
在古埃及人的幸存纪录中，有迹象显示他们对素数已有部分认识：例如，在莱因德数学纸草书中的古埃及分数展开时，对素数与对合数有着完全不同的类型。不过，对素数有过具体研究的最早幸存纪录来自古希腊。公元前300年左右的《几何原本》包含与素数有关的重要定理，如有无限多个素数，以及算术基本定理。欧几里得亦展示如何从梅森素数建构出完全数。埃拉托斯特尼提出的埃拉托斯特尼筛法是用来计算素数的一个简单方法，虽然今天使用电脑发现的大素数无法使用这个方法找出。
希腊之后，到17世纪之前，素数的研究少有进展。1640年，皮埃尔·德·费马叙述了费马小定理（之后才被莱布尼茨与欧拉证明）。费马亦推测，所有具22n + 1形式的数均为素数（称之为费马数），并验证至n = 4（即216 + 1）不过，后来由欧拉发现，下一个费马数232 + 1即为合数，且实际上其他已知的费马数都不是素数。法国修道士马兰·梅森发现有的素数具2p − 1的形式，其中p为素数。为纪念他的贡献，此类素数后来被称为梅森素数。
欧拉在数论中的成果，许多与素数有关。他证明无穷级数1/2 + 1/3 + 1/5 + 1/7 + 1/11 +…会发散。1747年，欧拉证明每个完全数都确实为2p−1(2p − 1)的形式，其中第二个约数为梅森素数。
19世纪初，勒让德与高斯独立推测，当x趋向无限大时，小于x的素数数量会趋近于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可被至少一个素数整除（即使N本身为素数亦同）。
任何可整除N的素数都不可能是有限集合S内的元素（素数），因为后者除N都会余1。所以，N可被其他素数所整除。因此，任一个由素数所组成的有限集合，都可以扩展为更大个由素数所组成之集合。
这个证明通常会被错误地描述为，欧几里得一开始假定一个包含所有素数的集合，并导致矛盾；或者是，该集合恰好包含n个最小的素数，而不任意个由素数所组成之集合。今日，n个最小素数相乘后加一的一个数字，被称为第n个欧几里得数。
解析证明
欧拉的证明使用到素数倒数的总和
。当p够大时，该和会大于任意实数。这可证明，存在无限多个素数，否则该和将只会增长至达到最大素数p为止。S(p)的增加率可使用梅滕斯第二定理来量化。比较总和
当n趋向无限大时，此和不会变成无限大（见巴塞尔问题）。这意味着，素数比自然数的平方更常出现。布朗定理指出，孪生素数倒数的总和
是有限的。
四、测试分解
确认一个数n是否为素数有许多种方法。最基本的程序为试除法，但因为速率很慢，没有什么实际用处。有一类现代的素数测试可适用于任意数字之上，另有一类更有效率的测试方法，则只能适用于特定的数字之上。大多数此类方法只能辨别n是否为素数。也能给出n的一个（或全部）素因数之程序称之为约数分解算法。
试除法
测试n是否为素数的最基本方法为试除法。此一程序将n除以每个大于1且小于等于n的平方根之整数m。若存在一个相除为整数的结果，则n不是素数；反之则是个素数。实际上，若
是个合数（其中a与b ≠ 1），则其中一个约数a或b必定至大为
。例如，对
使用试除法，将37除以m = 2, 3, 4, 5, 6，没有一个数能整除37，因此37为素数。此一程序若能知道直至
的所有素数列表，因为试除法只检查m为素数的状况，所以会更有效率。例如，为检查37是否为素数，只有3个相除是必要的（m = 2, 3, 5），因为4与6为合数。
作为一个简单的方法，试除法在测试大整数时很快地会变得不切实际，因为可能的约数数量会随着n的增加而迅速增加。依据下文所述之素数定理，小于
的素数之数量约为
，因此使用试除法测试n是否为素数时，大约会需要用到这么多的数字。对n = 1020，此一数值约为4.5亿，对许多实际应用而言都太过庞大。
筛法
一个能给出某个数值以下的所有素数之算法，称之为素数筛法，可用于只使用素数的试除法内。最古老的一个例子为埃拉托斯特尼筛法（见上文），至今仍最常被使用。阿特金筛法为另外一例。在电脑出现之前，筛法曾被用来给出107以下的素数列表。
测试证明
现代测试一般的数字n是否为素数的方法可分成两个主要类型，随机（或“蒙特卡洛”）与确定性算法。确定性算法可肯定辨别一个数字是否为素数。例如，试除法即是个确定性算法，因为若正确执行，该方法总是可以辨别一个素数为素数，一个合数为合数。随机算法一般比较快，但无法完全证明一个数是否为素数。这类测试依靠部分随机的方法来测试一个给定的数字。例如，一测试在应用于素数时总是会通过，但在应用于合数时通过的概率为p。若重复这个测试n次，且每次都通过，则该数为合数的概率为1/(1-p)n，会随着测试次数呈指数下滑，因此可越来越确信（虽然总是无法完全确信）该数为素数。另一方面，若测试曾失败过，则可知该数为合数。
随机测试的一个特别简单的例子为费马素数判定法，使用到对任何整数a，np≡n (mod p)，其中p为素数的这个事实（费马小定理）。若想要测试一个数字b是否为素数，则可随机选择n来计算nb (mod b)的值。这个测试的缺点在于，有些合数（卡迈克尔数）即使不是素数，也会符合费马恒等式，因此这个测试无法辨别素数与卡迈克尔数，最小的三个卡迈克尔数为561，1105，1729。卡迈克尔数比素数还少上许多，所以这个测试在实际应用上还是有用的。费马素数判定法更强大的延伸方法，包括贝利-PSW、米勒-拉宾与Solovay-Strassen素数测试，都保证至少在应用于合数时，有部分时候会失败。
确定性算法不会将合数错误判定为素数。在实务上，最快的此类方法为椭圆曲线素数证明。其运算时间是透过实务分析出来的，不像最新的AKS素数测试，有已被严格证明出来的复杂度。确定性算法通常较随机算法来得慢，所以一般会先使用随机算法，再采用较费时的确定性算法。
下面表格列出一些素数测试。运算时间以被测试的数字n来表示，并对随机算法，以k表示其测试次数。此外，ε是指一任意小的正数，log是指一无特定基数的对数。大O符号表示，像是在椭圆曲线素数证明里，所需之运算时间最长为一常数（与n无关，但会与ε有关）乘于log5+ε(n)。
测试
发明于
类型
运算时间
注记
AKS素数测试
2002
确定性
O(log6+ε(n))
椭圆曲线素数证明
1977
确定性
O(log5+ε(n))“实务分析”
贝利-PSW素数测试
1980
随机
O(log3 n)
无已知反例
米勒-拉宾素数判定法
1980
随机
O(k · log2+ε (n))
错误概率4−k
Solovay-Strassen素数
1977
随机
O(k · log3 n)
错误概率2−k
费马素数判定法
随机
O(k · log2+ε (n))
遇到卡迈克尔数时会失败
算法素数
除了前述可应用于任何自然数n之上的测试外，一些更有效率的素数测试适用于特定数字之上。例如，卢卡斯素数测试需要知道n − 1的素因数，而卢卡斯-莱默素数测试则需要以n + 1的素因数作为输入。例如，这些测试可应用在检查
n! ± 1 = 1 × 2 × 3 × … × n ± 1
是否为一素数。此类形式的素数称之为阶乘素数。其他具p+1或p-1之类形式的素数还包括索菲·热尔曼素数（具2p+1形式的素数，其中p为素数）、素数阶乘素数、费马素数与梅森素数（具2p − 1形式的素数，其中p为素数）。卢卡斯-雷默素数测试对这类形式的数特别地快。这也是为何自电脑出现以来，最大已知素数总会是梅森素数的原因。
费马素数具下列形式
Fk = 22k + 1,
其中，k为任意自然数。费马素数以皮埃尔·德·费马为名，他猜想此类数字Fk均为素数。费马认为Fk均为素数的理由为此串列的前5个数字（3、5、17、257及65537）为素数。不过，F5却为合数，且直至2015年发现的其他费马数字也全都是合数。一个正n边形可用尺规作图，当且仅当
n = 2i × m
其中，m为任意个不同费马素数之乘积，及i为任一自然数，包括0。
下列表格给出各种形式的最大已知素数。有些素数使用分散式计算找到。2009年，互联网梅森素数大搜索因为第一个发现具至少1,000万个数位的素数，而获得10万美元的奖金。电子前哨基金会亦为具至少1亿个数位及10亿个数位的素数分别提供15万美元及25万美元的奖金。
类型
素数
数位
日期
发现者
梅森素数
277232917 − 1
23,249,425
2017年12月26日
互联网梅森素数大搜索
非梅森素数（普罗斯数）
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的约数分解。椭圆曲线分解是一个依靠椭圆曲线上的运算来分解素因数的算法。
五、素数应用
长期以来，数论，尤其是对素数的研究，一般都会被认为是典型的纯数学，除了求知的趣味之外，没有其他应用。特别是，一些数论学家，如英国数学家戈弗雷·哈罗德·哈代即对其工作绝对不会有任何在军事上的重大性感到自豪。然而，此一观点在1970年代时遭到粉碎，当素数被公开宣布可以作为产生公钥加密算法的基础之时。素数现在也被用在杂凑表与伪乱数产生器里。
旋转机被设计成在每个转片上有不同数目的销，在每个转片上的销的数量都会是素数，亦或是会与其他转片上的销的数量互素。这有助于在重复所有的组合之前，让所有转片的可能组合都能出现过一次。
国际标准书号的最后一码为校验码，其算法使用到了11是个素数的这个事实。
在汽车变速箱齿轮的设计上，相邻的两个大小齿轮齿数最好设计成素数，以增加两齿轮内两个相同的齿相遇啮合次数的最小公倍数，可增强耐用度减少故障。
在害虫的生物生长周期与杀虫剂使用之间的关系上，杀虫剂的素数次数的使用也得到了证明。实验表明，素数次数地使用杀虫剂是最合理的：都是使用在害虫繁殖的高潮期，而且害虫很难产生抗药性。
以素数形式无规律变化的导弹和鱼雷可以使敌人不易拦截。
素数运算
“模运算”使用下列数字修改了一般的运算
其中n是个固定的自然数，称之为“模”。计算加法、减法及乘法都与一般的运算一样，不过负数或大于n − 1的数字出现时，会被除以n所得的余数取代。例如，对n=7，3+5为1，而不是8，因为8除以7余1。这通常念为“3+5同余于1模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，方程
的解x会类比于2/3，无解，亦可透过计算3 · 0、…、3 · 5模6看出。不过，有关素数的不同性质如下：除法在模运算里是可行的，当且仅当n为素数。等价地说，n为素数，当且仅当所有满足2 ≤ m ≤ n − 1的整数m都会与n 互素，亦即其公约数只有1。实际上，对n=7，方程
会有唯一的解x = 3。因此，对任何素数p，Z/pZ（亦标记为Fp）也会是个体，或更具体地说，是个有限域，因为该集合包含有限多（即p）个元素。
许多定理可以透过从此一抽象的方式检查Fp而导出。例如，费马小定理表示
，其中a为任一不被p整除的整数。该定理即可使用这些概念证得。这意味着
。
吾乡－朱加猜想表示，上述公式亦是p为素数的必要条件。另一个费马小定理的推论如下：若p为2与5之外的其他素数，1/p总是个循环小数，其周期为p − 1或p − 1的约数。分数1/p依q（10以外的整数）为基底表示亦有类似的效果，只要p不是q的素因数的话。威尔逊定理表示，整数p > 1为素数，当且仅当阶乘 (p − 1)! + 1可被p整除。此外，整数n > 4为合数，当且仅当 (n − 1)!可被n整除。
其他素数
许多数学领域里会大量使用到素数。举有限群的理论为例，西罗定理即是一例。该定理表示，若G是个有限群，且pn为素数p可整除G的阶的最大幂次，则G会有个pn阶的子群。此外，任意素数阶的群均为循环群（拉格朗日定理）。
金钥加密
几个公开金钥加密算法，如RSA与迪菲－赫尔曼金钥交换，都是以大素数为其基础（如512位元的素数常被用于RSA里，而1024位元的素数则一般被迪菲-赫尔曼金钥交换所采用）。RSA依靠计算出两个（大）素数的相乘会比找出相乘后的数的两个素因数容易出许多这个假设。迪菲－赫尔曼金钥交换依靠存在模幂次的有效算法，但相反运算的离散对数仍被认为是个困难的问题此一事实。
自然素数
周期蝉属里的蝉在其演化策略上使用到素数。蝉会在地底下以幼虫的形态度过其一生中的大部分时间。周期蝉只会在7年、13年或17年后化蛹，然后从洞穴里出现、飞行、交配、产卵，并在至多数周后死亡。此一演化策略的原因据信是因为若出现的周期为素数年，掠食者就很难演化成以周期蝉为主食的动物。若周期蝉出现的周期为非素数年，如12年，则每2年、3年、4年、6年或12年出现一次的掠食者就一定遇得到周期蝉。经过200年以后，假设14年与15年出现一次的周期蝉，其掠食者的平均数量，会比13年与17年出现一次的周期蝉，高出2%。虽然相差不大，此一优势似乎已足够驱动天择，选择具素数年生命周期的这些昆虫。
据猜测，ζ函数的根与复数量子系统的能阶有关。
