中国剩余定理.doc

《中国剩余定理.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、中国剩余定理的由来我国古代数学名著《孙子算经》载有一道数学问题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？”这里的几何指多少的意思。翻译成数学语言就是：求正整数N，使N除以3余2，除以5余3，除以7余2。如何求符合上述条件的正整数N呢？《孙子算经》给出了一个非常有效的巧妙解法。术曰：“三、三数之剩二，置一百四十；五、五数之剩三，置六十三；七、七数之剩二，置三十，并之，得二百三十三。以二百一十减之，即得。凡三、三数之剩一，则置七十；五、五数之剩一，则置二十一；七、七数之剩一，则置十五。一百六以上，一百五减之，即得。”过了一

2、千多年，到了十六世纪，数学家程大位在他所著的《算法统宗》里把这个问题的解法用歌诀形式表述出来。三人同行七十稀，五树梅花廿一枝，七子团圆正月半，除百零五便得之。歌诀的前三句给出了三组数，后一句给出了一个数：3  705  217  15105三组数的共同特征是：70除以3余1，除以5、7余0；21除以5余1，除以3、7余0；15除以7余1，除以3、5余0。首先程大位把不同的余数问题统一化为标准的余数问题。然后，他把复杂难解的问题化解为三个易解的问题。70、21、15分别是满足第一、二、三行条件的最小解。2×70满足原题第一个余数条件，且被5、7整除。

3、3×21满足原题第二个余数条件，且被3、7整除。2×15满足原题第三个余数条件，且被3、5整除。统统相加得和：N=2×70+3×21+2×15=233。N必然满足原题所有三个余数条件。但N不一定是最小的。歌诀最后一句“除百零五便得知”，这里“除”的意思是“减”，意即从233中减去3、5、7的最小公倍数105的倍数便得到23。这个23就是问题的最小解。这最后一句也可以理解为N除以105的余数就是问题的最小解。中国古代数学有一个传统，总是以具体的数量关系表示一般的规律。把中国剩余定理译成数论术语就是：设m₁、m₂、m₃是两两互质的正整数，对任意给定的整

4、数a₁、a₂、a₃，必存在整数，满足：x≡a₁(modm₁)，x≡a₂(modm₂)，x≡a₃(modm₃)。并且满足上列方程组的解x(modm1m2m3)是存在唯一的。上面定理的表述是为方便或为忠于《孙子算经》，我们只写出含三个余数的情形，其实，这个定理对n个余数是通用的。这个算法，给出了这类问题的非常简捷的一般解法。这个算法，具有非凡的数学思想，并对数论、代数产生了重要影响，中国称此算法为“孙子定理”，国际上称此为“中国剩余定理”。这是中国数学对世界数学最重要的贡献之一。中国剩余定理除本身的重要性之外，它还提示人们，要解决较复杂的问题，最好把它

5、分解为几个易解的子问题；把问题各不相同的条件化成标准的条件，然后用标准的、统一的方法去处理。这是两种重要的数学思想。南宋数学家秦九韶在他的《数书九章》中推广了“物不知数”问题，提出了计算“乘率”的方法——“大衍求一术”，使解决一次同余式问题的方法形成系统化的数学理论。在西方，直到十八世纪，瑞士的欧拉与法国的拉格朗日才对同余式问题进行系统的研究。十九世纪的第一年，德国的高斯在《算术探究》一书中，才提出解决这类问题的方法——剩余定理，并给出了严格证明，被后人称为“高斯定理”。1852年英国基督教士伟烈亚力在《字林西报》上发表了《中国科学的记述》，介绍《

6、孙子算经》中的“物不知数”题，并第一次解释了“大衍求一术”，并指出它实质上和高斯定理是一致的。当时，德国著名数学家康托尔称赞秦九韶是“最幸运的天才”，秦九韶推广了“中国的剩余定理”，为我国和世界数学史增添了光彩。好学不倦，因而从中养成了认真、细致、精核、严谨的精神。他不仅深入实际，搜集问题，而且帮助群众解决问题。