同余法解题完整版

同余法解题集团标准化办公室：同余法解题集团标准化办公室：[VV986T-J682P28-JP266L8-68PNN]五年级奥数培训资料第六讲同余法解题一、同余这个概念最初是由德国数学家高斯发明的。同余的定义是这样的：两个整数，a,b，如果他们同时除以一个自然数m,所得的余数相同，则称a,b对于模m同余。。记作a三b(mod.m)。读作：a同余于b模m。同余的性质也比较多，主要有以下一些：对于同一个除数，两个数的乘积与它们余数的乘积同余。例如201X95的乘积对于除数7,与201F7的余数5和95F7的余数4的乘积20对于7同余。对于同一个除数，如果有两个整数同余，那么它们的差就一定能被这个除数整除。例如519和399对于一个除数同余，那么这个除数一定是519与399的差的因数，即519与399的差一定能被这个除数整除。对于同一个除数，如果两个数同余，那么他们的乘方仍然同余。例如20和29对于一个除数同余，那么20的任何次方都和29的相同次方对于这个除数同余，当然余数大小随次方变化。对于同一个除数，若三个数a三b(modm),b三c(modm),那么a,b,c三个数对于除数m都同余(传递性)例如60和76同余于模8，76和204同余于模8，那么60,76,204都同余于模8。对于同一个除数， 若四个数a三b(modm)，c三d(modm)，那么a土c三c土d(modm)，(可加减性)对于同一个除数，若四个数a三b(modm)，c三d(modm)，那么ac三cd(modm)，(可乘性)二、 中国剩余定理解法一个数被3除余1，被4除余2，被5除余4，这个数最小是几？解法：求3个数：第一个：能同时被3和4整除，但除以5余4,即12X2=24第二个：能同时被4和5整除，但除以3余1,即20X2=40第三个：能同时被3和5整除，但除以4余2,即15x2=30这3个数的最小公倍数为60，所以满足条件的最小数字为24＋40+30-60=3412X2=2420X2=40 15x2=30中2的来历。三、 解题技巧同余口诀：“差同减差，和同加和，余同取余，最小公倍n倍加”这是同余问题的口诀。、差同减差：用一个数除以几个不同的数，得到的余数，与除数的差相同，此时反求的这个数，可以选除数的最小公倍数，减去这个相同的差数，称为：“差同减差”。例：“一个数除以4余1，除以5余2，除以6余3”，因为4-1=5-2=6-3=3，所以取-3,表示为60-3或者60n-3、和同加和：用一个数除以几个不同的数，得到的余数，与除数的和相同，此时反求的这个数，可以选除数的最小公倍数，加上这个相同的和数，称为：“和同加和”。例：“一个数除以4余3，除以5余2，除以6余1”，因为4+3=5+2=6+1=7，所以取+7,表示为60n+7。、余同取余：用一个数除以几个不同的数，得到的余数相同，此时反求的这个数，可以选除数的最小公倍数,加上这个相同的余数,称为：“余同取余”。例：“一个数除以4余1,除以5余1,除以6余1”,因为余数都是1,所以取+1,表示为60n+1。、最小公倍加：所选取的数加上除数的最小公倍数的任意整数倍(即上面1、2、3中的60n)都满足条件，称为：“最小公倍n倍加”，也称为：“公倍数作周期”。三、例题解评例1：判定288和214对于模37是否同余思路点拨：可直接由定义判断。解：•••288-214=74=37X2・・・288三214(mod37)例2、用412、133和257除以一个相同的自然数，所得的余数相同，这个自然数最大是几？【解析】假设这个自然数是a,因为412.133和257除以a所得的余数相同，所以aI(412—133),a|(412—257),a|(257—133)，说明a是以上三个数中任意两数差的约数，要求最大是几，就是求这三个差的最大公约数。(155,124,279)=31,所以a最大是31。例3、249X388X234除以19，余数是几？【解析】如果把三个数相乘的积求出来再除以19，就太麻烦了，利用同余思想解决就容易了。因为249三2(mdo19),388三8(mdo19),234三6(mdo19),所以249X388X234三2X8X6三1(mdo19)此题应用了同余的可乘性，同余的传递性。例4：求1992X59除以7的余数。思路点拨：可应用性质2,将1992X59转化为求1992除以7和59除以7的余数的乘积，使计算简化。解：T1992三4(mod7),59三3(mod7)・••根据性质5可得：1992X59三4X3(mod7),余数为12F7的余数。答：1992X59除以7的余数是5。例5：自然数16520、14903、14177除以m的余数相同，m的最大值是多少？思路点拨：自然数16520、14903、14177除以m的余数相同，也就是16520三14903三14177(modm)根据同余补充定义，这三个数同余，那么它们的差就能被m整除。要求m最大是多少，就是求它们差的最大公约数是多少。解：因为16520-14903=161716520-14177=234314903-14177=726(1617、2343、726)=33所以m的最大值是33。〖评注〗实际上，这三个差数还可以继续两两相减，得到1617-726=891,891-726=165，算出726和165的最大公约数即可，通常其结果与上面相同。例6：在除13511，13903，及14598时能剩下相同余数的最大整数是几？思路点拨：根据同余的性质，若几个数被同一个数除，余数相同，则这几个数中两两相减的差必能被这个数整除。所以这个数应是这三个数两两相减后所得数的最大公约数。解：这两个数两两只减的差是：13903-13511=39214598-13903=68614589-13511=1078因为(392，686，1078)=98，所以这个数是98。也可以以上三个差再两两相减，得686-392=294，再392-294=98答：这个最大整数是98。例7：一个三位数除以9余7，除以5余2，除以4余3。这样的三位数共有几个？思路点拨：由中国剩余定理解法求。解法：求3个数：第一个：能同时被9和5整除，但除以4余3,即45X3=135第二个：能同时被4和5整除，但除以9余7,即20X8=160第三个：能同时被9和4整除，但除以5余2,即36x2=72这3个数的最小公倍数为180，所以满足条件的最小数字为135＋160+72-180=1877+180X5=907V1000?7+180X6=1087>1000所以符合条件的三位数共有5个。分别是7+180Xn(n=1,2,4,5).答：这样的三位数共有5个。222……2例8、有一个1997位数，它的每个数位都是2,1997个2这个数除以13,商的第100位是几最后余数是几222……2< /【解析】1^7个2这个数除以13,商是有规律的。商是170940六个数循环，那么……4行卩，我们从左向右数“170940”的第4个数就是我们找的那个数“9”,所以商的第100位是9。余数是几呢则1996三4(mod6)解析过程：本题商共有1996位，每6位循环，共有332次循环后余4，所以商的个位数字应是“170940”中的第4个，商应是9，个位的余数就对应商为9时的余数5。三、练习题求下列算式中的余数。Ill……1 222……2（1）1997个1十7（2）1997牛2十7333……3 444……4''■V ' V'（3）199丁牛3 〜13（4）199丁个4 「132、 6254与37的积除以7，余数是几？3、 如果某数除482，992，1094都余74，这个数是几？4、 300、262、205被同一个整数除，得到相同的余数，这个整数是几？5、 一个自然数被247除余63，被248除余63，求这个自然数被26除的余数。6、 一个自然数N被10除余9,被9除余8,被8除余7,被7除余6,被6除余5,被5除余4,被4除余3