01 如何不去考虑数

我们已经习惯看见写下来的数，也习惯从中提取出某种意义。然而，一个数字（比如6）同它所代表的那个数并不是同一个东西。就像在罗马数字中，我们会把六[1]这个数写作Ⅵ，但是我们意识到这与用现代记号写下的6代表了同一个数，它们都对应6根算筹（IIIIII）的那一类集合。让我们先花一点点时间考虑一下表示和思考数的不同方法吧。

有时候，我们会在无意识的情况下解决一些关于数的问题。例如，假设你正要组织一次会议，想要保证每个人都拿到一份议程。你可以将每份议程逐个标上与会者的名字首字母。只要议程没用完，你就知道份数是足够的。这样你就解决了问题，而没有用到算术或者直接数数。这里数依然在发挥作用，它们使我们得以将一个集合同另一个集合进行精确比较，即便这两个集合的组成元素有着截然不同的性质。就像上述例子里，一个集合包含了人，而另一个集合则由纸张组成。数让我们可以比较两个集合的大小。

在上例中，你不需要费神去数有多少人将要出席，因为没有必要知道—你的问题是判断议程的份数是否不少于出席人数，而具体的数目无关紧要。但如果你要为15个人买午饭，你就需要真正数一数人数了。当然，要计算这顿饭的全部开销，就一定得使用算术，哪怕是用计算器求和来得出精确的数值。

现代数字系统让我们能以一种有效且统一的方式来表示数，这方便我们将一个数和其他数做比较，以及在计数问题中进行所需要的算术操作。日常生活中，我们在所有的算术中使用十进制，换句话说，我们十个十个地数数。这么做的原因是偶然的：我们恰好有十根手指。需要明确的是，让数的系统如此有效的原因并非我们对底数（base number）的选择，而是我们在数的表示中使用了位值进位法（positional value），即一个数字的值取决于它在数字串中出现的位置。比如，1984是4份1加上8份10，再加上9份100，再加上1份1000的缩写。

当我们把数写成特定形式的时候，我们想表达什么？理解这一点很重要。在这一章，我们将要考虑数代表了什么，发现不同的计数方法，认识一类非常重要的数（素数），并且介绍一些找到它们的简单技巧。

人们是如何学会数数的

这里值得我们花上一点时间来弄明白构造一套计数系统所需的两个重要阶段。让我们以十进制为例：我们会给孩子们规定两项基本任务，背诵字母表和学习数数。这两个过程表面上看是相似的，却有着本质的不同。英语基于26个字母，每个字母对应一个发音，供我们念单词用。总的来说，英语发展的结果是这门语言可以用26个符号来书写。如果不给字母表一个顺序，我们就没法编纂字典。然而，字母表并没有天生的排序。我们所采用并且都曾在学校吟诵过的a，b，c，d，…看起来实在很随意。诚然，常用的字母一般出现在字母表的前半部分，但这也只是大致的规律，而非铁律。比如，常用字母s和t就很晚才被点名。相比之下，用以计数的数，或者叫自然数[2]（natural number），如1，2，3，…一旦出现便已经排好了序。例如，符号3用来表示跟在符号2后面的那个数，因此必须列在2的下一位。在一定程度上，我们可以给每个数赋予一个新的符号。但为了处理永无止境的数，我们迟早得放弃不断引入新名字，而只能开始把它们按批次分组。按10个来分组代表发展出了一个坚实的数字系统的第一阶段，这个方法在古今中外几乎都是一样的。

但是各个文明在细节上却有很多不同。罗马系统除了按10分组外，同样也喜爱用5分组。他们使用特殊符号V和L，来分别代表5和50。古希腊系统则直接使用了十进制。他们用某些字母来代表数，有时候加上上画线来告诉读者这个符号应被解读为一个数，而不是平常的词语中的一个字母。比如，π代表80，而γ代表3，于是他们可以写下πγ来代表83。与我们的现代数学符号相比，它看起来好像同样高效，也确实相差不多，但它们是不一样的。希腊人仍然没能运用进位系统，因为他们每个符号的值都是固定不变的。具体来说，γπ还是只能表示同样的数——3＋80。而如果我们将83的数字顺序颠倒，会得到一个不同的数——38。

