Arithmetic / 算术

对我们每一个人来说, 数学都是从算术开始的, 这本书也是一样。如我们所知, 算术研究的是最基础的数量概念, 如整数。谈到最具普遍意义的数学思想, 那就是区分个体数目的思想, 也就是“计数”。

“上帝创造了整数, 其他一切都由人制造。”[1]利奥波德 • 克罗内克尔（Leopold Kronecker）这句名言揭示了整数的内在必然性以及它们无可否认的自然性。如果我们把数学比作一个庞大的管弦乐队, 那么整数系就应该被比作一面大鼓：简单、直接、反复, 为所有其他乐器提供基础节奏。的确, 也有更加复杂的概念, 可以比作“数学双簧管”“数学圆号”和“数学大提琴”, 我们将在后面的章节中研究其中的一些概念。但是, 整数总是根基。

数学家称这些无穷无尽的为正整数, 或更形象地称其为自然数。在认识了它们并为它们起好名字之后, 我们的注意力就转向了如何利用一些重要的方法把它们结合起来。最基础的方法就是加法。这一运算不仅基础, 而且很自然, 因为这些数是一个一个累加而成的, 即2=1+1, 3=2+1, 4=3+1, 以此类推。正如强壮的纯种马“天生就会跑”一样, 自然数也是“天生就会加”。

上小学的时候, 我们先是（几乎）无休止地把数加起来, 然后做相反的运算, 或者说是逆运算：减法。接下来就是乘法和除法, 这期间似乎没有一天停止过训练。经过多年这样的教育, 孩子们对算术运算的掌握程度仍然参差不齐, 尽管花7.95美元买来的计算器眨眼工夫就能毫无偏差地完成计算, 但人们并没有因此而放弃这种训练。遗憾的是, 对大多数年轻人来说, 做算术题已变成了操练和苦差事的代名词。

然而, 在不久之前, 算术一词不仅包含加减乘除这些基本运算, 而且还包含整数的一些较深层次的性质。例如, 欧洲人所说的“高级算术”实际上就是“更难的算术”的意思。今天更贴切的术语是数论。

尽管这门学科涉及的内容博大精深, 但是它多少还是以质数概念为主的。如果一个整数比1大, 而且不能写成更小的整数之积, 那么这个整数就是质数。因此, 前十个质数是2, 3, 5, 7, 11, 13, 17, 19, 23, 29。这其中任何一个数都没有除了1和它本身之外的正整数因子。

爱争论的读者也许会说17可以写成两个数的积, 例如或者。但是这些情况下的因子不都是整数。必须记住的是, 数论中的主角是由整数来扮演的, 整数的那些更复杂、更远房的“表亲”——分数、无理数和虚数, 都只能委身幕后, 在一旁干着急。

如果一个比1大的整数不是质数, 也就是说, 如果一个数有除了1和它本身之外的整数因子, 那么我们就称它为合数。或者就是合数的例子。我们认为整数1既不是质数也不是合数——原因很快就会揭晓。因此最小的质数是2。

使这些概念形象化的一个简单且常用的方法, 就是想象必须排成矩形的一块块正方形地砖。如果有12块这样的地砖, 我们就有很多不同的方法把它们排成矩形, 如图A-1所示。当然, 这是因为, 或者, 或者（这里我们不区分和, 因为在两种情况下, 最终地板的形状相同, 只不过一个是对另一个的旋转）。同样, 48块地砖能够产生5种不同的排列方案, 其对应的分解方案是。

图A-1

如果是7块地砖, 我们有且只能有一种方案, 即, 如图A-2所示。如果有人非要用7块地砖来铺一间房, 那么这间房子一定是又窄又长的。根据这个例子我们可以说, 如果一个整数只有一种分解方案, 那么这个数就是质数。如果一个整数有多种分解方案, 那么这个数就是合数。

图A-2

质数虽然是高级算术的核心, 但它们也是导致数学深奥难懂的根源之一。理由很简单：尽管整数是通过加法运算逐一构造出来的, 但质数和合数的问题向数学中引入了乘法。数论之难（当然, 还有之美）, 就在于数学家试图从乘法运算的角度来理解加法运算的结果。

