中国古代数学著作,关于中国剩余定理的数学探讨

橘子网 3,509 0

中国古代数学著作《孙子算经》、《数书九章》、《续古摘奇算法》、《算法统宗》等,这些是古代中国人对数学研究的智慧结晶,也是令中国人值得骄傲的数学成果。

在中外几乎每一本基础数论的教课书中,都会介绍一个被称之为“中国剩余定理”(Chinese Remainder Theorem)的知识。在我的印象里,自己是在小学四五年级的时候接触到这个知识的,并知道如何去应用它,但要等到初中后才真正明白其原理。中国剩余定理是中国古代史上最完美和最值得骄傲的数学成果,它是中国对世界数学思想史的重要贡献。但很遗憾,现在的孩子大部分都已经不学这部分知识。距我当年学习这部分内容已经近三十年了,我不知道我们的数学教育到底出了什么问题。

那么,今天我们就来了解和学习一下这个数论中的著名定理“中国剩余定理”。

第一部分:问题的起源

中国剩余定理起源于我国南北朝时期的数学著作《孙子算经》,因此又名“孙子剩余定理”。

中国古代数学著作,关于中国剩余定理的数学探讨

《孙子算经》,中国南北朝数学著作,《算经十书》之一。全书共分三卷:上卷详细的讨论了度量衡的单位和筹算的制度和方法;中卷主要是关于分数的应用题,包括面积、体积、等比数列等计算题,大致都在《九章》中论述的范围之内;下卷对后世的影响最为深远,如下卷第31题即著名的“鸡兔同笼”问题,后传至日本,被改为“鹤龟算”。下卷第26题“物不知数”为后来的“大衍求一术”的起源,被看作是中国数学史上最有创造性的成就之一,称为“中国剩余定理”。经考证,《孙子算经》的作者与《孙子兵法》的孙武并非同一人。

“中国剩余定理”在古代有“韩信点兵”、“鬼谷算”、“求一术”、“隔墙算”、“剪管术”、“秦王暗点兵”、“物不知数”、“孙子定理”之名,是数论中主要命题,它不仅在抽象代数理论中有相应的推广,也被应用到密码学、哥德尔不完全性定理的证明、快速傅里叶变换理论等。

首先,引述《孙子算经》中“物不知数”的原文:

今有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二,问物几何?

答曰:二十三。

术曰:三三数之剩二,置一百四十;五五数之剩三,置六十三;数之剩三,置三十。并之得二百三十三。以二百一十减之,即得。凡三三数之剩一,则置十,五五数之剩一,则置二十一,数之剩一,则置十五。一百六以上,以一百五减之,即得。

中国古代数学著作,关于中国剩余定理的数学探讨

用数论中的同余式表达就是:

中国古代数学著作,关于中国剩余定理的数学探讨

在这里,a≡b(mod n)的形式表示a和b除以n的余数相同,或者说a-b可被n整除,我们称之为“a、b关于模n同余”。同余符号“≡”为德国数学家高斯所发明并首先使用。

《孙子算经》简要给出了该问题的解法和答案,首先将该问题用算式求解即可表示为:

70×2+21×3+15×2-105×2=23。

中国古代数学著作,关于中国剩余定理的数学探讨

鉴于《孙子算经》对于这类问题的讨论存在没有总结成文以及未推及到一般情况的缺陷,因此也并没有达到理论的高度。南宋数学家秦九韶在1247年完成的《数书九章》中推广了“孙子定理”形成“中国剩余定理”。在《数书九章》中,秦九韶系统叙述了“大衍求一术”来归纳求解一次同余组的计算步骤,并提出了乘率、定数、衍母和衍数等一系列数学概念。至此,“物不知数”所引出的一次同余式组问题才真正得到了一般的解法,上升到中国剩余定理的高度。

