中国剩余 定理

《中国剩余 定理》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、中国剩余定理在中国古代劳动人民中，长期流传着“隔墙算”、“剪管术”、“秦王暗点兵”等数学游戏。有一首“孙子歌”，甚至远渡重洋，输入日本：“三人同行七十稀，五树梅花廿一枝，七子团圆正半月，除百零五便得知。”这些饶有趣味的数学游戏，以各种不同形式，介绍世界闻名的“孙子问题”的解法，通俗地反映了中国古代数学一项卓越的成就。“孙子问题”在现代数论中是一个一次同余问题，它最早出现在中国公元四世纪的数学著作《孙子算经》中。《孙子算经》卷下“物不知数”题说：有物不知其数，三个一数余二，五个一数余三，七个一数又余二，问该物总数几何？显然，这相当于求不定方程组N=3x+2,N=5y+3,N

2、=7z+2的正整数解N，或用现代数论符号表示，等价干解下列的一次同余组。《孙子算经》所给答案是N=23。由于孙子问题数据比较简单，这个答数通过试算也可以得到。但是《孙子算经》并不是这样做的。“物不知数”题的术文指出解题的方法多三三数之，取数七十，与余数二相乘；五五数之，取数二十一，与余数三相乘；七七数之，取数十五，与余数二相乘。将诸乘积相加，然后减去一百零五的倍数。列成算式就是：N=70×2+21×3+15×2－2×105。这里105是模数3、5、7的最小公倍数，容易看出，《孙子算经》给出的是符合条件的最小正整数。对于一般余数的情形，《孙子算经》术文指出，只要把上述算法中

3、的余数2、3、2分别换成新的余数就行了。以R1、R2、R3表示这些余数，那么《孙子算经》相当于给出公式N=70×R1+21×R2+15×R3－P×105（p是整数）。孙子算法的关键，在于70、21和15这三个数的确定。后来流传的《孙子歌》中所说“七十稀”、“廿一枝”和“正半月”，就是暗指这三个关键的数字。《孙子算经》没有说明这三个数的来历。实际上，它们具有如下特性：也就是说，这三个数可以从最小公倍数M=3×5×7=105中各约去模数3、5、7后，再分别乘以整数2、1、1而得到。假令k1=2，K2=1，K3=1，那么整数Ki（i=1，2，3)的选取使所得到的三数70、21、

4、15被相应模数相除的时候余数都是1。由此出发，立即可以推出，在余数是R1、R2、R3的情况下的情况。解法中的三个关键数70，21，15，有何妙用，有何性质呢?首先70是3除余1而5与7都除得尽的数，所以70a是3除余a，而5与7都除得尽的数，21是5除余1，而3与7都除得尽的数，所以21b是5除余b，而3与7除得尽的数。同理，15c是7除余c，3与5除得尽的数，总加起来70a+21b+15c是3除余a，5除余b，7除余c的数，也就是可能答案之一，但可能不是最小的，这数加减105(105=3×5×7)仍有这样性质，可以多次减去105而得到最小的正数解。附：如70，其实是要找

5、余2的，但只要找到了余1的再乘2即余二了。孙子问题的解法，以现代的说法，是找出三个关键数70，21，15。解法的意思就是用70乘3除所得的余数，21乘5除所得的余数，15乘7除所得的余数，然后总加起来，除以105的余数就是答案。即题目的答案为70×2+21×3+15×2=140+63+30=233233-2×105=23公式：70a+21b+15c-105n题中有三个数，分别为3、5、7，5×7÷3余数为2，取35；3×7÷5余数为1，要使余数为3，只需将3×7扩大3倍变成63即可；同样3×5÷7的余数为1，要使余数为2，则将3×5扩大2倍，变成30。中国剩余定理”算理及

6、其应用：为什么这样解呢？因为70是5和7的公倍数，且除以3余1。21是3和7的公倍数，且除以5余1。15是3和5的公倍数，且除以7余1。（任何一个一次同余式组，只要根据这个规律求出那几个关键数字，那么这个一次同余式组就不难解出了。）把70、21、15这三个数分别乘以它们的余数，再把三个积加起来是233，符合题意，但不是最小，而105又是3、5、7的最小公倍数，去掉105的倍数，剩下的差就是最小的一个答案。用歌诀解题容易记忆，但有它的局限性，只能限于用3、5、7三个数去除，用其它的数去除就不行了。后来中国数学家又研究了这个问题，运用了像上面分析的方法那样进行解答。例1：一个

7、数被3除余1，被4除余2，被5除余4，这个数最小是几？题中3、4、5三个数两两互质。则〔4，5〕=20；〔3，5〕=15；〔3，4〕=12；〔3，4，5〕=60。为了使20被3除余1，用20×2=40；使15被4除余1，用15×3=45；使12被5除余1，用12×3=36。然后，40×1+45×2+36×4=274，因为，274>60，所以，274－60×4=34，就是所求的数。例2：一个数被3除余2，被7除余4，被8除余5，这个数最小是几？题中3、7、8三个数两两互质。则〔7，8〕=56；〔3，8〕=24；〔3，7〕=21；