简单百科
质数

质数

质数（Prime number），也称素数、不可因数，数学定义为：设一个整数p不为0和正负1，如果它除了约数正负1外和正负p外没有其他的约数，那么p就称为质数。通常不考虑负数情况。

质数的研究最早可追溯到古埃及。古希腊的毕达哥拉斯学派，欧几里得，和埃拉托斯特尼等人对质数有不少研究。近现代数学中，皮埃尔·德·费马，法国博学家马林·梅森，德国数学家克里斯蒂安·哥德巴赫和瑞士数学家莱昂哈德·欧拉等人得到了一些关于质数的重要成果。法国数学家阿德里安-马里·勒让德与德国数学家约翰·卡尔·弗里德里希·高斯各自独立证明了素数定理。法国数学家雅克·阿达马和比利时数学家夏尔-让·德拉瓦莱·普桑完成了素数定理的初等证明。不过质数依然有许多悬而未决的理论，比如著名的哥德巴赫猜想等。

质数有一些基本性质，如质数有无穷多个。此外，在数论以及分析学中还有很多其他的性质，如费马定理和素数定理。质数的判定方法分为确定性和不确定性算法两种，其中试除法是较为基础常用的确定性算法。质数的筛选方法以埃拉托斯特尼筛法为代表。

质数作为数论中重要的概念之一，在数学、密码学、生物学、量子力学等领域应用广泛，如在密码学中，著名的RSA密码系统就基于质数的理论。此外，它也常出现在影视作品和文学作品中。

定义

设整数，如果它除了因数外没有其他的约数，那么就称为质数。通常不考虑负数情况。

历史

质数的发展历程

质数也叫素数，它的历史悠久。在公元前 1550 年左右的古埃及的莱因德数学纸草书中就有对素数与对合数完全不同类型的记录。古希腊的毕达哥拉斯学派（英语：Pythagoras）对质数有不少研究。他们把“2”排除在质数之外，因为“2”不是“真正的数”。公元前300年左右的欧几里得（希腊语：Ευκλειδης）所著的《几何原本》包含与素数有关的重要定理，如有无限多个素数，以及算术基本定理。埃拉托斯特尼（古希腊语：Eratosthenes Sieve）提出的埃拉托斯特尼筛法是用来计算素数的一个简单方法。新毕达哥拉斯学派的学者尼科马库斯（英语：Nicomachus）的《算数导论》定义了素数、合数和完全数,包括对埃拉托斯特尼筛选法的描述,并列出了前4个完全数 (6、28、496 和 8128)。接下来一段时间关于质数的研究发展缓慢，公元6世纪印度数学家婆罗摩笈多（印度语：Brahmagupta）和公元9世纪阿拉伯数学家塔比·库拉（阿拉伯语：Thglbit ibn Qurra）对质数有一些研究。

1640年，皮耶·德·费玛（法语：Pierre de Fermat）叙述了费马小定理，费马还研究了费马数的素数。法国博学家马林·梅森（法语：Marin Mersenne）发现了一类素数，即梅森素数。德国数学家克里斯蒂安·哥德巴赫（德语：Goldbach C）在 1742 年写给莱昂哈德·欧拉的一封信中提出了哥德巴赫的猜想，即每个偶数都是两个素数之和。瑞士数学家欧拉（德语：Leonhard Euler）有许多和质数有关的成果。他证明了素数倒数和的无穷级数会发散。19世纪初，法国数学家阿德里安-马里·勒让德（法语：Adrien-Marie Legendre）与德国数学家约翰·卡尔·弗里德里希·高斯（德语：Johann Carl Friedrich Gauss）独立推测，当趋向无限大时，小于的素数数量会趋近于。德国数学家伯恩哈德·黎曼（德语：Bernhard Riemann）在1859年关于zeta函数的论文中提出了证明勒让德和高斯猜想的大纲。尽管黎曼假说仍未得到证实，但黎曼的大纲于 1896 年由法国数学家雅克·阿达马（法语：Jacques Solomon Hadamard）和比利时数学家夏尔-让·德拉瓦莱·普桑（法语：Charles-Jean de La Vallée Poussin）完成，论文的结果现在被称为素数定理。