在印度-阿拉伯数字系统（Hindu-Arabic number system）中，数的第二个阶段得以实现。其主要思想是让一个符号的值依赖于它在字符串中出现的位置。这使我们可以只使用一套固定的符号来表示任何数。我们最终选择了由0，1，2，…，9这十个数字组成的数字系统。这套常用的数字系统被称为十进制（base ten）。当然，我们完全可以用一个更大或者更小的基本符号集来建立我们的数字系统。我们甚至可以使用两个数字去建立数字系统，比如0和1。这被称为二进制（binary system），在电脑运算中经常被用到。需要明确的是，具有革命性的不是对底数的选择，而是这样一种思想：使用位置来传达额外的信息，从而确定数的值。

例如，当我们写下一个数，比如1905，每个数字的值取决于其在数字串中的位置。这里有5份1，9份100（即10×10），以及1份1000（即10×10×10）。符号0被用作一个占位符，这很重要。在1905这个例子中，十位并没有贡献，但我们不能忽略它而只写作195，因为那代表了一个完全不同的数。事实上，每个数字串都代表了一个不同的数，正因为如此，海量的数才可能用很短的字符串表示出来。比如，用不超过10位的字符串便可以给地球上每个人分配一个独特的号码，这样，这个巨大集合中的每一个体都有了个人代号。

不同的古代社会在书写数时使用了不同的底数，但这远不能弥补一个事实，即几乎所有文明都缺少一套真正的进位制系统，更谈不上使用零来作为占位符。在古代的所有民族中，巴比伦文明的数字系统是最为接近位值进位法的系统，考虑到他们的古老程度，这实在让人赞叹。然而，他们没有彻底拥抱那个不那么自然的数—0。比如，我们用0来区分830和83，而古巴比伦人刻意回避了在数字串末尾使用这样一个表示空的符号。

意识到0确实是数，这需要跨越一个概念上的障碍。0确实并非一个正数，但它依然是一个数，如果不将它以一种完全自洽的方式吸纳进来，我们的数字系统就是残缺不全的。约公元6世纪，印度迈出了这关键的最后一步。现代的数字系统被称为印度-阿拉伯数字系统，正因为它是从印度经由阿拉伯传到了欧洲。

有或没有小数的生活

将以10为底的位值进位法思想推广到非整数部分，就可以得到我们现在所熟知的完整十进制数字系统。比如，当我们写下3.14的时候，小数点后的1表示一份。类似地，后面的4代表。这种两位小数形式的数我们已经很熟悉了，因为我们在处理十进制货币的时候，最小单位—取决于具体情况—不是美元、英镑或欧元，而是便士或美分。后者是其主币的百分之一。十进制小数算术是以10为底数的系统的自然推广。在实际应用中，它代表了执行普通加法运算的最佳方法。虽然有这些优点，十进制方法的诞生却并非一蹴而就。一开始它只在数学精英们的小圈子里得到运用，直到16世纪后半叶才最终进入商业结算并被大众使用，甚至在这之后，按照非十的幂次来组织数的方法依然在用。英国直到1971年才采用了十进制货币。而部分英语地区依然顽固地使用码、英尺和英寸[3]。若要捍卫英制单位，我们可以辩解说它们是根据人体的尺寸量身定制的。我们的手大约有6~8英寸长，而我们的身高大约是5~6英尺。我们将周围的物体制作得与我们的身体尺寸相似，自然可以方便地用英尺和英寸来丈量它们。但是，如果让1英尺等于10英寸，整个系统也可以很好地运作，还更方便我们用以10为底数的计算方法来处理问题。

为一个数字系统选底数有点像为一张地图选比例尺，这并非基于对象内在的性质，而是类似于赋予它一个坐标系，作为控制用的工具。我们对底数的选择本质上是任意的，面对自然数集1，2，3，4，…的时候，排他性地使用底数10让我们戴上了有色眼镜。只有掀起这层面纱，我们才能面对面地看清数到底是什么。当我们说起一个数，例如四十九，人们的脑海中都会浮现出两个字符4和9。某种程度上，这对我们谈论的那个数来说不太公平，因为我们毫不犹豫地将四十九转换成了(4×10)＋9。我们也可以同样轻松地用另一种方式来诠释这个数：49=(4×12)＋1。实际上，在十二进制中，四十九正是被写作41，这里数字4代表4份12。当然，四十九这个数最显著的特征是它是7×7的积。这一特点在七进制中十分明显，此时四十九这个数会被表示为100，这里的1代表一份7×7。

我们一样有权利为我们的数字系统选择另一个底数，例如12。玛雅人使用了12，而巴比伦人用了60。某种程度上，60是一个计数基底的好选择，因为60有很多因数，它是可以被1到6之间所有数整除的最小的数。不过，选择一个60这样相对大的数作为底数也有缺点，就是需要引入60个不同的符号来表示从0～59的所有数。