因此, 自然数就像离开了水的鱼一样。它们是加法运算的产物, 却身处陌生的乘法环境之中。当然, 在绝望地放弃整个事业之前, 我们应该回想一下3亿5000万年前。那时候, 鱼的确离开了水, 而且同样是在一个陌生的世界里徒劳无益地翕动着它们的鳃；接着, 这些鱼逐渐进化成两栖类、爬行类、鸟类、哺乳动物和数学家。有时候, 一个新的不利的环境能够造就完全不一样的结果。

如果不是因为算术基本定理（注意, 这里的算术一词使用的是其更广泛的意义）这个著名的结果, 质数也许不会在数论中占据中心位置。算术基本定理, 顾名思义, 就是整个数学中最基本、最重要的一个命题, 其内容如下。

算术基本定理：任何正整数（1除外）都能够用一种方式且只能用一种方式写成质数之积。

这个论断是一把双刃剑：首先, 我们可以把任意的整数表示成质数的积；其次, 只有一种表示方式。这必然引出这样的结论：质数是乘法的基本元素, 所有整数都是由这些基本元素构成的, 质数的重要性不言而喻。质数的角色与化学元素的角色类似, 因为正像任何自然化合物都是元素周期表中的92种（或者100多种, 其中包括在实验室中制造出来的元素）自然元素的某种组合一样, 任何一个整数都可以分解成它的质因数之积。我们称为水的化合物分子（）可以分解成两个氢原子和一个氧原子。类似地, “化合数”（即合数）45可以分解成两个质因数3和一个质因数5之积。模仿水的化学记法, 我可以把45写成, 然而数学家更喜欢指数形式。

但是, 算术基本定理不仅给出了质数分解。同等重要的是, 它能够确保这种分解的唯一性。如果一个人确定92365的质数分解为, 那么他的同行, 无论在隔壁房间还是在其他国家工作, 无论是在今天还是在1000个世纪之后, 必定给出完全相同的质数分解。

这令数学家非常满意。同样, 下面的情况也令化学家感到满意：当一名化学家把一个水分子分解成一个氧原子和两个氢原子时, 其他化学家绝不可能把这个水分子分解成一个铅原子和两个钼原子。如同化学元素一样, 质数不仅是基本元素, 而且是唯一的基本元素。

有必要提一下, 我们希望因子分解具有唯一性, 所以我们把1从质数中排除。这是因为, 如果把1归类为质数, 那么数14可能的质数分解是以及不同的质数分解, 。质数因子分解的唯一性不复存在。所以数学家认为给1一个特殊的角色会更好些。它既不是质数也不是合数, 被称为单位。

面对一个正整数, 数学家可能希望确定它是质数还是合数, 当它是合数时, 接下来就要寻找它的质因数。有时候, 这个问题很简单。任何一个偶数（大于2）显然不是质数, 因为它有一个因子2；任何一个个位是5（大于5）或0（非0）的整数也是合数。除此之外, 确定质数性质问题就相对比较困难。例如, 谁能确定数4 294 967 297和4 827 507 229}哪个是质数, 哪个不是质数吗？[1]

19世纪的数学家卡尔 • 弗里德里希 • 高斯（1777—1855）也许是他那个时代最伟大的数论学家, 在1801年的一部杰作《算术研究》中, 他非常简洁地描述了这个问题：

从古希腊人到现代数论学家, 在2400多年间, 数学家们义无反顾地扑向这一类问题, 就如同飞蛾扑火, 前仆后继。沿途众学者们创造出关于质数的很多猜测。其中一些已经解决, 另一些至今仍悬而未解, 而且有相当数量的问题还没有得到解决。

例如, 法国神学家马林 • 梅森（1588—1648）在1644年提出了一个很有趣的问题。梅森在17世纪科学史中扮演了重要的角色, 这不仅是因为他对数论做出了诸多贡献, 而且因为他扮演了数学家之间的信息交换平台的角色。当学者们对数学现状比较关心或者对某个问题感到困惑时, 他们就写信给梅森, 而梅森要么知道其答案, 要么把他们直接引荐给某位可能做出解答的权威。在科学会议、专业期刊以及电子邮件出现之前的那个时代, 这样的信息交流通道的价值是无法估量的。

梅森痴迷于形如的数, 即比2的某个幂少1的数。今天为了纪念他, 我们把这样的数称为梅森数。显然, 所有这样的数都是奇数。更重要的是, 它们之中有一些是质数。

梅森马上发现, 如果是合数, 那么也一定是合数。例如, 如果, 那么这个梅森数是一个合数（因为12是合数）；对于合数, 同样不是一个质数。