随着质数的不断研究，质数的检验成了重要的课题。许多数学家已经研究了比试除法实际适用的数字更大的数字的素数检验。包括费马数检验、卢卡斯-莱默素数检验和广义卢卡斯素数检验等。质数的应用也越来越广，著名的RSA密码系统就以质数的理论作为基础。随着现代计算机的发展，一些计算质数和检验质数的算法也不断被提出。不过一些质数的理论仍然没有得到完美地解决，一代一代的数学家正努力朝着最终的结果迈进。

“1”的素性

在古希腊早期，大多数人们甚至不认为“1”是一个数，自然也不会认为“1”是质数。到了中世纪与文艺复兴时期，许多数学家将“1”考虑为第一个质数。到18世纪中叶，德国数学家克里斯蒂安·哥德巴赫在他与瑞士数学家莱昂哈德·欧拉的通信里将“1”列为第一个质数，但欧拉持反对意见。到了19世纪，仍有许多数学家认为数字“1”是个质数，如美国数学家德里克·莱默（英语：Derrick Henry Lehmer）。

事实上，如果将质数的定义加入“1”，那么许多涉及质数的定理、概念等将需要重新措辞。例如，算术的基本定理需要根据因式分解重新表述为大于“1”的质数，因为每个数字都会有多个因式分解。如果埃拉托斯特尼筛法将“1”作为素数处理，它将无法正常工作，因为它会消除“1”的所有倍数（即所有其他数字）并仅输出单个数字“1”。质数的其他一些更复杂性质也不适用于数字“1”，比如欧拉函数和除数函数之和的公式对于质数包含“1”与否的公式不同。到20世纪初，数学家们开始同意，“1”不应该被列为质数，而应该作为一个“单位”划分为一个特殊的类别。

举例

例1

5是个质数，数字2、3与4均不能整除5。6不是个质数，数字2、3均能整除6。

例2

前50个质数为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。

例3

第1000个质数是7919。

基本性质

性质1

质数有无穷多个。

证明：用反证法和最小自然数原理来证明。最小自然数原理指的是任何非空的自然数集中都有最小的自然数。假设只有有限个不可因数（注意：已约定质数一定是正的）,它们是，考虑，显见，及，由假设知为合数。则知必有不可约数。由假设知必等于某个，因而一定整除，但不可约数，这是不可能的，矛盾。因此，假设是错误的，即不可因数必有无穷多个。证毕。

性质2

设整数，那么一定可表示为质数的乘积(包括本身是质数)，即，其中是质数。

证明：使用反证法和最小自然数原理来证明。假设结论不成立，则存在正整数，它不可表示为质数的乘积。设所有这种正整数组成的集合为，它是非空的。设是中的最小正整数。显见，一定是合数，所以必有。由假设及的最小性知，不属于集合，所以都可表示为质数的乘积：

，这样，就把表示为质数的乘积，这与假设矛盾，证毕。

算数基本定理

定理引理（英文：Fundamental lemma of arithmetic）：设是质数，，那么或至少有一个成立。一般地，若，则至少有一个成立。

算数基本定理（英文：fundamental theorem of arithmetic）：设，那么必有，其中是质数，且在不计次序的意义下，表达式是唯一的。

例子

。

算数基本定理不成立的情况

设集合，则该集合内算数基本定理不成立。原因为，该集合可以引入整除、不可约数、质数等概念，但它们的整除性质本质上是不同的，进一步地，该集合很难引入最大公约数的概念。

数论性质

概念

模：设，若，即，则称为模。

既约剩余系：先给出剩余类的定义。把全体整数分为这样的若干个两两不相交的集合，使得在同一个集合中的任意两个数对模一定同余，而属于不同集合中的两个数对模一定不同余。每一个这样的集合称为模的剩余类。一组数称为模的既约（或互质）剩余系，如果，以及对任意的，有且仅有一个是对模的剩余，即同余于模。

