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

《韩信点兵(同余问题).doc》由会员分享，可在线阅读，更多相关《韩信点兵(同余问题).doc（8页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、精品文档，仅供学习与交流，如有侵权请联系网站删除 二 韩信点兵例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

2、， 29，. 它们除以12的余数是： 1， 5， 9， 1， 5， 9，. 一个数除以12的余数是唯一的.上面两行余数中，只有5是共同的，因此这个数除以12的余数是5. 如果我们把问题改变一下：有一个数，除以3余2，除以4余1，问这个数是几？不求被12除的余数，而是求这个数是几？.很明显，这个数最小是5，满足条件的数是很多的，它们是 512n (n=0，1，2，3)， 事实上，我们首先找出5后，注意到12是3，4的最小公倍数，再加上12的整数倍，就都是满足条件的数.这样就是把“除以3余2，除以4余1”两个条件合并成“除以12余5”一个条件.题目中提出的条件有三个，我们可以先把两个条件合并成一个

3、.然后再与第三个条件合并，就可找到答案. 例3秦朝末年，楚汉相争.韩信帅1500名将士与楚王大将李锋交战。苦战一场，楚军不敌，败退回营，汉军也死伤四五百人，于是韩信整顿兵马也返回大本营。当行至一山坡，忽有后军来报，说有楚军骑兵追来。只见远方尘土飞扬，杀声震天。汉军本来已十分疲惫，这时队伍大哗。韩信急速点兵迎敌。他命令士兵3人一排，结果多出2名；接着命令士兵5人一排，结果多出3名；他又命令士兵7人一排，结果又多出2名。韩信马上向将士们宣布：我军有1073人，敌人不足五百，我们居高临下，以众击寡，一定能打败敌人。一个数除以3余2，除以5余3，除以7余2，求符合条件的最小数. 解：第1步 先列出满足

4、其中一个条件的数（一般从小到大），即除以3余2的数： 2， 5， 8， 11， 14， 17， 20， 23， 26， 第2步再列出满足其中第二个条件的数，即除以5余3的数： 3， 8， 13， 18， 23， 28，. 第3步归纳前面第3步首先出现的公共数是8.8就是满足除以3余2，除以5余3的最小的那个数。 3与5的最小公倍数是15.两个条件合并成一个就是815n (n=0，1，2，)。列出这一串数是8， 23， 38，第4步再列出满足其中第三个条件的数，即除以7余2的数 2， 9， 16， 23， 30， 第5步归纳第3步第4步得到的数列。就得出符合题目条件的最小数是23. 事实上，我们

5、已把题目中三个条件合并成一个。3，5，7的最小公倍数是 105 ，满足三个条件的所有数是23+105n(n=0，1，2，) 第6步那么韩信点的兵在1000-1100之间，应该是23+10510=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既

6、是3与5的倍数，又是以7去除余1的数），第4步将这些数加起来，若超过105（105是3,5,7的最小公倍数），就减掉105，如果剩下来的数目还是比105大，就再减去105，直到得数比105小为止。这样，所得的数就是原来的数了。根据这个道理，你可以很容易地把前面的题目列成算式：170221215105 142105 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正

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必满足0N385】，所以当 231a+330b+210c 大于或等于385时，还必须减去若干个385 直到比385小为止，才可以得到符合题意要求的最小数。【说明】231a+330b+210c + 385k 也一定满足“除以5,7,11以后所得余数分别是a,b,c”。【例5】求最小非负整数N，使他在除以5,7,11以后所得余数分别是3,5

8、,7。【解】231a+330b+210c=2313+3305+2107=3813.因为 3813385，所以减去9个385后，得到比385小的 3813-9385=348 就是符合题意的最小非负整数了这些题可转化为余数问题解决。如果你知道中国剩余定理，可直接用，如果不知道，也没有关系，可采取余数常用方法，先找一个最小的满足第一个数，然后调整一下满足第二个数，再调整满足第三个数。在调整时，一定不要改变你前面已经满足的数的特点，每次加前面已经满足的数的最小公倍数，这样它的余数就不会被改变。课堂练习(用上面介绍的两种方法)1 有一个数，除以3余1，除以5余3，问这个数除以16余几？ 2 韩信带150