然而, 当幂是质数时, 情况就不是这么显然了。设, 产生的“梅森数”分别是。但是, 如果用质数作幂, 我们得到；而这个数是23与89的积, 因此它是一个合数。梅森充分认识到, 是一个质数不能保证也是一个质数。事实上, 他断言：“对2与257之间的质数而言, 使是质数的质数只有。”[3]

遗憾的是, 梅森前辈的结论有不合理和缺失的地方。例如, 他漏掉了数是一个质数。另外, 有人已经证明根本不是一个质数。1876年爱德华 • 卢卡斯（Edouard Lucas, 1842—1891）证明了这一事实, 他使用了某个论据证明了这个数是合数, 但这个论据不是很直接, 因为它不能很明确地展示出任何因子。因此在某种意义上, 的故事仍然很不完整, 但是对这一故事的最后部分值得再说两句。

那是在1903年, 背景是美国数学学会的一次会议。哥伦比亚大学的弗兰克 • 纳尔逊 • 柯尔（Frank Nelson Cole）是日程安排的演讲者之一。当轮到他上台时, 柯尔走到会议室的前台, 静静地把2与它自己相乘67次, 再减去1, 得到一个巨大的结果147 573 952 589 676 412 927。在见证了这样沉默无语的计算之后, 迷迷糊糊的观众接下来看到柯尔在黑板上写道

他仍旧沉默地计算着。这个积不是别的数, 正是

柯尔落座。他完美地演出了一幕哑剧。

在座的观众目睹了把梅森数明明白白分解成两个大因子的过程, 他们一度像柯尔一样哑口无语。随后, 他们送上了热烈的掌声, 并站起来向他祝贺！希望这掌声能够温暖柯尔的心, 因为后来他承认他为此已经计算了二十年。[4]

尽管有了柯尔的因子分解, 但梅森数仍然是质数的源泉。几乎可以肯定, 当一家报纸宣布找到一个新的“最大”质数时, 它一定是的形式。例如1992年, 已知最大的质数是, 这是一个有227832位的庞然大物。[5]但如何确定哪些梅森数是质数, 哪些是合数, 仍旧是数论的一个未解问题。

梅森数出现在另一个质数故事中。在19世纪中期, 法国数学家德 • 波利尼亚克（De Polignac）声称：

例如, 15可以写成, 而, 。尽管德 • 波利尼亚克没有声明已经对他的猜测给出了证明, 但是他表示已经检验了300万以内的所有奇数。

因为2的任意幂都不可能在它的质因数分解里有奇数, 所以这样的幂可以说成是所有数中最纯粹的偶数。德 • 波利尼亚克的陈述说明任意奇数可以由一个质数（这个基本的构造块）加上一个纯偶数的2的幂构建而成。这是一个大胆的陈述。

而它也绝对是错误的。如果德 • 波利尼亚克真的花了足够的时间对他的猜测做了上百万次的检验, 那么我们只能同情他, 因为一个相对较小的梅森数127就反驳了他的结论——我们没法把127写成2的幂加上一个质数。如果我们用各种可能的方式把127分解成2的幂和一个余数, 就会发现这个余数不是质数, 因此, 他显然错了。

（因为大于127, 所以我们无须再进一步计算了。）今天, 德 • 波利尼亚克的猜测已被扔入数论的垃圾堆之中, 因为他没有注意到就在眼前的一个反例。就如同19世纪尝试扑翼飞行的人一样, 他野心勃勃的主张从来就没有飞离地面。

我们已经把化学元素的唯一分解与整数的唯一质数分解对应起来。尽管这种化学类比很有帮助, 但是仅就一点它就失效了, 因为历史上所有化学家的全部实验室的工作成果也不过提供了区区100多种元素, 而质数是无穷的。虽说元素周期表能够占满一面墙, 但是类似的质数表则需要一面可以无限延伸的墙。

质数无穷性的最早证明是古希腊数学家欧几里得（大约公元前300年）给出的, 这一证明出现在他的巨作《几何原本》之中。[7]下面我们给出他的证明的一个修改后的版本, 但是它仍然保留了原来证明的独特的优美之处。

为了能够理解这一推导过程, 需要两个数论的预备结果, 它们都不是很难。第一个是对于任意一个整数, 的两个倍数之差仍然是的倍数。用符号表示, 如果和是的两个倍数, 那么也是的倍数。例如, 70和21都是7的倍数, 那么它们的差也是7的倍数；同样, 216和72都是9的倍数, 那么它们的差也是9的倍数。这里没有给出这一事实的一般证明, 但是证明过程真的很简单。

