整个数学界最重要的问题之一，质数是如何分布的？

[遇见数学翻译小组] 核心成员: 刘雄威

一个数学爱好者，希望为数学科普工作做更多贡献，欢迎纠错或讨论，微信号是Mr_LiuXW。

英文: plus.maths.org/content/whirlpool-numbers, 翻译: 刘雄威 [遇见数学翻译小组] 核心成员, 校对: 公理. ★ 提示: 如果文中数字/公式显示较大, 请点击右上角中"刷新"即可恢复正常. 欢迎加入 [翻译小组] 请点击 这里 . 

杰赛拉克一动不动地坐在数字的漩涡里。用二进位制表示的一千个质数，整整齐齐地在他面前行进。自电子计算机发明以来，一切算术运算用的都是这种进位制。无数列 1 和 0 雄赳赳地过去，将所有除了自身及 1 外不拥有因子的数的完整序列带到了他的眼前。质数所拥有的神秘性一直使人们为之着迷，直到现在他们仍然吸引着人类的想象。

杰赛拉克不是数学家，虽然有时候他喜欢自认为数学家。他所能做的仅仅是在无穷列质数中寻找特殊关系与规则，使更具有天才的人有可能把它们纳入到总的规律中去。他能发现数字的特征，但不能解释其所以然。披荆斩棘穿行于算术丛林，是他的乐事，有时候他会发现被更有本领的探索者疏漏了的奇妙现象。

他列出所有的整数的矩阵，着手让计算机将布于矩阵表面的质数穿起来，就像将珠子排列于筛子的交叉网上一样。杰赛拉克以前成百次这么做过，但却从未学到任何东西。不过他被所研究的那些数的散布方式迷住了，那些数明显是不按任何规律散布在整个整数矩阵上的。他知道分布的规律已经被发现了，但他总希望找到更多。

- 亚瑟 C.克拉克《城市与群星》(1956,周晓贤译本)

▌算术的基石

▲ 卡尔·弗里德里希·高斯

德国伟大的数学家卡尔·弗里德里希·高斯曾说：“数学是科学的皇后，而算术是数学的皇后。”高斯所说的算术这一数学分支，如今被命名为数论，即关于正整数或整数的研究。十九世纪数学家克罗内克有一句名言“上帝创造了整数，其余的一切则是人造的。”

数论的基本组成部分是质数。即诸如：2、3、5、7、11、13等，除了 1 和该数自身外，无法被其他自然数整除的数(在大于 1 的自然数中)。质数无法被分解为更简单的元素；它与数学的关系恰如元素与化学的关系。由 100 个左右的化学元素可以合成化学家们所研究的上百万种化合物。欧几里得证得算术的基本理论为：

所有的正整数要么是质数，要么能被唯一地分解为一组质数。例如:

若取小于 300 的质数，则共有 62 个：
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.

小于 100 的质数有 25 个，介于 100 与 200 之间的有 21 个，介于 200 与 300 的有 16 个。看上去质数会随增大而稀少。如果选择更大的数，我们会发现 10,000 和 10,100 之间仅有 11 个质数，100,000 和 100,100 之间仅有 6 个。这似乎证明了质数的数量随数值增大逐渐减少， 那么它们最终会消失吗？我们知道，地球上没有超过 92-铀的自然存在的元素。那么质数也适用同理吗？最大质数是什么？

▌不存在最大的质数
早在古代，就有数学家开始研究质数的性质。古希腊人首先证明了质数的数量有无穷多，因此实际上不存在一个最大的质数。欧几里得的证明部分是已知的最古老的证明。他通过假设存在最大的质数，从而得出矛盾，借用反证法进行证明。我们给所有质数以升序编号，则有   以此类推。假设有   个质数，记最大质数为 。现取   为全体质数乘积加   ，有

现在我们可以发现， 除以以上任何一个质数，都有余数，所以   不能被以上的任何质数整除。但我们知道，任意正整数要么是质数，要么能被分解为一组质数。这就意味着 ，  要么是质数，要么能被比   更大的质数整除。与我们的   为最大质数假设相矛盾，原假设不成立，故不存在最大质数。

▌质数是如何分布的？
我们知道质数的数量随数值增大而减少，但它们不会逐渐消失。那下一个问题便是，我们能否得知质数的分布？质数是否像化学元素排列在元素周期表上那样符合某种分布？这是整个数学界的重要问题之一。

