包邮经典数论的现代导引

第1章　整除的算法 1.1　自然数的来历 在人类所有的发明中, *古老的无疑是数学和诗歌了. 可以说自从有了人类的历史, 就有了这两样东西. 如果说诗歌起源于农人祈求丰收的祷告, 那么牧人计算家畜的只数便产生了数学. 由此看来, 它们均源于生存的需要. 随着时间的推移, 人类渐渐有了明确的正整数概念: 1, 2, 3, …, 这些正整数的全体被称为自然数(natural number, 有时也包含0), 显然有着天然的或来自自然界的意思. *初, 可能因为这些牲畜的财物是如此重要, 人们在表达同一数量的不同对象时所用的量词也不尽相同. 例如, 在古英语里使用过team of horses (共同拉车或拉犁的两匹马), yoke of oxen (共轭的两头牛), span of mules (两只骡), brace of dogs (一对狗), pair of shoes (一双鞋)等. 慢慢地, 只剩下pair一词较为常用. 至于汉语, 量词的变化更为丰富, 且有许多一直保留至今. 很久以后, 人类才从无数生活经验和社会实践中, 把这样的数(比如2)作为共同性质抽象出来, 这意味着自然数的诞生. 事实上, 它的意义远不止于此, 英国哲学家罗素(Russell, 1872—1970)指出: 当人们发现一对雏鸡和两天之间有某种共同的东西(数字2)时, 数学就诞生了. 而在作者看来, 数学的诞生或许稍晚一些, 即在人们从“3只鸡蛋加上2只鸡蛋等于5只鸡蛋, 3枚箭矢加上2枚箭矢等于5枚箭矢, 等等”中抽象出“3 + 2 = 5”之时. 也就是说, 在我们对自然数实行加法和减法运算以后, 那可能比罗素所定义的要晚上几千年. 当人们需要进行更广泛、深入的数字交流时, 就必须将计数方法系统化. 世界各地的不同民族不约而同地采取了以下方法: 把从1开始的若干连续的自然数作为基数, 以它们的组合来表示大于这些数字的数. 换言之, 采用了进位制. 在不同民族和原始部落中, 使用过的有据可查的基数有2, 3, 4, 5, 8, 9, 10, 12, 16, 20和60等. 如同全才的古希腊哲学家亚里士多德(Aristotle, 公元前384—前322)所言, 由于“绝大多数人生来具有10个手指这个解剖学事实”, 十进制*终被广泛采纳. 当然, 古代巴比伦人发明的60进制仍被保留下来, 作为众所周知的时间单位之间的一种换算. 有人这样推算过巴比伦人的计算方法, 即利用了一只手拇指以外的12个关节和另一只手的5个手指. 至于二进制, 有证据表明, 曾被澳大利亚昆士兰原住民和非洲矮人使用过, 而在三千多年前中国一部古老而深邃的典籍《易经》里, 就已在六十四卦里藏匿了这一奥妙. 接下来是0的出现和记号. 1881年在印度白沙瓦附近(今属巴基斯坦)出土的“巴克沙利手稿”中, 记载了公元前后数个世纪的耆那教数学. 里面出现了完整的10进制数, 包括用实心的点书写的零. 至晚9世纪, 印度人用圆圈代替了实心. 之后, 0连同其他9个数字的记号经阿拉伯人的改造传递到了西方, 然后再次变更并传遍整个世界, 且被讹传为阿拉伯数字. 等到17世纪, 德国数学家、哲学家莱布尼茨(Leibniz, 1646—1716)在他发明可以计算乘除的轮式计算机以前, 已建立起严格的二进制. 他用0表示空位, 用1表示实位, 所有的自然数均可由这两个数表示. 例如, 1=1, 2=10, 3=11, 4=100, 5=101, …. 遗憾的是, 莱布尼茨未能将两者联系起来. 直到20世纪中叶, 匈牙利出生的美国数学家冯·诺依曼(von Neumann, 1903—1957)在为计算机设计的程序中, 作了一系列重要革新, 才用二进制代替十进制, 他也因此被誉为“电子计算机之父”. 对任意整数b>1, b进制早就建立起来了. 可是, 对素数p(定义见1.3节),p进数(p-adic数)却是晚近才有的概念. 1897年, 德国数学家亨泽尔(Hensel, 1861—1941)通过对绝对值重新进行解释, 将有理数的算术用一种不同于实数系或复数系的方法进行了扩展. 如若, 则, 而对其余素数p, . 故在五进制数里, 下列级数是收敛的. 这是因为. 不仅如此, 我们还能求出S的值. 将上式两端同乘以5, 可得 两式相减, 即得, 因此. 但在本书里, 我们要讨论的整数以10进制的形式出现. 在一些东方古国, 都有过从自然界中提取出数的规律的伟大发现, 比如巴比伦人和中国人各自发现了3平方数组, 即我们祖先所称的勾股数或古希腊人所称的毕达哥拉斯数. 在中国*早的数学典籍《周髀算经》(至晚公元前1世纪)里, 记载了西周**个皇帝周武王的弟弟周公(公元前11世纪)与大夫商高关于测量的一段对话, 其中提到 勾广三, 股修四, 径隅五. 《周髀算经》里的勾股定理插图 这应该是现存(3, 4, 5)这组*小的勾股数的首次记录. 虽然现藏纽约哥伦比亚大学的巴比伦泥版书“普林顿322号”历史更为悠久, 但那上面*小的毕达哥拉斯数组却是(45, 60, 75). 周公是孔子*崇敬的人, 《周礼》的作者, 书中提出了“六艺”, 数是其中之一. 在《周髀算经》里, 还叙述了周公后人荣方与学者陈子(约公元前六七世纪)的一段对话: 以日下为勾, 日高为股, 勾股各自乘, 并而开方除之, 得斜至日. 此即勾股定理, 用现代数学语言来表达就是 每一个直角三角形的两条直角边长的平方和等于斜边长的平方. 不过, 西方人将此结论称为毕达哥拉斯定理, 并早已约定俗成了. 一来古代东西方文化和科技交流几乎隔绝, 二来毕达哥拉斯率先给出了证明. 毕达哥拉斯(Pythagoras, 公元前580—前500)是古希腊**个堪称伟大的数学家, 他生活的年代比陈子和荣方略晚. 值得一提的是, 毕达哥拉斯是用诗歌的语言来描述他所发现的**个定理的. 斜边的平方, 如果我没有弄错, 等于其他两边的 平方之和. 毕达哥拉斯出生在地中海东端的萨摩斯岛(今希腊), 曾游历埃及和巴比伦, 后来他在克罗托内(今意大利南方)创办了一个秘密社团, 广收弟子, 形成了所谓的毕达哥拉斯学派, 其影响绵延后世两千多年. 毕达哥拉斯*早认识到在客观世界和音乐中数的重要性, 并提出了“万物皆数”这一哲学命题. 在他和他的弟子们关于自然数的种种发现里面, *有意思的可能要数完美数和亲和数. 许多文明和民族都对自然数有着宗教般的信仰或幻想, 完美数便是其中一个. 所谓完美数或完全数(perfect number)是这样的自然数n, 它等于其真因子的和, 即满足 此处表示d整除n(参见定义1.1). *小的两个完美数是6和28, 这是因为 毕达哥拉斯或许*早研究了完美数, 至迟到公元1世纪, 希腊人已知道第3个完美数496和第4个完美数8128. 毕达哥拉斯和古罗马思想家圣奥古斯丁(Saint Augustinus, 354—430)都认定6是完美无缺的. 甚至《旧约圣经》首卷《创世纪》里也提到, 上帝用6天的时间创造了世界(第7天是休息日). 相信地心说的古希腊人则认为, 月亮围绕地球旋转一圈所需的时间是28天. 在1.3节我们将会了解, 一个偶数n要成为完美数当且仅当它是下列形式 其中p和均为素数. 后者即著名的梅森素数, 也就是说, 有多少梅森素数, 就有多少偶完美数, 反之亦然. 迄今为止, 人们已发现了51个梅森素数, 这也是已知完美数的数量. 另一方面, 既没有人找到哪怕一个奇完美数(如果存在的话, 一定大于), 也没有人能够否定它的存在. 这些使得完美数问题引人入胜, 我们将在1.3节给出上述充要条件的证明, 并在7.3节进行更为细致深入的研究和拓展, 那也是本书*有价值的部分之一. 所谓亲和数或友好数(amicable number)是指这样一对数, 其中的任意一个是另一个的真因子之和. 显然, 完美数与其自身互为亲和数, 因此通常人们只考虑不同的两个数. 毕达哥拉斯找到了*小的一对亲和数220和284, 这是因为 《创世纪》里也曾提到, 雅各送给孪生兄弟以扫220只羊, 以示挚爱之情. 后人为亲和数添加了神秘色彩, 使其在魔法术和占星术方面得到应用. 欧洲中世纪期间, 叙利亚数学家、阿基米德著作的阿拉伯文译者塔比(Thabit, 826—901, 其出生地哈兰, 今属土耳其)认为, 毕达哥拉斯和他的追随者之所以研究完美数和亲和数, 是为了表达他们的哲学观念. 塔比还率先给出了确定亲和数的方法, 他指出, 对任意整数, 若均为素数, 则必是一对亲和数. 当n=2时, 它对应的就是毕达哥拉斯发现的那一对. 遗憾的是, 阿拉伯人并没有用这种方法找到新的亲和数. 而事实上, 有两对只是举手之劳. 直到1636年, 第二对亲和数(17296, 18416)才由有着“业余数学家之王”美称的法国数学家费尔马(Fermat, 1601—1665)找到; 同年, 费尔马的同胞、数学家兼哲学家笛卡儿(Descartes,1596—1650)找到了第三对(9363584, 9437056). 在此之前, 16世纪伊斯兰世界的一位主要的数学家、伊朗人亚兹迪(Yazdi)已找到这对. 这两对分别对应于塔比数组n=4和n=7的情形. 到了1747年, 瑞士数学家欧拉(Euler, 1707—1783)利用自己的方法, 一下子找到了30多对亲和数. 他一生共找到了60多对, 其中一对(10744, 10856)比费尔马所得的还小. 第二小的一对亲和数是(1184, 1210), 这是在1866年, 由一位16岁的意大利男孩帕格尼尼(Paganini)发现的. 欧拉还把塔比的亲和数公式作了推广, 对任意的整数, 若 均为素数, 则必是一对亲和数. 当m=n1时, 此即为塔比公式, 但欧拉的公式只提供了两对新的亲和数, 即当(m,n)=(1,8)和(29,40)时. 迄今为止, 人们已经发现的亲和数远比完美数要多, 有1200多万对. 可是, 无论亲和数还是完美数, 我们都不知道是否有无限多对(个). 1955年, 匈牙利数学家爱多士(Erds, 1913—1996)证明, 亲和数在自然数中的密度为0. 而假如亲和数有无限多对, 我们想问, 亲和数对两数之比是否趋向于1? 1.2　自然数的奥妙 在自然数中间存在着无穷无尽的奥妙, 这使得研究整数性质的数学分支——数论充满了魅力, 吸引了古往今来不计其数的数学天才和业余爱好者. 有着“数学王子”美誉的德国数学家高斯(Gauss, 1777—1855)曾谈道:“任何一个花过一点功