韩信点兵(同余问题).doc

二 韩信点兵我们先考虑下列的问题：假设兵不满一万，每5人一列、9人一列、13人一列、17人一列都剩3人，则兵有多少？首先我们先求5、9、13、17之最小公倍数9945（注：因为5、9、13、17为两两互质的整数，故其最小公倍数为这些数的积），然再加3，得9948（人）。有一个数，除以3余2，除以4余1，问这个数除以12余几？  解：除以3余2的数有： 2， 5， 8， 11，14， 17， 20， 23….  它们除以12的余数是： 2，5，8，11，2，5，8，11，….  除以4余1的数有： 1， 5， 9， 13， 17， 21， 25， 29，….  它们除以12的余数是： 1， 5， 9， 1， 5， 9，….  一个数除以12的余数是唯一的.上面两行余数中，只有5是共同的，因此这个数除以12的余数是5.  如果我们把问题改变一下有一个数，除以3余2，除以4余1，问这个数不求被12除的余数，而是求这个数.很明显，这个数满足条件的数是很多的，是 5＋12×0，1，2，…)， 事实上，我们首先找出5后，注意到12是34的最小公倍数，再加上12的整数倍，就都是满足条件的数.这样就是把“除以3余2，除以4余1”两个条件合并成“除以12余5”一个条件.提出的有三个，我们可以先把两个条件合并成一个.然后再与第三个条件合并，就可找到答案.  　秦朝末年，楚汉相争韩信1500名将士与楚王大将李锋交战。苦战一场，楚军不敌，败退回营，汉军也死伤四五百人，于是韩信整顿兵马也返回大本营。当行至一山坡，忽有后军来报，说有楚军骑兵追来。只见远方尘土飞扬，杀声震天。汉军本来已十分疲惫，这时队伍大哗。韩信急速点兵迎敌。他命令士兵3人一排，结果多出2名；接着命令士兵5人一排，结果多出3名；他又命令士兵7人一排，结果又多出2名。韩信马上向将士们宣布：我军有1073，敌人不足五百，我们居高临下，以众击寡，一定能打败敌人。一个数除以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.除以3余2，除以5余33与5的最小公倍数是15.两个条件合并成一个就是8＋15×0，1，2，…列出这一串数是8， 23， 38，…，再列出除以7余2的数 2， 9， 16， 23， 30，…，  就得出符合题目条件的最小数是23. 事实上，我们已把题目中三条件合并成一个3，5，7的最小公倍数是 23+105×n(n=0，1，2，…那么韩信点的兵在1000-100之间，应该是23+105×10=1073人如果你随便拿一把蚕豆（数目约在100粒），假如3粒一数余1粒，5粒一数余2粒，7粒一数余2粒，那么，原有蚕豆有多少粒呢？中国剩余定理韩信点兵的计算方法是：用3个一数剩下的余数，将它70（因为70是5与7的倍数，又是以3去除余1的数）；5个一数剩下的余数，将它21（因为21是3与7的倍数，又是以5去除余1的数）；7个一数剩下的余数，将15（因为15是3与5的倍数，又是以7去除余1的数），将这些数加起来，若超过105最小公倍，就减掉105，如果剩下来的数目还是比105大，就再减去105，直到得数比105小为止。这样，所得的数就是原来的数了。根据这个道理，你可以很容易地把前面的题目列成算式：1×70＋2×21＋2×15－105 ＝142－105 ＝37 因此，可以知道，原来这一堆蚕豆有37粒。【】求最小非负整数N，使他在除以5,7,11以后所得余数分别是a,b,c。 【韩信点兵法口诀的原理】①能被7,11除尽数是77k,k=3，即231除5正好余1，231a 除5正好余a。②能被5,11除尽数是55k,k=6，即330除7正好余1，330b 除7正好余b。③能被5,7除尽数是35k,k=6，即210除11正好余1，210c 除11正好余c。 那么 231a+330b+210c 除以5,7,11以后所得余数一定分别是a,b,c。 5,7,11最小公倍根据【符合要求的最小数N必满足0≤N＜385】，所以当 231a+330b+210c 大于或等于385时，还必须减去若干个385 直到比385小为止，才可以得到符合题意要求的最小数。 【说明】231a+330b+210c + 385k 也一定满足“除以5,7,11以后所得余数分别是a,b,c”。 【例】求最小非负整数N，使他在除以5,7,11以后所得余数分别是3,5,7。 【解】231a+330b+210c=2