雪帆奥数老师对中国剩余定理的详细讲解

发布时间：2008-06-12 14:32:45 来源：雪帆奥数作者：雪帆 [打印] [评论]

引子：民间传说着一则故事——“韩信点兵”。

秦朝末年，楚汉相争。一次，韩信将1500名将士与楚王大将李锋交战。苦战一场，楚军不敌，败退回营，汉军也死伤四五百人，于是韩信整顿兵马也返回大本营。当行至一山坡，忽有后军来报，说有楚军骑兵追来。只见远方尘土飞扬，杀声震天。汉军本来已十分疲惫，这时队伍大哗。韩信兵马到坡顶，见来敌不足五百骑，便急速点兵迎敌。他命令士兵3人一排，结果多出2名；接着命令士兵5人一排，结果多出3名；他又命令士兵7人一排，结果又多出2名。韩信马上向将士们宣布：我军有1073名勇士，敌人不足五百，我们居高临下，以众击寡，一定能打败敌人。汉军本来就信服自己的统帅，这一来更相信韩信是“神仙下凡”、“神机妙算”。于是士气大振。一时间旌旗摇动，鼓声喧天，汉军步步进逼，楚军乱作一团。交战不久，楚军大败而逃。

问题：一千多年前的《孙子算经》中，有这样一道算术题：

“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”

翻译过来就是让你找一个数a，满足a除以3余2，除以5余3，除以7余2。（当然a有一定的范围，否则会有无数个答案！）

普通解法：余数方法

例题：一个数除以3余2，除以5余3，除以7余2，求符合条件的最小数.

解：先列出除以3余2的数： 2， 5， 8， 11， 14， 17， 20， 23， 26，…，

再列出除以5余3的数：3， 8， 13， 18， 23， 28，….

很明显，满足这两个条件的最小数就是8。但8不能满足第三个条件。于是我们加以调整！

但又不能改变前面的余数。于是，每次就要加上3和5的最小公倍数（这一点由你自己来思考为什么？）

3与5的最小公倍数是15.两个条件合并成一个就是8＋15×整数，列出这一串数是8， 23， 38，…，再列出除以7余2的数 2， 9， 16， 23， 30，…，

就得出符合题目条件的最小数是23.

所以韩信才会根据数的特点，判断兵在1000-1500之间，应该是105×10+23=1073人

性质：根据余数的性质可以得出另外一种解法。方法简单总结如下：
1.算两两数之间的能整除数；
2.算三个数的能整除数；
3.用1中的三个整除数之和减去2中的整除数之差(有时候是倍数)；
4计算结果即可。

万能解法：中国剩余定理

例题：一个数除以3余2，除以5余3，除以7余2，求符合条件的最小数.

步骤一：找基准

求用其中两个除数的最小公倍数除以第三个数的余数

35＝2mod（3）

15＝1mod（7）

21＝1mod（5）

步骤二：调整

调整各自的倍数，使其能满足题目要求

35*1＝35（思考为什么要分别乘以1，3，2。提示余数的性质）

21*3＝63

15*2＝30

步骤三：加和