《数书九章》又名《数学九章》,全书共十八卷,分为九类,每类九问,共九九八十一问,由南宋数学家秦九韶著于淳祐七年(1247年)。《数书九章》题材广泛,取自宋代社会各方面,包括农业、天文、水利、城市布局、建筑工程、测量、赋税、兵器、军旅等方面,是一部实用数学大全。

中国古代数学著作,关于中国剩余定理的数学探讨

1275年,杨辉的《续古摘奇算法》包了五个不同的同余问题,在此例子之后又附四例。同时,剩余问题也出现在阿拉伯数学家伊本·塔希尔(Ibn Tahir)和伊本·海什木(lbn al-Haytham)的著作中。意大利数学家斐波那契写于1202年的《计算之书》(Liber Abaci)中的剩余问题,使用了跟《孙子算经》中一样的模和法则。从此,剩余问题成为欧洲数学家论著中常见的主题。

明代程大位编撰的《算法统宗》用歌谣的形式给出了物不知数问题的解:

三人同行七十稀,

五树梅花廿一枝。

七子团圆正半月,

除百零五便得知。

该歌谣中的“七十稀”、“廿一枝”和“正半月”,就暗指70、21和15这三个重要的数字。

到了宋代,有人把这个口诀编为四句诗(周密《志雅堂杂钞》):

三岁孩儿七十稀,

五留廿一事尤奇,

七度上元重相会,

寒食清明便可知。

在这首诗里,“上元”是指正月十五日,即元宵节,暗指15;而“寒食”是节气时令名,从冬至到清明,间隔105日,这段期间叫做“寒食”,故“寒食”暗指105。

这里我们也可以看到,古人在数学教育中寓教于文,将中国剩余定理的解法以歌谣的形式更加便于记诵,使得该解法更为普及,以致远渡重洋,流传到日本。但是以上解法都没有说明这三个数的缘由。

第二部分:尝试与探索

在正式介绍同余解法之前,我们先来观察和尝试一下可能的答案。

当我们面对一个不熟悉的问题时,最先想到的办法就是先观察并进行试错(trial and error),通过投石问路的方式收集信息,再经系统化处理,这往往就能够解决一个问题。即使不能立马解决,对该问题也有了相当的理解,比盲目地解题更加有效。这就是我们经常说的“摸着石头过河”。

首先,我们考虑被3除余2的问题。正整数可被3整除的有 3、6、9、12、……,所以被3除余2的正整数有2、5、8、11、14、……;其次,被5除余3的正整数有3、8、13、18、……;最后,被7除余2的正整数有2、9、16、23、……。通过列表对其观察与比较:

中国古代数学著作,关于中国剩余定理的数学探讨

我们可以发现,第一个符合题目要求的答案是23。如果你有足够的耐心罗列下去,第二个答案就是128,第三个答案是233,……。于是我们可以归纳得到,从第一个答案23开始,逐个加上105都是符合题目要求的答案。如果写成表达式就是:

中国古代数学著作,关于中国剩余定理的数学探讨

从概率上来说,一只猴子用打字机随机地打字,最终会打出一部《莎士比亚全集》,其概率为1。这可能是试错法中最为令人惊叹的一个例子了。人为万物之灵,使用试错法当然会更加高明和有效。这也是我经常提醒孩子们的地方:我允许你们最后失败,但不能原谅你们不去尝试!

中国古代数学著作,关于中国剩余定理的数学探讨

根据笛卡儿(Descartes,1596~1650)的解题方法论:面对一个难题,尽可能把它分解成许多部分,然后由最简单、最容易下手的地方开始,一步一步地拾级而上,直到原来的难题解决。换言之,你问我一个问题,我就自问更多相关的问题,由简易至复杂,铺成一条探索之路。

第三部分:从不定方程说起

让我先从不定方程组开始说起。

前文“物不知数”的问题可以用不定方程组表达:

中国古代数学著作,关于中国剩余定理的数学探讨

要求这个联立方程组,先从单个的方程开始入手。

中国古代数学著作,关于中国剩余定理的数学探讨