如果一个数是另一个数的整数倍，则称第二个数是第一个的因数[4]（factor）。比如，6是42的一个因数；但8不是28的一个因数，这是因为28含有三个8还余4。数字系统的底数拥有众多因数会是一个很方便的性质。这就是为什么相对于我们的数字系统来说，底数选择12也许比10更好，因为12的因数是1，2，3，4，6和12，而10只能被1，2，5和10整除。

数字系统的有效性，加上我们对它高度熟悉，给了我们一种虚假的信心，同时也带来了一定的局限。我们会更愿意使用单个的数，而非一个算术表达式。例如，大多数人情愿谈论5969，而不是47×127，即使这两种表示方式代表了同一个东西。仅在“求出最终答案”5969之后，我们才觉得我们“有”了这个数，从而可以正视它。然而，这里面包含着一丝虚妄的成分，因为我们只是将这个数写成了多个10的几次幂的和。若将这个数分解为一系列因数的乘积，从这个等价形式中，我们反而可以更好地推断它一般意义上的构造和其他的性质。确切地说，5969这个标准形式能让我们将它和其他以同样方法表示的数直接比较大小，但并不能展现出这个数的全部特性。分解为因数的形式可能有用得多。在第4章中，你会发现其中的一个原因，即一个数的十进制表示可能掩盖了关键的因数。

古人比我们多拥有的一项优势是，他们并未被十进制的思想所束缚。谈到数的规律时，他们会自然地想到一个数可能拥有或缺乏某些特殊的几何性质。比如，10和15这样的数是三角形数（triangular number）。这可以通过图像展现在我们面前，正如十瓶制保龄球中排成三角形的球瓶，以及斯诺克台球中15个红球摆成的三角。但如果只用十进制展示这些数，这样的画面就不会出现在我们眼前。我们要放下十进制的思维定势，告诉自己只有从很多不同角度来思考数，才能重新获得古代人天然就拥有的自由。

这样，把我们自己解放出来之后，我们可能会选择重点关注一个数的因数分解（factorization）——把数写成一些更小的数的积。因数分解揭示了一个数内部构造的相关信息。通常，我们仅将数看作科学和商业的仆人。如果我们花一点点时间专门研究数本身，而不与其他任何事物做关联，就能发现很多原来隐藏着的信息。单个数的性质可能会在自然界中以有序的模式展现出来，这比单纯的三角形或方形来得更微妙，比如，向日葵螺旋形的头状花序代表的斐波那契数。我们将在第5章中介绍这种类型的数。

素数数列概览

数的荣耀中有一项是如此显而易见，以至于很容易被忽视——它们每一个都是独一无二的。每个数都有自己的结构——如果你喜欢的话，可以称之为个性。单个数的个性非常重要，这是因为当一个特定的数出现时，它的特征会反映在它所描述的集合的结构中。当我们执行加法和乘法这些基本的数的运算时，数之间的关系也会显现出来。显然，任何比1大的自然数都可以表示成更小的数的和。但是，当我们开始将数相乘，我们很快注意到有些数从来都不会在我们得到的乘积里出现。这些数就是素数[5]（prime number）。它们代表了乘法的构成要素。

一个素数是一个像7，23或103这样的数。它有且仅有两个因数——1和它本身。我们并不把1看作一个素数，因为它只有1个因数。那么，第一个素数便是2。这也是仅有的偶素数。接下来的3个素数3，5和7都是奇数。大于1而又不是素数的数称为合数（composite number），因为它们由一些更小的数复合而成。数4=2×2=22是第一个合数；9是第一个奇合数，9=32也是一个平方数（square number）；6=2×3是我们第一个真正意义上复合的数，因为它由两个不同的大于1的因数复合而成。而8=23是第一个立方数（cube number），立方数是指等于某个数的3次幂 的数[6]。

紧接着个位数的是我们选择的底数10=2×5，它本身就是特殊的，而且还是三角的，因为10=1＋2＋3＋4 （回想一下十瓶制保龄球）。接下来我们有一对孪生素数（twin primes）11和13，它们是由12隔开的两个相邻的奇数，且同为素数。考虑到数值的大小，12显得有很多因数。的确，12是第一个所谓的盈数[7]（abundant number），因为它的真因数（proper factor）——严格小于它自身的因数——之和超过了这个数本身： 1＋2＋3＋4＋6=16。数14=2×7可能看起来并没有什么特别的，但这实在是一条悖论，作为第一个不特别的数本身就是一件特别的事。到了15=3×5，我们又遇到了一个三角数，并且它是第一个等于两个真因数之积的奇数。数16=24不仅是一个平方数，还是第一个四次幂数（在1以后），这使得它十分特别。17和19是另一对孪生素数。对于18和20，以及更多数的独有性质，我就留给读者朋友自己去观察了。对每一个数，你都可以说它是特别的。

