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

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