9、0名兵士打仗，战死四五百人。韩信令活着的兵士3人站一排，多出2人；5人站一排，多出4人；7人站一排，多出6人。韩信有多少士兵？ 人数：1049 3 有一堆苹果五个五数剩3，七个七数剩1，九个九数剩2，这堆苹果最少有多少个？同余问题 上面的问题，也有人称为“韩信点兵”.它形成了一类问题，也就是初等数论中的解同余式。一 同余的定义： 如果两个正整数a和b除以n后余数相同，那么我们就说 a和 b关于模n同余，记作：a b (mod n) 读作a与b同余，mod为n。或者a同余于b模m表示同余关系的数学表达式，与等式相似。将等式中的等号“=”换成同余符号“”，在式尾缀以(mod n) 注明模n（即除数

10、），就是同余式。含有未知数的同余式叫做同余方程，求未知数的值就是解同余式。上面求到余数的和或者积，如果比除数大，所求的余数等于余数的和或者积再除以c的余数。三 弃九法原理： 检验算式是不是正确的1234除以9的余数为1， 1898除以9的余数为8， 18922除以9的余数为4，678967除以9的余数为7， 178902除以9的余数为0，这些余数的和除以9的余数为2 而等式右边和除以9的余数为3，那么上面这个算式一定是错的。上述检验方法恰好用到的就是我们前面所讲的余数的加法定理，即如果这个等式是正确的，那么左边几个加数除以9的余数的和再除以9的余数一定与等式右边和除以9的余数相同。而我们在求一

11、个自然数除以9所得的余数时，常常不用去列除法竖式进行计算，只要计算这个自然数的各个位数字之和除以9的余数就可以了，在算的时候往往就是一个9一个9的找并且划去，所以这种方法被称作“弃九法”。即 ：任何一个整数模9同余于它的各数位上数字之和。这个特性，不仅可以检验几个数相加的结果有没有错误，对于检验相乘、相除和乘方的结果对不对同样适用注意：弃九法只能知道原题一定是错的或有可能正确，但不能保证一定正确。例如：检验算式9+9=9时，等式两边的除以9的余数都是0，但是显然算式是错误的但是反过来，如果一个算式一定是正确的，那么它的等式2两端一定满足弃九法的规律。(注)X6000能够被8除尽，故（2）式里不

12、列出它先试除得3对19可除尽，把1919个2对19一组折算成为3对19一组，即3838个19。3837个可以除尽，剩下下一个就是余数。 97+23=120 答 ；除数与余数的和是120练习1 有两个自然数相除，商是，余数是，已知被除数、除数、商与余数之和为，则被除数是多少？【解析】 被除数除数商余数被除数除数+17+13=2113，所以被除数除数=2083，由于被除数是除数的17倍还多13，则由“和倍问题”可得：除数=(2083-13)(17+1)=115，所以被除数=2083-115=19682已知2008被一些自然数去除，所得的余数都是10，那么这样的自然数共有多少个？【解析】 本题为一道

13、余数与约数个数计算公式的小综合性题目由题意所求的自然数一定是2008-10即1998的约数，同时还要满足大于10这个条件这样题目就转化为1998有多少个大于10的约数，共有(1+1)(3+1)(1+1)=16个约数，其中1，2，3，6，9是比10小的约数，所以符合题目条件的自然数共有11个3有一个整数，除39，51，147所得的余数都是3，求这个数【解析】 (法1) ，12的约数是，因为余数为3要小于除数，这个数是；(法2)由于所得的余数相同，得到这个数一定能整除这三个数中的任意两数的差，也就是说它是任意两数差的公约数，所以这个数是4有一个整数，用它去除70，110，160所得到的3个余数之和

14、是50，那么这个整数是_【解析】 ，除数应当是290的大于17小于70的约数，只可能是29和58，所以除数不是58，所以除数是5用自然数n去除63，91，129得到的三个余数之和为25，那么n=_【解析】 n能整除因为，所以n是258大于8的约数显然，n不能大于63符合条件的只有436一个大于10的自然数去除90、164后所得的两个余数的和等于这个自然数去除220后所得的余数，则这个自然数是多少？【解析】 这个自然数去除90、164后所得的两个余数的和等于这个自然数去除后所得的余数，所以254和220除以这个自然数后所得的余数相同，因此这个自然数是的约数，又大于10，这个自然数只能是17或者是

15、34如果这个数是34，那么它去除90、164、220后所得的余数分别是22、28、16，不符合题目条件；如果这个数是17，那么他去除90、164、220后所得的余数分别是5、11、16，符合题目条件，所以这个自然数是177甲、乙、丙三数分别为603，939，393某数除甲数所得余数是除乙数所得余数的2倍，除乙数所得余数是除丙数所得余数的2倍求等于多少？【解析】 根据题意，这三个数除以都有余数，则可以用带余除法的形式将它们表示出来：由于，要消去余数， ， ，我们只能先把余数处理成相同的，再两数相减这样我们先把第二个式子乘以2，使得被除数和余数都扩大2倍，同理，第三个式子乘以4于是我们可以得到下面

