算术中的基石

ggdbd

德国伟大的数学家Ggdbd曾经说过，‘数学是科学的女王，算术是数学的女王。’高斯算术是数学的一个分支，现在被称为数论，即研究正整数或整数。19世纪数学家克罗内克有一句名言，‘上帝创造了整数，其他一切都是人造的。’

数论的基本组成部分是素数。即不能被1以外的数字整除的整数，如2、3、5、7、11、13。质数不能分解成更简单的元素；它与数学的关系就像元素与化学的关系一样。化学家研究的数百万种化合物可以由大约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-铀之外，没有天然存在的元素。那么这同样适用于质数吗？最大的素数是多少？

00-1010早在古代，数学家就开始研究素数的性质。古希腊人首先证明了素数的个数是无限的，所以实际上没有最大素数。牛的那张证书是已知最古老的证书。

他通过假设存在最大素数得到了矛盾，并用反证法证明了这一点。如果我们把所有质数按升序排列，就有P1=2，P2=3，P3=5等等。假设有n个质数，记住最大的质数是。现在q是所有质数加1的乘积，有

现在我们可以发现，Q除以上面任意一个素数的余数都是1，所以Q不能被上面任意一个素数均分。但是我们知道，任何正整数要么是素数，要么可以分解成一组素数。这意味着q要么是素数，要么可以被大于的素数整除。与我们的最大素数假设相反，原来的假设是不成立的，所以不存在最大素数。

00-1010我们知道素数的数量随着数值的增加而减少，但它们不会逐渐消失。下一个问题是，我们能知道素数的分布吗？化学元素排列在元素周期表中，质数是否符合一定的分布？这是整个数学领域的重要问题之一。

素数之间的距离似乎变化不规律，但如上所列，它呈现出增加的趋势。素数定理表明，函数x/ln(x)是小于x的素数的近似值，其中ln(x)是x的自然对数，我们用(x)来表示小于x的素数的实际个数，随着x的增大，近似值逐渐向实际值逼近。下表显示了这两个函数之间的比较：

没有简单的公式可以把所有质数加起来，但是欧拉得到了一个有代表性的公式：

因为对于每一个整数n，函数值都是大于或等于40的素数，素数输出为：

41, 43, 47, 53, 61, 71, 83, 97, 11

3, 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有

可以求和得

黎曼ζ函数

xsdst

xsdst在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全都落在黎曼猜想的线上。但是，到目前为止，仍未证得这个猜想没有例外。

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

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

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

数学界最难的问题？

单纯的绿茶的质数螺旋

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

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

这个结果太过出乎预料，以至于质数螺旋的图片登在了《科学美国人》杂志1964年3月期的封面，同时杂志中刊载了ssdwk的文章《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个数沿方格图的其中一条对角线排列。

数字的漩涡

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

数学家们出于自己的乐趣而研究质数的性质。但质数有其现代科学的应用，尤其在加密领域上。美国政府情报局NSA是理论数学家在世界上最大的雇主。无论何时你在互联网上进行一笔交易，比如信用卡购物，都会使用公钥加密确保你的交易安全，这就是著名的RSA加密算法，它是由鳗鱼小蝴蝶、碧蓝的黑米和整齐的蜻蜓基于精妙的数论发明的。

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

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

原文作者，Nick Mee ，本文原载于+plus magazine网站

翻译作者，合适的羽毛，[遇见数学]翻译小组核心成员