手机版 | 登陆 | 注册 | 留言 | 设首页 | 加收藏
当前位置: 网站首页 > 世界科技全景 > 数学大发现 > 文章 当前位置: 数学大发现 > 文章

中国剩余定理

时间:2019-09-30    点击: 次    来源:网络    作者:佚名 - 小 + 大

中国剩余定理


在我国古代劳动人民中,长期流传着“隔墙算”、“剪管术”、“秦王

暗点兵”等数学游戏。有一首“孙子歌”,甚至远渡重洋,输入日本:

“三人同行七十稀,五树梅花廿一枝,

七子团圆正半月,除百令五便得知。”

这些饶有趣味的数学游戏,以各种不同形式,介绍世界闻名的“孙子问

题”的解法,通俗地反映了中国古代数学一项卓越的成就。

“孙子问题”在现代数论中是一个一次同余问题,它最早出现在我国公

元四世纪的数学著作《孙子算经》中。《孙子算经》卷下“物不知数”题说:

有物不知其数,三个一数余二,五个一数余三,七个一数又余二,问该物总

数几何?显然,这相当于求不定方程组

N=3x+2,N=5y+3,N=7x+2

的正整数解 N,或用现代数论符号表示,等价于解下列的一次同余组:

N≡2(mod3)≡3(mod5)≡2(mod7)

《孙子算经》所给答案是 N=23。由于孙子问题数据比较简单,这个答数

通过试算也可以得到。但是《孙子算经》并不是这样做的。“物不知数”题

的术文指出解题的方法:三三数之,取数七十,与余数二相乘;五五数之,

取数二十一,与余数三相乘;七七数之,取数十五,与余数二相乘。将诸乘

积相加,然后减去一百零五的倍数。列成算式就是:

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

这里 105 是模数 3、5、7 的最小公倍数,容易看出,《孙子算经》给出

的是符合条件的最小正整数。对与一般余数的情形,《孙子算经》术文指出,

只要把上述算法中的余数 2、3、2 分别换成新的余数就行了。以 R1、R2、R3

表示这些余数,那么《孙子算经》相当于给出公式

N=70×R1+21×R2+15×R3-P×105(P 是整数)

孙子算法的关键,在于 70、21 和 15 这三个数的确定。后来流传的《孙

子歌》中所说“七下稀”、“廿一枝”和“正半月”,就是暗指这三个关键

的数字。《孙子算经》没有说明这三个数的来历。实际上,它们具有如下特

性:


 

70 = 2×


3×5×7

3


≡1(mod 3)


 


21 = 1×

 

15 = 1×


3×5×7

5

3×5×7

7


≡1(mod 5)

 

≡1(mod 7)


也就是说,这三个数可以从最小公倍数 M=3××7=105 中各约去模数 3、

5、7 后,再分别乘以整数 2、1、1 而得到。假令 k1=2,k2=1,k3=1,那么整

数 ki(i=1,2,3)的选取使所得到的三数 70、21、15 被相应模数相除的时

候余数都是 1。由此出发,立即可以推出,在余数 R1、R2、R3 的情况下


 


R1×k1×

 

R2×k 2×

 

R3×k3×


M

3

M

5

M

7


= R1×2×

 

= R2×1×

 

= R 3×1×


3×5×7

3

3×5×7

5

3×5×7

7


≡R1(mod 3)

 

≡R 2 (mod 5)

 

≡R3(mod 7)


 


综合以上三式又可得到


 


R1×2×


3×5×7

3


+ R2 ×2×


3×5×7

5


+ R3×1×


3×5×7

7


≡R1(mod3)

≡R2(mod5)

≡R3(mod7)

因为 M=3××7 可被它的任一因子整除,于是又有:


 