要求这个方程的解,可以通过先求解m=3x而得到,然后加上2或5或-4等等即可。

接着考虑两个方程的情况,即:

中国古代数学著作,关于中国剩余定理的数学探讨

先考虑特殊情况,即余数为0的情况:

中国古代数学著作,关于中国剩余定理的数学探讨

显然,解m就是3和5的公倍数。因为3和5互质,所以3×5=15就是它们的最小公倍数。因此m=15·n(n∈Z),这就是上面联立方程组的通解。

进一步探索,尝试求特解:

中国古代数学著作,关于中国剩余定理的数学探讨

这个方程组的解其实就是要在5的倍数中找到除3余1的数字。

中国古代数学著作,关于中国剩余定理的数学探讨

由于是特解,我们不妨设m=10。从而我们可以得到下面这个方程组的特解为m=2×10=20。

中国古代数学著作,关于中国剩余定理的数学探讨

同理,我们可以得到下面方程组的特解为m=6。

中国古代数学著作,关于中国剩余定理的数学探讨

从而得到下面方程组的特解为m=3×6=18。

中国古代数学著作,关于中国剩余定理的数学探讨

根据上面的尝试,我们可以得到:

中国古代数学著作,关于中国剩余定理的数学探讨

这就是不定方程组

中国古代数学著作,关于中国剩余定理的数学探讨

的通解公式。

再进一步,我们求解原题的不定方程组:

中国古代数学著作,关于中国剩余定理的数学探讨

我们知道,因为3、5、7三个数互质,所以它们的最小公倍数为105。然后,我们分别找下面三个方程组的特解:

中国古代数学著作,关于中国剩余定理的数学探讨

分别得到m=70、m=21、m=15,从而得到:

中国古代数学著作,关于中国剩余定理的数学探讨

当n=-2时,m=23,即为“物不知数”问题的最小正整数解了。

小结:在这个问题上,我们通过分析与综合,将原问题分解成几个相关的简易问题(相当于物质之分解成原子),分别求得解答后,再将它们综合起来(相当于原子之组合成物质)。这里的综合包括特解的放大某个倍数和相加,然后再加上齐次线性方程组的通解。这非常相像于原子论的研究物质的组成要素、结构、变化和分合之道。

第四部分:从同余解法说起

数论中很重要的一部分内容就是同余式,理解了同余也就数论入门了。下面我们通过同余的解法来解释中国剩余定理,这部分内容本质上没有什么创新,其实就是对第三部分不定方程解法的进一步阐释。

首先,可以将孙子问题的解法分为三步。

第一步,找出这样三个数,从3和5的公倍数中找出被7除余1的最小数15,从3和7的公倍数中找出被5除余1的最小数21,从5和7的公倍数中找出被3除余1的最小数70;

第二步,用15乘以所求数除以7的余数2,用21乘以所求数除以5的余数3,用70乘以所求数除以3的余数2,然后把三个乘积相加,就可以得到15×2+21×3+70×2=233。

第三步,再用233除以3、5、7这三个数的最小公倍数105,得到余数23,这个余数就是符合条件的最小数。

我们将这种求解的方法称为“同余(congruence)算法”,这种算法的依据如下:

首先,假设a满足除以3余2,b满足除以5余3,c满足除以7余2。从a出发,由于a满足除以3余2,依据定理“如果一个除法运算的余数为r,那么被除数与k倍的除数相加(减)的和(差)再与除数相除,余数不改变”,可以使得a+b的和仍然满足除3余2;同理,可以使得a+b+c的和仍然满足除3余2,对于b、c有类似推导。

综上可以得出:

b和c是3的倍数,则a+b+c的和满足除3余2;

a和c是5的倍数,则a+b+c的和满足除5余3;

a和b是7的倍数,则a+b+c的和满足除7余2。

所以为了使得a+b+c的和为所求解,只要满足:

a除3余2,且是5和7的公倍数;

b除5余3,且是3和7的公倍数;