质数之间的间距看上去呈无规则变化，但正如上文所列呈现出不断增大的趋势。质数定理表明函数   所得为小于   的质数个数的近似值，其中   为   的自然对数，我们用   表示小于   的质数的实际个数，随着   的增大，近似值逐渐趋近于实际值。下表为两个函数之间的比较：

没有一个简单的公式能够归纳所有的质数，但欧拉得出了一个具有代表性的公式：

因为对于每个整数 ，函数值都大于等于  的质数，输出的质数有：
41, 43, 47, 53, 61, 71, 83, 97, 113, 131, 151, 173, 197, 223, 251, 281, 313, 347, 383, 421, 461, 503, 547, 593, 641, 691, 743, 797, 853, 911, 971, 1033, 1097, 1163, 1231, 1301, 1373, 1447, 1523, 1601.

但该公式在  时无法输出质数，因为此时不可避免的由下式得出结论来。

此外，欧拉还提出了一个更重要的函数，即现在我们所知的  函数:

欧拉给出了  函数的无穷项积形式

其中的积包含所有的质数  。从而可知一个明显的结论：当该函数表示为无穷项和时，和的通项取所有正整数，但当该函数表示为无穷项积时，积的通项只取所有质数。

欧拉把该函数定义在  时有效。在定义域内，即使和包含无数项，但总收敛于某个值。然而，当  时，这一系列项的和却是分散的，从而导致函数难以定义。比如，取  时有

每一项都在无穷无尽地增大。相比之下，取  有

可以求和得  .

▌黎曼  函数

▲ 格奥尔格·弗里德里希·波恩哈德·黎曼

格奥尔格·弗里德里希·波恩哈德·黎曼在1859年发表了他在数论方面唯一的论文。论文中黎曼论述了一个函数，当   时，该函数与欧拉   函数完全相同，但黎曼的函数能够定义在全体实数上。实际上黎曼   函数是定义于复数 上的，其中  且 。黎曼证得他的解析连续   函数与质数分布有着密切联系。他惊人的直觉使得他将连续复变函数的性质与质数那实数与独立的性质联系在一起。

更具体地说，黎曼说明了   与   函数的零点的关系，其中   是比x小的质数。黎曼发现当s取实数时，即便是取负整数，如   时，   函数均为零，但黎曼同样发现了函数的其它零点都出现   直线上。其中第一个零点大约在   处。黎曼猜测   函数的所有的非实数零点都在   上，虽然他尚不能证明这一点。这个猜想很快成为人尽皆知的黎曼猜想，并成为了理解质数分布的关键。最近，由计算机算得至少前1000亿个非实数零点   全都落在黎曼猜想的线上。但是，到目前为止，人来仍未证得这个猜想。

英国的数论数学家G.H.哈代在他的书《一个数学家的自白》中讲到，他在 20 世纪 20 年代从丹麦跨国南海返航启程之前留了一张纸条给同事，里面写着自己已经证明了黎曼猜想，他预料到航行的危险。尽管是一个坚定的、并致力于劝服别人的无神论者，哈代解释道他写那张纸条的目的是希望上帝能够保佑他不会淹死。因为假若他淹死了，就意味着数学家生前声称已证明了，却在与别人讨论证明之前就离世的著名数学问题有两个，即费马大定理与黎曼猜想。费马大定理早已在数学界中名声显赫。17 世纪法国的律师兼业余数学家皮埃尔·德·费马，也是数论历史上的名人之一。他在阅读关于丢番图《算术》所著《页边笔记》中将此命题旁边写道：
将一个立方数分成两个立方数之和，或一个四次幂分成两个四次幂之和，或者一般地将一个高于二次的幂分成两个同次幂之和，这是不可能的。关于此，我确信我发现了一种美妙的证法，可惜这里的空白处太小，写不下。

而在费马去世之后，数学家们用了 350 年的努力，才把这个猜想变成这个定理。

▌数学界最难的问题？

▲ 乌拉姆的质数螺旋

自从黎曼发表论文的 150 年间都没有人能证明或证伪他的猜想，但费曼大定理最后在 1994 年被安德鲁·怀尔斯成功证明。黎曼猜想是当今数学界最著名和最杰出的问题。同时相比于费曼大定理，黎曼猜想有着更深远的数学意义。实际上，许多数学家在假定黎曼猜想正确的基础上发展了许多数学领域，而黎曼猜想看上去也比费曼大定理更难解。