互素：若，则称和是既约的，或是互素的。一般地，若，则称是既约的，或是互素的。

欧拉函数

模的既约剩余系的元素个数就是欧拉函数（英文：Euler function），以下介绍欧拉函数的性质。

性质1

设，若与有相同的素因素，那么，特别地，若，，则。若，则。

性质2

对任意正整数有。

性质3

费马-欧拉定理（英文：Fermat-Euler's theorem）：设，则有，特别当为质数时，对任意的有。通常把后式称为费马小定理（英文：Fermat's little theorem），前式称为欧拉定理（英文：Euler's theorem）。

威尔逊定理

设是质数，是模的既约剩余系，就有，特别地，有。

p进数

p进数（英文：p-adic number）也称作局部数域，是有理数域拓展成的完备数域的一种。p进数的距离概念建立在整数的整除性质上。给定素数p，若两个数之差被p的高次幂整除，那么这两个数距离就“接近”，幂次越高，距离越近。这种定义在数论性质上的“距离”能够反映同余的信息。

分析学性质

素数定理

设是给定的实数，以表示不超过的素数个数。素数定理是指以下的渐进公式：

和。上述两式可简写为：。

素数定理直到1896年才为法国数学家雅克·阿达马（法语：J. Hadamard）和比利时数学家德·拉·瓦·布桑（法语：Charles Jean de la Vallée Poussin），利用十分高深的复变函数理论所各自独立证明。直到1949年，美籍挪威数学家阿特勒·塞尔伯格（英文：A.Selberg）和匈牙利数学家爱尔特希（英文： P.Erdos）才各自独立地给出了这个定理的初等证明，但证明十分复杂。

狄利克雷算术级数定理

狄利克雷算术级数定理（英文：Dirichlet's theorem on arithmetic progressions）：对于任意两个正的互质整数和，存在无限多形式的的质数，其中也是一个正整数。的级数形式为：

狄利克雷算术级数定理的更强形式指出，对于任何这样的算术级数，级数中素数的倒数之和是发散的，并且具有相同模数的不同算术级数具有大致相同的素数比例。等效地，素数均匀分布（渐近）在包含与的互质的同余类模中。

Zeta 函数和黎曼假设

黎曼假设（英文：Riemann hypothesis）是1859年数学中最著名的未解问题之一，也是千禧年奖问题之一。它是伯恩哈德·黎曼Zeta函数的零点分布的猜想。黎曼猜想提出，Zeta函数非平凡零点的实数部分是，即所有的非平凡零点都应该位于直线（“临界线”）上。为一实数，而为虚数的基本单位。Zeta函数定义为：

。

质数在自然数中的分布问题在纯粹数学和应用数学上都很重要，但它的分布没有什么规律。伯恩哈德·黎曼发现质数出现的频率与黎曼Zeta函数紧密相关。如果黎曼假设成立，那么由素数定理给出的质数的渐近分布将在更短的区间内成立。

二次多项式的素值

欧拉指出函数在时均产生质数。在时会产生合数。对这种现象的解释导致了黑格纳数（英文：Heegner number）问题和类数问题（英文：Class number problem）。哈代-利特尔伍德猜想（英文：Hardy-Littlewood conjecture F）根据对数积分和多项式系数预测了具有整数系数的二次多项式值中的素数密度。没有二次多项式被证明可以取无限多的素数。

质数的判定

质数的判定有确定性算法和不确定性算法两类方法，确定性是指可以肯定地给出一个数是不是质数，不确定性算法则有可能出错。

确定性算法

试除法

这是判断质数的最基本方法。试除法将该数除以每个大于1且小于等于的数。若存在一个相除为整数的结果，则不是质数。反之则是个质数。试除法在数字较小的时候可以使用，但当数字较大时运算极慢，需要面对指数爆炸的情况。

AKS素性测试