回到素数，它们中的前20个是：2，3，5，7，11，13，17，19，23，29，31，37，41，43，47，53，59，61，67，71。

显然，在数列的开始部分，素数是十分常见的，因为小的数没有多大可能会有因数分解。在这之后，素数越来越稀少。比如，只有一组连续3个奇素数：3，5，7。这三者的组合是独一无二的，因为每3个奇数就会出现1个3的倍数，所以这种情况再也不会发生。此外，素数出现频率减少的过程是十分松散的，还非常不规律。比如，30～40之间只有两个素数，即31和37，但刚过100就会有两个“相继的”孪生素数对，即101，103和107，109。

素数在数千年来一直深深吸引着人们[8]，因为它们无穷无尽（我们在下一章会证明这个说法），在自然数中现身的方式又神出鬼没。它们性质中神秘莫测的这一面在现代密码学（cryptography）中被加以运用，来保护互联网上的机密信息。这将是第4章的话题。

素性检验：素数整除性测试

为了找出不大于某个数（比如100）的所有素数，最容易想到的方法是把所有数写下来，再寻找并画掉里面的合数。基于这一思想的标准方法叫作埃拉托斯特尼筛法[9]（Sieve of Eratosthenes）。方法如下：首先圈出2并画掉列表里2的倍数（即其他偶数）。然后回到开始，圈出第一个尚未被画掉的数（即3），画掉剩下数表里它的所有倍数。重复这一过程足够多遍，剩下没有被画掉的就是素数。即便它们中一些被圈出来了，而另一些没有。例如，图1展示了对不大于60的数运用筛法的过程。

图1 素数筛：没有被画掉的数即为60以内的素数

你怎么知道什么时候该停止筛选呢？重复这一过程，直至圈到一个数，大于整张表中最大数的平方根。比如，当你在不大于120的数中筛选素数时，需要筛掉2，3，5和7的倍数。接着当你圈出11，就可以停下了，因为112=121。此时，你已经圈到了第一个大于你的最大数（这里是120）的平方根的数，剩下的素数虽未被触及，但所有的合数都已经被画掉，它们都是2，3，5或7的倍数。

不难看出为什么列表中最大数n的平方根决定了需要筛选的遍数。任何列出的合数m都至少有一个素因数，它最小的素因数必小于n的平方根，因为两个或两个以上大于的数的积大于n（并且因此也大于m）[10]。

素性问题的另一面是：任一给定数n是素数还是合数。为了确定这一点，我们可以用小于的素数逐个除n，如果n不能被所有这些数整除，则其为素数，否则不为素数。鉴于这个原因，对于小素数，如2，3，5，7，…了解一些简单的整除性测试方法会很便捷。下文将介绍一些简单的方法。

检测能否被2或5整除很容易，因为这两个素数是我们的底数10的素因数。要看出这一点，你只须查看待检数n的最后一位：当且仅当个位为偶（即0，2，4，6或8）时n可以被2整除，当且仅当n最后一位为0或5时它含有因数5。不管数n有多少位，判断n是否为2或5的倍数，我们都只须检查最后一位。对于不能整除10的素因数，我们需要多做一点工作。尽管如此，仍然有一些整除性测试方法，比计算完整的除法更快捷。

一个数能被3整除，当且仅当其各位数字之和能被3整除。例如，数n=145 373 270 099 876 790的各位数字之和是87，而87=3×29，因此n可被3整除。当然，我们还可以将这个测试应用于数87，然后继续在每一阶段都求出各位数字之和，直到结果显而易见。对于给出的例子这样做，可以得到以下数列：

145 373 270 099 876 790→87→15→6=2×3。

你会发现，这里列出的所有整除性测试方法都如此快捷，你可以相对轻松地处理有几十位的数，甚至比手持式计算器能处理的最大的数还要大上数十亿倍。

下面要给出不大于20的剩下的所有素数的整除性测试方法，因为它们都属于同一个类型。虽然它们成立的原因不那么明显，但是这些方法应用起来都很简单。即便这里没有收录论证，想证明它们的正确性并不是特别困难。