c除7余2,且是3和5的倍数。

因此,问题可以归结为从5和7的公倍数中找出一个数,使得其除3余2,记为a;从3和7的公倍数中再找出一个数,使得其除以 5余3,记为b;最后从3和5的公倍数中找出一个数,使得其除7余2,记为c。最后再把三个数相加就是所求数,尽管这时还不是最小解。在求解a、b、c时,以求解a为例,并不是直接从5和7的公倍数中找到除3余2的数,而是先找到除3余1的数,再乘2。

用同余式表达就是:

中国古代数学著作,关于中国剩余定理的数学探讨

中国剩余定理还可以通过线性代数求解,并一般化到n个两两互质的正整数情况,有兴趣的朋友可以去寻找相关的资料进行学习,并进一步理解和体会到中国剩余定理的重要性和影响力。

第五部分:秦九韶与《数书九章》

最后,我有必要向读者朋友们再介绍一位被严重忽视的南宋数学家秦九韶。

中国古代数学著作,关于中国剩余定理的数学探讨

秦九韶祖籍河南范县,出因地理位置处于鲁豫交界处,有数百年设在山东莘县境内,故自称山东鲁郡人。他生于四川普州安岳,曾担任过四川巴州的地方官,后因巴州兵变调任临安(杭州)。在蒙古大军兵临潼川城下的艰难环境里,秦九韶却有了撰写《数书九章》的时间和灵感,也许恰是数学才使他抚平了战乱的担忧,缓解了国事飘零的悲痛。

鉴于他对数字的尊崇和对《周易》命理学的信服,秦九韶将《数书九章》分成九部分,每一部分又包含九道题,也许这不是一个单纯的巧合。除了天文、历法、气象、军旅(营盘布置)以及市物(利息的计算)相关的数学问题,书中还包括了不定分析、田域测量、测望法(勾股、重差)、求“均税”(均输、税收)、农业营建以及仓窖容积和各种商品转运方面的题目。

在序言中,从占卜和《周易》中数学的地位,到“土圭度晷”在量天测地中所起到的作用,秦九韶强调了数学在社会生活各方面扮演的角色。他所引用的河图洛书充满了神秘的数学意义,因为它们的图形与幻方有密切关联。河图出自黄河,据说它的灵感来自一匹龙马身上的斑点;洛书则来源于洛水,传说有神龟出于洛水,其甲壳上有此图像,前九个数字列成了一个幻方。

中国古代数学著作,关于中国剩余定理的数学探讨

除了仅将数学应用于历法推算、官员们的日常管理以及摇役摊派的计算上,秦九韶对数学家们故步自封导致数学被“漠然置之”而耿耿于怀。结果,甚至掌握了基本算法的数学家都不能处理高次开方或不定分析问题。

《数书九章》的伟大创新之处在于该书的第一部分就对不定分析问题做了详细的阐释,书中所展示的计算方法被称作“大衍求一术”。此名就带有神秘主义的色彩,秦九韶把命理学与解一次同余式的方法联系在一起。《数书九章》的前言提及“道数合一”,并把数学运算过程解释为“通神明”。“大衍术”的独特之处在于强调了一条《九章》里没有的数学规律,尽管造历者早巳对其熟练利用,数学家的工作显然尚未开始。“大衍求一术”中求解方程ax≡1(mod m)中的步骤,是解决中国剩余问题的关键一步,即n个同余式N≡ri(mod mi)的解,其中mi两两互质。

用现代数学语言来描述“大衍求一术”就是:设有k个两两互质的大于1的正整数mi,其乘积为M,则对任意k个整数ai,存在唯一不超过M的正整数x,x被各个mi相除所得余数依次为ai。秦九韶给出了求解的过程,为此他发明了“辗转相除法”(欧几里得算法)和 “求一术”。后者是指,设a和m是互质的正整数,m大于1,可以求得唯一不超过m的正整数x,使得a和x的乘积被m除后余数为1。