AKS素性测试由三个来自印度坎普尔理工学院的计算机科学家，曼宁德拉·阿格拉瓦尔（英文：Manindra Agrawal）、尼拉吉·卡亚尔（英文：Neeraj Kayal）和尼汀·沙克谢纳（英文：Nitin Saxena）提出的计算机算法。它的计算时间复杂度为。

椭圆曲线素性证明

椭圆曲线素性证明（英文：Elliptic curve primality proving）简称ECPP，是素数证明中最快、使用最广泛的方法之一。它的计算时间复杂度为。

不确定性算法

费马素数判定法

费马素数判别法使用到如下的费马小定理：如果是质数，，那么。若想要测试一个数字b是否为素数，则可随机选择n来计算的值。这个测试的缺点在于，有些合数即使不是素数，也会符合上述等式。这些数叫卡迈克尔数，比如561,1105,1729。

质数的筛选

埃拉托斯特尼筛法

对给定的正整数，从已知不超过的所有素数出发，找出不超过的所有素数的方法，就称为埃拉托斯特尼筛法（古希腊语：Eratosthenes 筛子）。这是筛选素数的十分有效的方法，至今构造素数表仍是利用这个方法。埃拉托斯特尼筛法通常指下列两个等价的公式：

或，

这里表示序列中所有与既约的数的个数。

埃拉托斯特尼筛法可以经公式推导为下述公式：

这就给出了计算的一个有效算法。

以下是一个例子：

例：求不超过100的质数个数。

解：取，不超过的质数是2,3,5,7，所以得

即不超过100的质数个数有25个。

质数个数与大小的弱估计

先介绍一个重要函数，莫比乌斯函数（英文：Mobius 函数）记作，定义为：

莫比乌斯函数可以推出埃拉托斯特尼筛法的公式。它也可以推出一个重要定理：

设，表示不超过，且其素因数都大于的所有正整数的个数，那么

。

上述定理可以得到的很弱的下界估计及第个质数的很弱的上界估计，共两个：

结论1：设，一定存在正常数，使得这里表示第个质数。

结论2：设全体质数按大小排列排成的序列是，有及。

质数个数与大小的强估计

切比雪夫总和不等式（俄语：Чебышев）是依靠的素因数分解式来给出从阶来说最好的上下界估计。不等式形式如下：

设，有及，这里表示第个质数。

质数的猜想

关于质数的猜想有非常多，这里介绍几个著名猜想。

哥德巴赫猜想

哥德巴赫猜想（英文：Goldbach's conjecture）：是否每一个大于2的偶数都可以写成两个素数之和？

哥德巴赫猜想最早出现在1742年普鲁士数学家哥德巴赫（英文：Goldbach）与欧拉的通信中。哥德巴赫原初猜想的现代陈述为：任一大于5的整数都可写成三个质数之和。欧拉在回信中注明此一猜想可以有另一个等价的版本：任一大于2的偶数都可写成两个质数之和。从关于偶数的哥德巴赫猜想可推出：任一大于5的奇数都可写成三个素数之和。后者被称为弱哥德巴赫猜想。弱哥德巴赫猜想已于1937年苏联数学家列夫·杰里科维奇·史尼尔曼证明。而哥德巴赫猜想的证明难度比弱哥德巴赫猜想难度大得多，很长时间以来都没有什么实质性的进展。

挪威数学家布朗（法语：Brun）于1919年使用推广后的埃拉托斯特尼筛法证明了：所有充分大的偶数都能表示成两个数之和，并且两个数的素因数个数都不超过9个。这个方法的思路是：如果能将其中的“9个”缩减到“1个”，就证明了哥德巴赫猜想。布朗证明的命题可以被记作“9+9”，以此类推，哥德巴赫猜想就是“1+1”。1966 年，陈景润宣布他证明了“陈氏定理”，并于1973 年发表了“1+2”的全部证明。这在国际数学界引起了强烈的反响，并且一致地将这一结果称为陈景润定理。时至今日，这也是哥德巴赫猜想所得到的最好结果。

梅森猜想

梅森猜想（英文：Mersenne's conjecture）：对于任何奇自然数p，若以下其中两句叙述成立，剩下的一句就会成立：

