余数问题

中国剩余定理程卫华收集整理136879887481民间传说着一则故事——“韩信点兵”。秦朝末年，楚汉相争。一次，韩信将1500名将士与楚王大将李锋交战。苦战一场，楚军不敌，败退回营，汉军也死伤四五百人，于是韩信整顿兵马也返回大本营。当行至一山坡，忽有后军来报，说有楚军骑兵追来。只见远方尘土飞扬，杀声震天。汉军本来已十分疲惫，这时队伍大哗。韩信兵马到坡顶，见来敌不足五百骑，便急速点兵迎敌。他命令士兵3人一排，结果多出2名；接着命令士兵5人一排，结果多出3名；他又命令士兵7人一排，结果又多出2名。韩信马上向将士们宣布：我军有1073名勇士，敌人不足五百，我们居高临下，以众击寡，一定能打败敌人。汉军本来就信服自己的统帅，这一来更相信韩信是“神仙下凡”、“神机妙算”。于是士气大振。一时间旌旗摇动，鼓声喧天，汉军步步进逼，楚军乱作一团。交战不久，楚军大败而逃。解：一个数除以3余2，除以5余3，除以7余2，求适合此条件的最小数解答:23。70×2＋21×3+15×2-105×2＝23那么韩信点的兵在1000-1500之间，应该是70×2＋21×3+15×2+105×9=1073在我国古代算书《孙子算经》中有这样一个问题：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？意思是，一个数除以3余2，除以5余3，除以7余2.求适合这个条件的最小数.这个问题称为孙子问题.关于孙子问题的一般解法，国际上称为中国剩余定理.如何求符合上述条件的正整数N呢？《孙子算经》给出了一个非常有效的巧妙解法。术曰：“三、三数之剩二，置一百四十；五、五数之剩三，置六十三；七、七数之剩二，置三十，并之，得二百三十三。以二百一十减之，即得。凡三、三数之剩一，则置七十；五、五数之剩一，则置二十一；七、七数之剩一，则置十五。一百六以上，一百五减之，即得。”过了一千多年，到了十六世纪，数学家程大位在他所著的《算法统宗》里把这个问题的解法用歌诀形式表述出来。三人同行七十稀，五树梅花廿一枝，七子团圆正月半，除百零五便得之。歌诀的前三句给出了三组数，后一句给出了一个数：3——70，5——21，7——15，105三组数的共同特征是：70除以3余1，除以5、7余0；21除以5余1，除以3、7余0；15除以7余1，除以3、5余0。统统相加得和：N=2×70+3×21+2×15=233。N必然满足原题所有三个余数条件。但N不一定是最小的。歌诀最后一句“除百零五便得知”，这里“除”的意思是“减”，意即从233中减去3、5、7的最小公倍数105的倍数便得到23。这个23就是问题的最小解。这最后一句也可以理解为N除以105的余数就是问题的最小解。128÷105=1……余23.1、(五年级)有一个数，除以3余2，除以4余1，问这个数除以12余几？答：一个数，除以3余2，除以4余1，可以理解为除以3余3+2，除以4余4+1，所以这个数减去5后，既能被3整除，又能被4整除，设这个数为a，则a=12m+5（m为自然数），所以这个数除以12余5.答：除以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.2、(五年级)一个小于200的数，它除以11余8，除以13余10，这个数是多少？答：我们发现这两个除数与余数的差都等于11-8=13-10=3，可知这个数加上3后就能同时被11和13整除，而[11,13]=143，这个数又要在200以内，所以这个数是143-3=1403、(五年级)一个大于10的数，除以3余1，除以5余2，除以11余7，问满足条件的最小自然数是多少？答：仔细分析发现，所以这个数可以看成被3,5,11除余7，由于[3,5,11]=165,所以这个数最小是165+7=1724、5、(六年级)在200至300之间，有三个连续的自然数，其中，最小的能被3整除，中间的能被7整除，最大的能被13整除，那么这样的三个连续自然数分别是多少？答：先找出两个连续的自然数，第一个被3整除，第二个被7整除，例如，找出6和7，下一个连续自然数是8。3和7的最小公倍数是21，考虑8加上21的整数倍，使加得的数能被13整除。8＋21×12＝260，能被13整除，那么258,259,260这三个连续自然数，依次分别能被3,7,13整除，又恰好在200至300之间，由于3,7,13的最小公倍数为273，所以在200至300之间只有258,259,260这三个数满足条件6、一个数被5除余2，被6除少2，被7除少3，这个数最小是多少？解法：题目可以看成，被5除余2，被6除余4，被7除余4。看到那个“被6除余4，被7除余4”了么，有同余数的话，只要求出6和7的最小公倍数，再加上4，就是满足后面条件的数了，6X7＋4＝46。下面一步试下46能不中国剩余定理程卫华收集整理136879887482能满足第一个条件“一个数被5除余2”。不行的话，只要再46加上6和7的最小公倍数42，一直加到能满足“一个数被5除余2”。这步的原因是，42是6和7的最小公倍数，再怎么加都会满足“被6除余4，被7除余4”的条件。46＋42＝88，46＋42＋42＝130，46＋42＋42＋42＝172这是一种形式的，它的前提是条件中出现同余数的情况，如果遇到没有的，下面讲7、一个班学生分组做游戏，如果每组三人就多两人，每组五人就多三人，每组七人就多四人，问这个班有多少学生？解法：题目可以看成，除3余2，除5余3，除7余4。没有同余的情况，用的方法是“逐步约束法”，就是从“除7余4的数”中找出符合“除5余3的数”，就是再7上一直加4，直到所得的数除5余3。得出数为18，下面只要在18上一直加7和5得最小公倍数35，直到满足“除3余2”4＋7＝11，11＋7＝18，18＋35＝5325、一个数除以3余2，除以5余3，除以7余4，问满足条件的最小自然数____.35的公倍数37的公倍数57的公倍数15213530427045631056084140………除以7余4的除以5余3除以3余2分别是：606335可见60+63+35=158满足我们的条件，但不是最小的自然数，处理方法就是减去最小公倍数的若干倍，使结果在最小公倍数之内。所以答案为：158-105=53。8、有一个年级的同学，每9人一排多6人，每7人一排多2人，每5人一排多3人，问这个年级至少有多少人？答：题中9、7、5三个数两两互质。则〔7，5〕=35；〔9，5〕=45；〔9，7〕=63；〔9，7，5〕=315。为了使35被9除余1，用35×8=280；使45被7除余1，用45×5=225；使63被5除余1，用63×2=126。然后，280×6＋225×2＋126×3=2508，因为，2508315，所以，2508－315×7=303，就是所求的数。26、有一个年级的同学,每9人一排多5人,每7人一排多1人,每5人一排多2人,问这个年级至少有多少人?5和9的公倍数依次是45、90、135、180、225……这些公倍数中，被7除余1的数是2259和7的公倍数依次是63、126、189、252……这其中，被5除余2的是2525和7的公倍数是35、70、105、140、……其中被9除余5的是140把以上225252140三个数相加，求得225+252+140=617，而579三个数的最小公倍数是5*7*9=315617-315=302因此302就是这个年级至少人数。9、有一个年级的同学，每9人一排多5人，每7人一排多1人，每5人一排多2人，问这个年级至少有多少人？答：题中9、7、5三个数两两互质。则〔7，5〕=35；〔9，5〕=45；〔9，7〕=63；〔9，7，5〕=315。为了使35被9除余1，用35×8=280；使45被7除余1，用45×5=225；使63被5除余1，用63×2=126。然后，280×5＋225×1＋126×2=1877，因为，1877315，所以，1877－315×5=302，就是所求的数。10、一个数被3除余2，被7除余4，被8除余5，这个数最小是几？答：题中3、7、8三个数两两互质。则〔7，8〕=56；〔3，8〕=24；〔3，7〕=21；〔3，7，8〕=168。为了使56被3除余1，用56×2=112；使24被7除余1，用24×5=120。使21被8除余1，用21×5=105；然后，112×2＋120×4＋105×5=1229，因为，1229168，所以，1229－168×7=53，就是所求的数。11、一个数除以5余4，除以8余3，除以11余2，求满足条件的最小的自然数。答：题中5、8、11三个数两两互质。则〔8，11〕=88；〔5，11〕=55；〔5，8〕=40；〔5，8，11〕=440。为了使88被5除余1，用88×2=176；使55被8除余1，用55×7=385；使40被11除余1，用40×8=320。然后，176×4＋385×3＋320×2=2499，因为，2499440，所以，2499－440×5=299，就是所求的数。12、一个数被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，因为，27460，所以，274－60×4=34，就是所求的数。13、有一个数，除以3余数是1，除以4余数是3，这个数除以12余数是_7_.答：因为除以3余数是1的数是1,4,7,10,13,16,19,22,25,28,31,…中国剩余定理程卫华收集整理136879887483除以4余数是3的数是3,7,11,15,19,23,27,31…所以，同时符合除以3余数是1，除以4余数是3的数有7，19，31，…这些数除以12余数均为714、一个两位数,用它除58余2,除73余3,除85余1,这个两位数是_14_.答：用一个两位数除58余2,除73余3,除85余1,那么58-2=56,73-3=70,85-1=84能被这个两位数整除,这个两位数一定是56、70和84的公约数.56，70，84，除2后得28，35，42，除7后得4，5，6由可可见,56、70、84的两位数公约数是27=14，可见这个两位数是14.15、学习委员收买练习本的钱,她只记下四组各交的钱,第一组2.61元,第二组3.19元,第三组2.61元,第四组3.48元,又知道每本练习本价格都超过1角,全班共有41人.答：319-261=练习本单价第二、一组人数之差，348-319=练习本单价第四、二组人数之差.即练习本单价第二、一组人数之差=58,练习本单价第四、二组人数之差=29，所以,练习本单价是58与29的公约数,这样,练习本的单价是29分,即0.29元.因此,全班人数是(2.612+3.19+3.48)0.29=11.890.29=41(人)16、五年级两个班的学生一起排队出操,如果9人排一行,多出一个人；如果10人排一行，同样多出一个人.这两个班最少共有_91_人.答：如果将两个班的人数减少1人,则9人一排或10人一排都正好排完没有剩余,所以两班人数减1是9和10的公倍数,又要求这两班至少有几人,可以求出9和10的最小公倍数,然后再加上1.所以,这两个班最少有91(人)17、一个数能被3、5、7整除，若用11去除则余1，这个数最小是_210.答：一个数能被3,5,7整除,这个数一定是3,5,7的公倍数.3,5,7的公倍数依次为:105,210,315,420,……，其中被11除余数为1的最小数是210，所以这个最小数是21018、（六年级）大科学家爱因