算术中的基石

卡尔·弗里德里希·高斯

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

数论的基本组成部分是质数。即诸如：2、3、5、7、11、13等不能被1以外的数整除的整数。质数无法被分解为更简单的元素；它与数学的关系恰如元素与化学的关系。由100个左右的化学元素可以合成化学家们所研究的上百万种化合物。欧几里得证得算术的基本理论为：所有的正整数要么是质数，要么能被唯一地分解为一组质数。

若取小于 300 的质数，则共有 62 个：

2, 3, 5, 7, 11, 13, 17, 19, 23, 29,31, 37, 41, 43, 47, 53, 59, 61, 67, 7173, 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-铀的自然存在的元素。那么质数也适用同理吗？最大质数是什么？

不存在最大的质数

早在古代，就有数学家开始研究质数的性质。古希腊人首先证明了质数的数量有无穷多，因此实际上不存在一个最大的质数。 欧几里得的证明部分是已知的最古老的证明。

他通过假设存在最大的质数，从而得出矛盾，借用反证法进行证明。 我们给所有质数以升序编号，则有P1=2, P2=3, P3=5以此类推。假设有n个质数，记最大质数为。现取Q为全体质数乘积加1，有

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

质数是如何分布的？

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

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

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

因为对于每个整数n，函数值都大于等于40的质数，输出的质数有：

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.

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

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

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

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

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

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

可以求和得

黎曼ζ函数

波恩哈德·黎曼

波恩哈德·黎曼在1859年发表了他在数论方面唯一的论文。论文中黎曼论述了一个函数，当s>1时，该函数与欧拉ζ函数完全相同，但黎曼的函数能够定义在全体实数上。实际上黎曼ζ函数是定义于复数s上的，其中 s=a+b i，且 i²=-1。

黎曼证得他的解析连续ζ函数与质数分布有着密切联系。他惊人的直觉使得他将连续复变函数的性质与质数那实数与独立的性质联系在一起。更具体地说，黎曼说明了π(x)与ζ函数的零点的关系，其中π(x)是比x小的质数。黎曼发现当s取实数时，即便是取负整数，如s=-2,-4,-6,…ζ函数均为零，但黎曼同样发现了函数的其它零点都出现s=1/2+bi直线上。其中第一个零点大约在b=14.134725处。黎曼猜测ζ函数的所有的非实数零点都在s=1/2+bi上，虽然他尚不能证明这一点。这个猜想很快成为人尽皆知的黎曼猜想，并成为了理解质数分布的关键。最近，由计算机算得至少前1000亿个非实数零点s全都落在黎曼猜想的线上。但是，到目前为止，仍未证得这个猜想没有例外。

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

将一个立方数分成两个立方数之和，或一个四次幂分成两个四次幂之和，或者一般地将一个高于二次的幂分成两个同次幂之和，这是不可能的。关于此，我确信我发现了一种美妙的证法，可惜这里的空白处太小，写不下。

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

数学界最难的问题？

乌拉姆的质数螺旋

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

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

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

螺旋的对角线上皆为质数

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

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

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

数字的漩涡

虽然塔尼斯拉夫·乌拉姆因质数螺旋的发现而受到普遍的赞誉，但是他可能不是第一发现人。亚瑟C.克拉克1956年的经典小说《城市与群星》的第六章的开头是英雄杰赛拉克一边分析着电脑屏幕里的整数”漩涡”，一边看着质数像珠子一样近乎整齐地排列在网的交织点。似乎在乌拉姆发现质数螺旋的七年前，亚瑟C.克拉克就已经发现了。

数学家们出于自己的乐趣而研究质数的性质。但质数有其现代科学的应用，尤其在加密领域上。美国政府情报局NSA是理论数学家在世界上最大的雇主。无论何时你在互联网上进行一笔交易，比如信用卡购物，都会使用公钥加密确保你的交易安全，这就是著名的RSA加密算法，它是由罗纳德·李维斯特、阿迪·萨莫尔和伦纳德·阿德曼基于精妙的数论发明的。

RSA加密算法用的是由两个很大的质数相乘得到的数字密钥。这个系统的安全性取决于分解大量数据的难度。使用已知的所有算法去分解大量数据所需步骤数随数字大小呈指数级增长。这意味着密码学家总会领先于计算机一步。若计算机处理器能足够快地分解用于编码的128位数字，我们就可以开始采用512位。然而，如果一个数学家找到一种新的更高效率的分解算法，我们的编码交易安全将会遭到威胁。但密码学家依旧认为当前的算法是安全的，因为尽管许多世纪以来数学家一直寻求破解的算法，但从未成功过。

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