《孙子算经》中所给出的“中国剩余问题”(Chinese Remainder Problem)的解决方法表明作者似乎懂得这个问题的一般规律,只是没有明白地表示出来,并且孙子的解决方案仅针对“孙子问题”中的数据而言,这显然不足以满足秦九韶对更普遍规律的渴求。由此,他构思出了一个更加详细的步骤,将算板上数字的每一步都加以说明。

求满足xiPi≡1(mod m)的xi的步骤也解释了秦九韶为什么把中国剩余定理命名为“大衍求一术”,这可以追溯到《易经》。在那里占卜的方法开始于50只计数用的小棍,其中在把剩余的分成阴阳两组之前,有一只是被放到一边的。

中国古代数学著作,关于中国剩余定理的数学探讨

秦九韶设计了9道复杂的同余问题。例如,第3题涉及四个模:54、57、72和75。而且,当同余问题与天文应用结合时,数学的复杂性陡然上升。例如,因为mi代表了行星或者月亮相位的运动周期,其中的同余式并非都是整数。他还进一步考虑了更加复杂的情形,比如m是分数的情况。他解释了如果mi不互质该怎么做。尽管中国数学家没有明确地使用质数概念,在同余式中mi不包含公因子的必要性对秦九韶这样的数学家也是显而易见的。

《数书九章》对同余问题的系统性解决方法与历法应用紧密相连,秦九韶也恰好对后者非常感兴趣,并在这里使用了追及问题的形式以求得从一个给定的初始位置到(行星)第二次排列出现时所需要的时间。这样的追及问题出现在《数书九章》的第一章和第二章,且虽然求“上元积年”的方法主要应用于天文历法,秦九韶也用这个方法来解决各种数学中的同余问题。李俨、杜石然指出,直到欧拉(Euler)和高斯(Gauss)系统地研究了同余问题,才可与秦氏的结果相比肩,他们据此认为“秦九韶的研究比欧洲此方面的研究早了500年”。

《数书九章》包含了许多问题,其中涉及二次方程、三次方程、四次方程,甚至有一道十次方程的题。这些方程的系数可正可负,或是整数或是分数——开方根的方法是普遍适用的。在他的解法阐释中,秦九韶经常清晰地给出表示算筹摆布形状的图,用以说明用迭代乘法进行开方根算法的每一步过程。

1852年,英国传教士和汉学家伟烈亚力(Wylie,1815~1881)将“大衍求一术”和同余方程组的解法翻译介绍到西方,德国数学史家康托尔(1829~1920) 赞扬秦九韶是“最幸运的天才”。因为此前欧拉和高斯都对这个问题做了深入研究,并给以理论证明,但尚未命名。当年法国数学家拉格朗日 (1736~1813) 也是这样称赞牛顿的,拉格朗日认为,发现万有引力定律只有一次机会。有着“科学史之父”美誉的比利时裔美国科学史家萨顿 (Sarton,1884~1956) 则认为,秦九韶是“他那个民族,他那个时代,并且确实也是所有时代最伟大的数学家之一”。2005年,牛津大学出版社出版了《数学史:从美索不达米亚到现代》,该书重点介绍的12位数学家中,秦九韶是唯一的中国人。

因此,从严格意义上讲,孙子定理应称为“孙子-秦九韶定理”,或“秦九韶定理”。

第六部分:结  语

二十世纪最大的物理学家之一的费曼(R. P. Feynman,1918~1988)曾经批评物理学教育说:“物理学家总是在传授解题技巧,而不是从物理的精神层面来启发学生。”这里的“物理”改为“数学”也适用。

中国古代数学著作,关于中国剩余定理的数学探讨

作为数学工作者,我想说的是:“我们的数学教育工作者总是在教孩子背公式、学套路,而不是从最基本的数学原理和知识架构上去向学生传授知识,敢问这样的教育称得上是真正的教育吗?

文/Mr.Why

上一篇:

下一篇:

相关阅读

分享