让我们从给定一个数n是否能被7整除开始。将n的最后一位数字乘以2得到一个数，n移除最后一位数字之后的结果再减去这个数。当n是7的倍数时，新的数也恰好会是7的倍数。我们重复这一过程，直到结果变得显然。例如，设n=3465，5乘以2得10，因此我们从346减去10，得336；接着再做一次，将6乘以2得12，从33减去12得21=3×7，因此n可以被7整除。如果你忘记了7的乘法表，我们可以再次进行，从2中减去2倍的1得0，而0可以被7整除，因为=0。（可以用0除以一个非0的数，但反过来的话——除以0则没有意义。）甚至大如好几千万的数也可以用这个方法简单地处理。在本例和之后的例子中，我们仅仅列出算法（algorithm）在每个阶段输出的数。算法是指用来解决一类特定问题的一个机械的过程。正如我们这里用到的方法：

n=27 916 924→2 791 684→279 160

→27 916→2779→259→7。

因此n可以被7整除。每执行一次指令循环，我们都至少能减少一位数，因此执行循环的次数大约与初始数的长度相同。

为了检测n是否有因数11，将原数的最后一位移除，再从新数中减去原数的最后一位，依此重复。比如，我们的方法揭示了下面这个数是11的倍数：

4 959 746→495 968→49 588

→4950→495→44=4×11。

检测能否被13整除，将原数最后一位移除，再用新数加上原数最后一位的4倍，接着用类似于7和11的方法，不断重复。比如，13是下面这个数的一个素因数：

11 264 331→1 126 437→112 671

→112 71→1131→117→39=3×13。

接下来是17和19。对于17，我们将原数最后一位移除，再用新数减去原数最后一位的5倍，重复操作直到可判断整除性；对于19，我们将原数最后一位移除，再用新数加上原数最后一位的2倍，重复操作直到可判断整除性。例如，我们来检测18 905是否能被17整除：

18 905→1865→161→11，

因而它不是17的倍数。但对于19，整除性测试给出了另一种结论：

18 905→1900=100×19。

拥有了这一组测试，你现在就可以检查不大于500的所有数的素性，因为232=529超过了500，因此19是你需要考虑的最大的素因数。例如，为了确定247的性质，我们只需要检查它是否能被不大于13的素因数整除，因为下一个素数的平方，172=289超过了247。通过对13的测试，我们发现247→(24＋28)=52→13，这是一个13的倍数(247=19×13)。

素数相乘可以得到无平方因数的数（square-free number），要想构造关于这些数的整除性测试，可以叠加并行其素数因子的整除性测试。比如，对于 42=2×3×7，一个数n能被42整除，当且仅当n可以通过2，3和7的三项整除性测试。但是，对于那些有平方数因数的数，像9=32，则不能由此得到。顺便说一句，9是n的因数，当且仅当9也是n的各位数字之和的因数。

你也许会问：数千年以来，那些聪明的数学家们难道还没有想出更好、更精妙的检测素性的方法？答案是有的。2002年，我们发现了一个相对快速的判断一个给定的数是否为素数的方法。不过，如果给定的数恰好是一个合数，那么这个所谓的“AKS素性测试”（AKS primality test）并不能给出该数的因数分解。虽然原则上说找到一个给定数的素因数的问题可以通过试错来解决，但实际操作中，这对于很大的整数依然难以实现。正因为此，它构成了很多互联网加密方法的基础。我们会在第4章回到这个话题。在那之前，我们会在接下来的两章中更近距离地认识一下素数和因数分解。

[1]　这里用中文数字“六”，强调的是“六”这个数本身的概念，下同。—译者注。如无特殊说明，以下注释均为译者注。

[2]　我国的自然数包含0，而本书所说的自然数不包含0。

[3]　1码=3英尺=36英寸。

[4]　或称因子、约数，英文也可以写作divisor。

[5]　英文也可以写作prime。

[6]　这里指的立方数从2的立方开始，因为1=13。

[7]　又称丰数或过剩数。

[8]　最近的例子是孪生素数猜想，传奇美籍华裔数学家张益唐在2013年取得重大进展，引起轰动。

[9]　又称埃氏筛或素数筛，简称筛法。埃拉托斯特尼（公元前276——公元前194），古希腊数学家、地理学家。

[10]　当解释有关任意数的性质的时候，数学家们会用符号为讨论的对象赋予名称。对于数，这些名字通常都是小写字母，如m和n；两个数的积m×n经常简写为mn。——作者注