16、的式子：这样余数就处理成相同的最后两两相减消去余数，意味着能被整除51的约数有1、3、17、51，其中1、3显然不满足，检验17和51可知17满足，所以等于178 与的和除以7的余数是_【解析】 找规律用7除2，的余数分别是2，4，1，2，4，1，2，4，1，2的个数是3的倍数时，用7除的余数为1；2的个数是3的倍数多1时，用7除的余数为2；2的个数是3的倍数多2时，用7除的余数为4因为，所以除以7余4又两个数的积除以7的余数，与两个数分别除以7所得余数的积相同而2003除以7余1，所以除以7余1故与的和除以7的余数是【巩固】 除以7的余数是多少？【解析】 除以7的余数为1，所以，其除以7的余

17、数为：；2008除以7的余数为6，则除以7的余数等于除以7的余数，为1；所以除以7的余数为：【例 1】 (2009年走美初赛六年级)有一串数：1，1，2，3，5，8，从第三个数起，每个数都是前两个数之和，在这串数的前2009个数中，有几个是5的倍数？【解析】 由于两个数的和除以5的余数等于这两个数除以5的余数之和再除以5的余数所以这串数除以5的余数分别为：1，1，2，3，0，3，3，1，4，0，4，4，3，2，0，2，2，4，1，0，1，1，2，3，0，可以发现这串余数中，每20个数为一个循环，且一个循环中，每5个数中第五个数是5的倍数由于，所以前2009个数中，有401个是5的倍数【巩固】著

18、名的裴波那契数列是这样的：1、1、2、3、5、8、13、21这串数列当中第2008个数除以3所得的余数为多少？【解析】 斐波那契数列的构成规则是从第三个数起每一个数都等于它前面两个数的和，由此可以根据余数定理将裴波那契数列转换为被3除所得余数的数列：1、1、2、0、2、2、1、0、1、1、2、0第九项和第十项连续两个是1，与第一项和第二项的值相同且位置连续，所以裴波那契数列被3除的余数每8个一个周期循环出现，由于2008除以8的余数为0，所以第2008项被3除所得的余数为第8项被3除所得的余数，为0【例 2】 (1997年全国小学数学奥林匹克试题)将依次写到第1997个数字，组成一个1997位

19、数，那么此数除以9的余数是 _【解析】 本题第一步是要求出第1997个数字是什么，再对数字求和共有9个数字，共有90个两位数，共有数字： (个)， 共900个三位数，共有数字： (个)，所以数连续写，不会写到999，从100开始是3位数，每三个数字表示一个数，即有602个三位数，第603个三位数只写了它的百位和十位从100开始的第602个三位数是701，第603个三位数是9，其中2未写出来因为连续9个自然数之和能被9整除，所以排列起来的9个自然数也能被9整除，702个数能分成的组数是： (组)，依次排列后，它仍然能被9整除，但702中2未写出来，所以余数为【例 3】 有2个三位数相乘的积是一个

20、五位数，积的后四位是1031，第一个数各个位的数字之和是10，第二个数的各个位数字之和是8，求两个三位数的和【解析】 本题条件仅给出了两个乘数的数字之和，同时发现乘积的一部分已经给出，即乘积的一部分数字之和已经给出，我们可以采用弃九法原理的倒推来构造出原三位数因为这是一个一定正确的算式，所以一定可以满足弃九法的条件，两个三位数除以9的余数分别为1和8，所以等式一边除以9的余数为8，那么1031除以9的余数也必须为8，只能是3将31031分解质因数发现仅有一种情况可以满足是两个三位数的乘积，即所以两个三位数是143和217，那么两个三位数的和是360【例 4】 设的各位数字之和为，的各位数字之和

21、为，的各位数字之和为，的各位数字之和为，那么？【解析】 由于一个数除以9的余数与它的各位数字之和除以9的余数相同，所以与、 除以9都同余，而2009除以9的余数为2，则除以9的余数与除以9的余数相同，而除以9的余数为1，所以除以9的余数为除以9的余数，即为5另一方面，由于，所以的位数不超过8036位，那么它的各位数字之和不超过，即；那么的各位数字之和，的各位数字之和，小于18且除以9的余数为5，那么为5或14，的各位数字之和为5，即 同余补充练习1有四个自然数A、B、C、D，它们的和不超过400，并且A除以B商是5余5，A除以C商是6余6，A除以D商是7余7。那么，这四个自然数的和是?A. 2