1.或。

2.是质数。

3.是质数。

其中，就是著名的梅森素数。梅森猜想最开始是法国博学家马林·梅森（法语：Marin Mersenne）提出的，但他最先的猜想存在错误。最后由美国数学家贝特曼（英语： P. T. Bateman）等人提出了新梅森猜想，就是上述形式。新梅森猜想更被视作是一种已证实的规律，而不是未解决的难题。

波利尼亚克猜想

波利尼亚克猜想（英文：Polignac's conjecture）：对于任何正偶数 n，存在无限多大小为 n 的素数间隙。换句话说：有两个连续的素数有无穷多的情况，差值为n。

应用

数学

质数可用于构造多边形和多边形分区。对于费马质数，其中为自然数。时3，5，17，257和65537为质数，时则为合数。在几何的尺规作图中，正多边形可尺规做图当且仅当正多边形的边数的奇质数因子是费马数。当是质数幂时，就可以将一个正多边形划分成个周长、面积相等的多边形分区。

密码学

RSA系统是三位计算机科学家罗纳德·林·里维斯特（英文：R.L. Rivest），阿迪·萨莫尔（英文：A. Shamir）及莱纳德·阿德尔曼（英文：L.Adleman）于1978年提出的基于欧拉定理及大数的素因子分解所提出的公开加密方式的密码系统。下面简介RSA的理论原理。

设是两个不同的大质数，再设正整数满足，这样对任一整数A，，必有唯一的整数B满足，从而对任意整数必有，因此，有。这样，如果某甲知道了数(但不知道)，他为了把A发送给知道的某乙而不让别人知道，就可以公开把确定的B发送给某乙，因为乙可以利用式子确定的来由B得到A。由于大数要分解为这两个素数的乘积是十分困难的，所以，不知道的人很难获得正确的数A。这就是RSA系统的基本原理。这样，任何一个信息都可以先数字化，然后以这样的方式发送。这就是乙为自己建立了一个公开加密方式——公开数及转换方式-——的密码系统。任何人可以公开向乙这样发送信息，而难以被他人破解。

生物学

Magicicada 属蝉使用的进化策略利用了质数。这些昆虫一生中的大部分时间都是作为蛴螬在地下度过的。它们只会在 7 年、13 年或 17 年后化蛹，然后从洞穴中出来，此时它们会飞来飞去，繁殖，然后最多几周后死亡。生物学家推测，这些质数繁殖周期长度已经进化，以防止捕食者与这些周期同步。

量子力学

质数在量子信息科学中也很重要，质数的一些数学结构例如互无偏基和对称信息完备的正映射值测度对于构建量子信息有着重要的作用。在不等于 3 的素数维数中，每个组协变对称信息完全正算子值测度（SIC POVM）相对于唯一的海森伯格赫尔曼·外尔（HW）群是协变的。此外，SIC POVM 的对称群是Clifford群的一个子群。因此，当且仅当两个SIC POVM相对于HW群的协变在扩展的 Clifford 群的同一轨道上时，它们在酉或反酉等价。也有数学家和物理学家推测伯恩哈德·黎曼 zeta 函数的零点与量子系统的能级有关。

参考资料

prime number.cnki学术翻译.2023-11-26

Earliest Known Uses of Some of the Words of Mathematics (G).mathshistory.2023-11-26

质数的孤独.豆瓣读书.2023-11-26

A000040 as a simple table.OEIS.2023-11-26

The First 1,000 Primes.t5k.2023-11-26

Least Carmichael number with n prime factors, or 0 if no such number exists. .OEIS.2023-11-26

Goldbach Conjecture.mathworld.2023-12-29

new mersenne prime conjecture.t5k.2023-11-26

Fermat primes: primes of the form 2^(2^k) + 1, for some k >= 0..OEIS.2023-12-29

石之海（乔乔的奇妙冒险第6部）.哔哩哔哩漫画.2023-11-26

定义

相关概念

素因数

公约数

历史