所有编码在  函数中模模糊糊的质数规律仍未被清晰地破解。但是黎曼猜想展示了一个关于质数的更明显的规律。1963 年，一位在美国专攻原子核项目、曾参与曼哈顿计划的波兰数学家塔尼斯拉夫·乌拉姆在二战期间的参与了一个会议，他在会议的研讨会期间心不在焉地随手乱画。画了一个正方形的网格图，然后在网格图的中央标记 ，接着以螺旋形往外的方向按递增顺序标记了其他的正整数。乌拉姆十分惊喜地注意到：当他以这种方式排列整数时，在网格图的对角线上整齐地排列着质数。

▲ 当年该期《科学美国人》杂志封面

这个结果太过出乎预料，以至于质数螺旋的图片登在了《科学美国人》杂志1964年3月期的封面，同时杂志中刊载了马丁·加德纳的一篇《Mathematical Recreations: The Remarkable Lore of the Prime Number.》 Sci. Amer. 210, 120-128, March 1964。

▲ 螺旋的对角线上皆为质数

上图展示了的螺旋仅包含前 100,000 个整数。复合数表示为黑点，质数表示为白点。可以在网格图中清晰地看到大量的白色对角线。即使用除1以外的其他数作为螺旋的起始点，也会有同样的现象。没人能对此提出一个清晰的解释。但这暗示着有很长一系列的质数能被函数  生成，其中、 和  均为整数。

如果我们把  作为螺旋中央的起始数，我们将发现对角线上的数字恰符合欧拉发现的公式 ；正如前文所述，对于  取每个正整数，函数都有大于  的质数。

在插图里，  位于螺旋的中央，其它整数绕螺旋的逆时针方向排列。方格图中的复合数格子标为黄色，质数格子标为白色。  输出的前  个数沿方格图的其中一条对角线排列。

▌数字的漩涡
虽然塔尼斯拉夫·乌拉姆因质数螺旋的发现而受到普遍的赞誉，但是他可能不是第一发现人。亚瑟C.克拉克 1956 年的经典小说《城市与群星》的第六章的开头是英雄杰赛拉克一边分析着电脑屏幕里的整数“漩涡”，一边看着质数像珠子一样近乎整齐地排列在网的交织点。似乎在乌拉姆发现质数螺旋的七年前，亚瑟C.克拉克就已经发现了。我最近问亚瑟C.克拉克先生，他在《城市与群星》中关于描述质数的灵感是从何而来的。他告诉我：
近半个世纪我都对此毫无头绪。在 1970 年H.P.给了我掌上电脑的直系祖先HAL Jr(HP9001)之前我都没有电脑。但我在 1936 年搬到伦敦不久后在科学博物馆看到的巴贝奇未完成的计算机给我留下了深刻的印象。

数学家们出于自己的乐趣而研究质数的性质。但质数有其现代科学的应用，尤其在加密领域上。美国政府情报局 NSA 是理论数学家在世界上最大的雇主。无论何时你在互联网上进行一笔交易，比如信用卡购物，都会使用公钥加密确保你的交易安全，这就是著名的 RSA 加密算法，它是由罗纳德·李维斯特、阿迪·萨莫尔和伦纳德·阿德曼基于精妙的数论发明的。RSA加密算法用的是由两个很大的质数相乘得到的数字密钥。这个系统的安全性取决于分解大量数据的难度。使用已知的所有算法去分解大量数据所需步骤数随数字大小呈指数级增长。这意味着密码学家总会领先于计算机一步。若计算机处理器能足够快地分解用于编码的 128 位数字，我们就可以开始采用 512 位。然而，如果一个数学家找到一种新的更高效率的分解算法，我们的编码交易安全将会遭到威胁。但密码学家依旧认为当前的算法是安全的，因为尽管许多世纪以来数学家一直寻求破解的算法，但从未成功过。

去年三位印度数学家——马宁德拉·阿格拉沃教授和他的两位毕业学生尼拉吉·凯亚尔和尼廷·萨克塞纳——发表了一个检验一个数是质数或复合数的算法。这个算法运用的是非常基本的运算并且作者的代码只有 13 行。这个算法有一个重要的新功能是测试数字  是 否为质数，并且所花费时间是  的线性级而非指数级。实际上，这一时间为  的 12 倍。随着这一算法的出现，也许我们不应该过于草率地排除存在着一个简单的分解算法，尚未被被发现的可能性。也许密码学家应该开始感到担忧了。