第二个预备结果也同样非常初等。它说的是任意合数至少有一个质因数。同样, 我们还是用例子加以说明。合数39有质因数3, 合数323有质因数17, 合数25有质因数5。欧几里得在他的《几何原本》第七卷的命题31中对这个定理给出了一个非常巧妙的证明。

除此之外, 证明质数无穷性的必备知识是能够理解利用矛盾的证明方法。这种证明方法需要我们理解最基础的逻辑二分法：一个陈述或为真或为假。

论证一个命题为真的一种方法就是直接对它加以证明。这是显然的（也是一种直白的传统方法）。还有一种不同但同样显然的方法就是所谓的反证法, 这种证明是假设陈述为假, 然后从这一假设出发, 利用逻辑规则去得出不可能的结果。这样一个结果的出现表明在整个推理过程中的某个地方出现了错误, 如果我们的推理步骤是正确的, 那么唯一可能出现问题的地方就是最开始的“陈述为假”的假设。因此我们必须驳回这一假设, 上面说的二分法给我们留下唯一的一种可能性：这个陈述一定是真的。不可否认, 这种间接性似乎让人感觉很奇怪, 而这种迂回策略似乎也让人觉得没必要。为了强调这种间接性, 在证明质数无穷性之前, 我们先考虑一个例子。

假设我们要研究既是完全平方数又是完全立方数的数, 如64是和, 729是和。这样的数被称为sqube。我们的目标是要证明下面的定理。

定理　有无穷多个sqube。

证明　这是一个简单且非常直接的证明。我们仅通过观察就知道, 如果是一个整数, 那么有是一个完全平方数, 而且是一个完全立方数。所以我们通过观察得到无穷多的sqube

显然这个过程可以无限地持续下去, 因为每选择一个不同的都能产生一个新的不同的。因此sqube的无穷性就直接被证明了。

遗憾的是, 为了证明质数的无穷性, 我们却没有这样直接的选择。无论是欧几里得还是其他人都没有像我们从出发构建出sqube那样构建出质数。我们不能采用正面进攻, 而是必须采用一种非直接的进攻方式——反证法, 这一方法更巧妙、更聪明, 而且更优美。事实上, 这种证明通常充当数学敏感度的试金石：那些对数学上瘾的人觉得它令人激动得流泪, 而那些没有此瘾的人则认为它令人头痛得流泪。我们让读者自己做个判断吧。

定理　存在无穷多个质数。

证明　（反证法）假设只有有限个质数, 并假设它们被记为。这个集合可能包含400个或400000个质数, 但是我们假设它把全部质数都包含进来。现在我们开始引出一个矛盾。

把这些质数乘起来, 然后再加1得到一个新数

注意, 因为我们仅有有限个质数, 因此能够把它们按这种方式乘起来, 而无穷多个质数是不能这样乘起来的。显然, 比中任何一个质数都大, 所以与它们都不相同。因为只有有限个质数, 所以我们得出结论不是一个质数。

这表明是一个合数。通过前面的第二个预备结果, 我们知道有一个质因数。因为我们假设构成了世界上的所有质数, 所以的这个质因数一定是其中的某一个。

换句话说, 是质数中某一个质数的倍数。到底是哪个质数无关紧要, 但是为了具体起见, 假设是的倍数。显然积也是的倍数, 因为是其中的一个因子。根据上面提到的第一个预备知识, 与的差还是的倍数。但是我们定义只比这个积大1, 所以这个差是1。

因此我们得出结论：1是（或的任何其他质因数）的倍数。这显然是不可能的, 因为最小的质数是2, 所以1不可能是任意质数的倍数。这里出现了问题。

当我们沿着这一证明返回去的时候, 就会明白唯一可能出现问题的是我们最初假设有有限个质数。因此我们必须拒绝这个假设并通过反证法得出质数的数目必定无穷的结论。证明完毕。

这段完美的推理是初等的, 但其意义深刻。它保证质数是无穷无尽的。在最强大的计算机证明了是质数之后, 我们就能够很得意地说更大的质数, 或者说无穷多个更大的质数仍旧没有发现。即便我们不能够指出那些更大的质数中的某一个质数, 但是没有人认为我们是含糊其词。多亏了逻辑和反证法证明的巧妙, 我们知道了这些质数的存在。