22、16 B. 108 C. 314 D. 348【解析】利用余数基本恒等式：被除数=除数商+余数，有A=B5+5= (B+1)5。由于A、B均是自然数，于是A可以被5整除，同理，A还可以被6、7整除，因此，A可以表示为5、6、7的公倍数，即210n。由于A、B、C、D的和不超过400，所以A只能等于210，从而可以求出B=41、C=34、D=29，得到A+B+C+D=314，选C。2一个三位数除以9余7，除以5余2，除以4余3，这样的三位数共有多少个?A. 5个 B. 6个 C. 7个 D. 8个解析：除以5余2，除以4余3，我们知道除数与对应余数的和相同，对应的为“和同加和”，满足这两个条件的

23、数可以表示为，P=20n+7，表示除以20余7;再配上之前的条件除以9余7，对应的为“余同取余”，我们得到这个数可以表示为180n+7，由于这个数为三位数，所以n可以取1、2、3、4、5，所以共5个。3有一个整数用它去除63，91，129得到的3个余数的和是25，这个整数是多少？一个整数去除63，91，129得到的3个余数的和是25则（63+91+129）除以这个数的余数是25即：63+91+129-25=258能够被这个数整除。而258=2343所以这个数可能是：2、3、43、6、86、129又这个数应小于63，且大于9（8325）所以这个数是434自然数m除13511、13903和1458

24、9，余数都相同，m的最大值是多少？因为m除13511、13903和14589，余数都相同，所以，13903-13511=392和14589-13903=686都能被m整除。而392和686的最大公约数是98，也就求出了m的最大值是98。55555.（一共2000个5）除以13所得的余数是多少？记住这个，很多题目都用得到。71113=1001 1111001=111111 连续的6个1，能被7或13整除6：在1、2、3、4、1993、1994这1994个数中，选出一些数，使得这些数中的每两个数的和都能被26整除，那么这样的数最多能选出_个。（1994年全国小学数学奥林匹克初赛试题） 思路：选出的

25、这些数必须具备条件：除以26的余数为13。只有这样，任意两个数相加才能能被26整除。于是，这些数构成一个首项为13，公差为26的等差数列。设共有n项，则an=13+(n-1)26=26n-13令an1994，则26n-131994，n2007/26因为n是正整数，所以n77那么这样的数最多能选出77个。7在1、2、3、4、1998、1999这1999个数中，选出一些数，使得这些数中的每两个数的和都能被48整除，那么这样的数最多能选出_个。 8有一个整数，除1200，1314，1048所得的余数相同且大于5.问：这个数与余数的和是多少？9用一个自然数去除715和903所得余数相同，且商相差4.求

26、这个数.10：在1、2、3、30这30个自然数中，最多能取出_个数，使取出的这些数中，任意两个不同的数的和都不是7的倍数。从自然数130中，最多取出多少个数，才能使取出的这些数里任意两个数之和都不是7的倍数？这30个自然数按除以7的余数可以分为7类：余0：7，14，21，28余1：1，8，15，22，29余2：2，9，16，23，30余3：3，10，17，24余4：4，11，18，25余5：5，12，19，26余6：6，13，20，27其中第一组最多只能取一个，组都不能同时取于是最多可以取1+5+5+4=15个11在1、2、3、30这30个自然数中，最多能取出_个数，使取出的这些数中，任意两个

27、不同的数的和都不是6的倍数。12某数被2000除，余1993；被1999除，余1992；被1998除，余1991.求某数最小是多少？ 注意到，此数相当于 2000、1999、1998的公倍数减去7所以 此数最小为 2000、1999、1998的最小公倍数减去7也就是 1000*1999*1998-7=3994002000-7=399400199313.某数用5除余3，用7除余5，用9除余7，用11除余9.求某数最小是多少？14.某数被5、6、7除，都得到相同的余数1.问某数在1000以内有哪几个答案？15、要使五位数12ABC能被36整除，而且所得到的商尽量小，那么这个五位数是多少？36=49，要使12abc能被36整除，则：12abc数字和必须是9的倍数，后两位必须能被4整除。1+2+A+B+C=9的倍数，得出A+B+C=610B+C能被4整除。得出BC分别为04, 08 12 16 20 24.。除数一定，商最小，只有被除数最小，先令A=0，这时B+C =6 综合上面，要求的数是1202416 六位数15abc6能被36整除,要使商最大,A、B、C分别是多少？要使商最小,A、B、C分别是多少？17 解同余方程组 x1(mod 6) x4(mod 9)x7(mod 15)x67（mod 90）18 19 答 4【精品文档】第 8 页