(R1×2×


3×5×7

3


+ R2×1×


3×5×7

5


+ R3×1×


3×5×7

7


− PM


≡R1(mod3)

≡R2(mod5)

≡R3(mod7)

这里的 P 是整数。这就证明了《孙子算经》的公式。应用上述推理,可

以完全类似地把孙子算法推广到一般情形:设有一数 N,分别被两两互素的

几个数 a1、a2……an 相除得余数 R1、R2、……Rn,即

N≡Ri(mod ai)(i=1、2、……n)

只需求出一组数 Ki,使满足


 


ki


M

a i


≡1(mod a ai )(i = 1 、Ë 2、n)


 


那么适合已给一次同余组的最小正数解是


 


N = (R 1k 1


M

a 1


+ R 2 k 2


M

a2


+ R 3 k3


M

a 3


+Ë R n k n


M

a n


)


 


这就是现代数论中著名的剩余定理。如上所说,它的基本形式已经包含

在《孙子算经》“物不知数”题的解法之中。不过《孙子算经》没有明确地


表述这个一般的定理。

孙子问题出现在公元四世纪的中国算书中,这并不是偶然的。我国古代

天文历法资料表明,一次同余问题的研究,明显地受到天文、历法需要的推

动,特别是和古代历法中所谓“上元积年”的计算密切相关。大家知道,一

部历法,需要规定一个起算时间,我国古代历算家把这个起点叫做“历元”

或“上元”,并且把从历元到编历年所累积的时间叫做“上元积年”。上元

积年的推算需要求解一组一次同余式。以公元三世纪三国时期魏国施行的《景

初历》做例,这部历法规定以冬至、朔旦(朔日子夜)和甲子日零时会合的

时刻作为历元。设 a 是一回归年日数,b 是一朔望月日数,当年冬至距甲子

日零时是 R1,离平朔时刻是 R2 日,那么《影初历》上元积元数 N 就是同余组

aN≡Ri(mod 60)≡R2(mod b)

的解。到了南北朝时期,祖冲之《大明历》(公元 462 年)更要求历元

必须同时是甲子年的开始,天“日月合璧”、“五星联珠”(就是日、月、

五大行星处在同一方位),月亮又恰好行经它的近地点和升交点。这样的条

件下推算上元积年,就相当于要求解十个同余式了。天文历法数据一般又都

十分庞杂,所以,在《孙子算经》成书前后的魏晋南北朝时期,我国的天文

历算家无疑已经能够求解形式比《孙子算经》“物不知数”题复杂得多的一

次同余式,因而必定掌握了按一定程序计算一次同余式的方法。《孙子算经》

比例题的形式总结、反映了这一事实。以后天文历算家长期沿用孙子算法推

算上元积年,这中间肯定会引起更加深入的探讨。到公元 13 世纪,大数学家

秦九韶集前法之大成,终于在一次同余式的研究上获得了超越前人的辉煌成

果。

秦九韶,字道古,生活于南宋时期,自幼喜好数学,经过长期积累和苦

心钻研,于公元 1247 年写成《数书九章》。这部中世纪的数学杰作,在许多

方面都有创造,其中求解一次同余组的“大衍求一术”和求高次方程数值解

的“正负开方术”,更是具有世界意义的成就。

这里主要介绍秦九韶对一次同余论的伟大贡献。

秦九韶在《数书九章》中明确地系统地叙述了求解一次同余组的一般计

算步骤。秦的方法,正是前述的剩余定理。我们知道,剩余定理把一般的一


 


次同余问题归结为满足条件Ki


M

a i


(mod a i )的一组数k i 的选定。秦九韶给


 


这些数起名叫“乘率”,并且在《数书九章》卷一“大衍总术”中详载了计

算乘率的方法——大衍求一术”。

在秦九韶那个时代,计算仍然使用算筹。秦九韶在一个小方盘上,右上

布置奇数 g,右下布置定数 a,左上置 1(他叫它做“天元 1”),然后在右

行上下交互以少降多,所得商数和左上(或上),直到右上方出现 1 为止。

下页就是秦九韶的一般筹算图式,右边是一个数字例子(g=20,a=27 ,

k=c4=23)。

秦九韶在《数书九章》中采集了大量例题,如“古历会积”、“积尺寻

源”、“推计土功”、“程行计地”等等,广泛应用大衍求一术来解决历法、

工程、赋役和军旅等实际问题。在这些实际问题中,模数 ai 并不总是两两互

素的整数。秦九韶区分了“元数”(ai 是整数)、“收数”(ai 是小数)、


“通数”(ai 是分数)等不同情形,并且对每种情形给出了处理方法。“大

衍总术”把“收数”和“通数”化成“元数”的情形来计算,而对于元数不

两两互素的情形,给出了可靠的程序,适当选取那些元数的因子作定数而把

问题归结为两两互素的情形。所有这些系统的理论,周密的考虑,即使以今

天的眼光看来也很不简单,充分显示出秦九韶高超的数学水平和计算技巧。

秦九韶小时曾跟随他父亲到南宋京城杭州,向太史局(主管天文历法的

机构)的官员学习天文历法,“大衍求一术”很可能就是他总结天文历法计

算上元积年方法的结果。但是“大衍求一术”似乎没有为他同时代的人所充

分理解。明中叶以后几乎失传。一直到清代“大衍求一术”又重新被发掘出

来,引起了许多学者(张敦仁、李锐、骆腾风、黄宗宪等)的兴趣。他们对

“大衍求一术”进行了解释、改进和简化,其中黄宗宪《求一术通解》对模

数非两两互素的情形给出了更加简明的方法,但是时代已是晚清。

从《孙子算经》“物不知数”题到秦九韶的“大衍求一术”,我国古代

数学家对一次同余式的研究,不仅在中国数学史上而且在世界数学史上占有

光荣的地位。在欧洲,最早接触一次同余式的,是和秦九韶同时代的意大利

数学家斐波那契(1170~1250),他在《算法之书》中给出了两个一次同余

问题,但是没有一般的算法。整个水平没有超过《孙子算经》。直到十八、

十九世纪,大数学家欧拉(1707~1783)于公元 1801 年对一般一次同余式进

行了详细研究,才重新获得和秦九韶‘大衍求一术”相同的定理,并且对模

数两两互素的情形,给出了严格证明。欧拉和高斯事先并不知道中国人的工

作。公元 1852 年英国传教士伟烈亚力(1815~1887)发表《中国科学摘记》,

介绍了《孙子算经》物不知数题和秦九韶的解法,引起了欧洲学者的重视。

1876 年,德国马蒂生(1830~1906)首先指出孙子问题的解法和高斯方法一

致,当时德国著名数学史家康托(1829~1920)看到马蒂生的文章以后,度

评价了“大衍术”,并且称赞发现这一方法的中国数学家是“最幸运的天才”。

直到今天,“大衍求一术”仍然引起西方数学史家浓厚的研究兴趣。如 1973

年,美国出版的一部数学史专著《十三世纪的中国数学》中,系统介绍了中

国学者在一次同余论方面的成就,作者力勃雷希(比利时人)在评论素九韶

的贡献的时候说道:“秦九韶在不定分析方面的著作时代颇早,考虑到这一

点,我们就会看到,萨顿称秦九韶为‘他那个民族’,是毫不夸张的。”

印度学者对一次同余论也有过重要贡献。从公元 6 世纪到 12 世纪,他们

发展了一种称为“库塔卡”的算法,用来求解和一次同余式等价的不定方程

组。“库塔卡”法出现在孙子算法之后,印度数学家婆罗门芨多(七世纪)、

摩柯吠罗(九世纪)等人的著作中,都有和物不知数题相同的一次同余问题。

这当然不是要借此断言“库塔卡”法一定受到了孙子算法的影响,但是有人

(如万海依等)硬说中国的“大衍求一”来源于“库塔卡”,就是毫无根据

的妄说了。万海依居然把中国算法中数码从左到右横写作为“大衍术”受印

度影响的重要根据。大家知道,中国古代至迟从春秋战国时期就开始使用算

筹记数,我们今天还可以从现存的公元前三世纪的货币上看到这种从左到右

的记数方法。由此可见,万海依的论点多么荒唐可笑。中国古代数学家对一

次同余论的研究有明显的独创性和继承性,“大衍求一术”在世界数学史上

的崇高地位是毋容置疑的,正因为这样,在西方数学史著作中,一直公正地

称求解一次同余组的剩余定理为“中国剩余定理”。

   

上一篇:“虚幻之数”

下一篇:影子的数学应用

推荐阅读
备案ICP编号  |   QQ:81962480  |  地址:上海金海路  |  电话:12345678910  |  
Copyright © 2019 MAPDF Studio 版权所有,授权www.mapdf.net使用 Powered by MAPDF.net