正因为数论含有这些如此简单而美妙的结果, 所以对于很多年轻学者来说, 这是他们进入更高级数学的切入点。美国数学家朱莉娅 • 罗宾逊（Julia Robinson, 1919—1985）就是其中的一个。1970年, 罗宾逊是解决了“希尔伯特第十问题”的三位学者之一。这个问题是数论中一个很难的问题, 自戴维 • 希尔伯特（David Hilbert, 1862—1943）七十年前提出以来一直没有得到解决。在少年时期, 罗宾逊就沉迷于整数的美妙特性之中。“我对整数的某些定理尤其感到兴奋, ”她写道, “我经常在晚上上床之后, 把这些定理讲给康斯坦斯（她的姐姐）听。不久她发现, 每当她不想睡觉时就可以问数学问题来让我保持清醒。”[8]

还有一位匈牙利数学家保罗 • 埃尔德什（Paul Erdös, 1913—1996）在回首一生时说：“当我十岁时, 我的父亲给我讲了欧几里得的证明 (质数无穷性的证明), 从此我就上瘾了。”[9]

埃尔德什在青年时代取得了如此多的学术成就, 因此在社会上受到多方保护。在17岁的年龄, 大多数大一新生只是单纯期望顺利度过青春期, 而埃尔德什却在此时因为给出了两个整数与之间至少存在一个质数的证明而在数学界赢得了声誉。例如8和16之间一定存在质数, 而80亿和160亿之间也一定存在质数。

这似乎不是一个太引人注目的定理。的确, 几乎在一个世纪前, 它已经被一位俄罗斯的数学家切比雪夫（Pafnuty Lvovich Chebyshev, 在数学文献上这个名字的英文有时被拼写成Chebychev、Tchebysheff、Cebysev或Tshebychev, 这应该属于翻译错误而不是因偏爱出现的混乱）证明了。但是切比雪夫的证明非常复杂。埃尔德什的证明令人吃惊的地方是, 它如此简单, 而且出自一位如此年轻的人之手。

这里顺便提一下, 他的定理给出了质数无穷性的另一种证明, 因为它保证2和4之间, 4和8之间, 8和16之间等都有质数。如同我们能够永远把数翻番一样, 质数也一定是无穷的。

这是保罗 • 埃尔德什众多定理中的第一个, 他是20世纪最多产或许也是最古怪的数学家。甚至在这样一个违反常规的行为被视作正常行为的行业中, 埃尔德什也是一个传奇人物。例如, 这位年轻人受到百般的爱护, 到了21岁, 也就是在给出上面提到的关于质数的定理的四年后, 他才第一次自己往面包上涂黄油。后来他回忆说：“那时我刚到英格兰去学习。有一天, 在用下午茶时, 桌子上放了面包。我实在不太好意思承认我从来没有涂过黄油, 于是我尝试着做。这不太难。”[10]

同样不寻常的是埃尔德什没有固定的住所。他游遍世界各地的数学研究中心, 拎着手提箱到处走, 并且坚信每到一处都会有人留他过夜。由于他不间断地四处游历, 这位漂泊的数学家与很多同行合作, 联合发表了很多文章, 这在历史上无人能及。他就是一条《圣经》谚语的写照：人不能仅靠（涂黄油的）面包活着。

作为回报, 数学界想出了一种出奇的东西来肯定他带来的影响：埃尔德什数。[11]埃尔德什本人有埃尔德什数0；任意与埃尔德什联合发表文章的数学家有埃尔德什数1；没有直接与埃尔德什合作, 但与直接与埃尔德什合作发表过文章的人合作发表过文章的数学家有埃尔德什数2；与有埃尔德什数2的人合作发表过文章的人有埃尔德什数3；以此类推。就如同一棵巨大的橡树一样, 这棵埃尔德什树跨越了整个数学界。

这样, 有了质数、合数、梅森数乃至埃尔德什数, 很显然, 人类对数论的热情没有熄灭的危险。对从高斯到罗宾逊, 从欧几里得到埃尔德什这众多的数学家来说, 数学中没有哪一部分能像高级算术那样美妙、优雅、充满无穷的魅力。

---

[1]641可整除4 294 967 297；另一个数是质数。参见D. 韦尔斯的《奇特有趣的企鹅数字词典》（David Wells, The Penguin Dictionary of Curious and Interesting Numbers）。