同余法解题.doc

(完整word)同余法解题五年级奥数培训资料第六讲 同余法解题 一、 同余这个概念最初是由德国数学家高斯发明的。同余的定义是这样的： 两个整数，a，b，如果他们同时除以一个自然数m,所得的余数相同，则称a，b对于模m同余。记作ab（mod.m）。读作：a同余于b模m。 同余的性质也比较多，主要有以下一些：1.对于同一个除数,两个数的乘积与它们余数的乘积同余。例如20195的乘积对于除数7，与2017的余数5和957的余数4的乘积20对于7同余。2.对于同一个除数，如果有两个整数同余，那么它们的差就一定能被这个除数整除。例如519和399对于一个除数同余,那么这个除数一定是519与399的差的因数,即519与399的差一 定能被这个除数整除。3.。对于同一个除数，如果两个数同余，那么他们的乘方仍然同余。 例如20和29对于一个除数同余，那么20的任何次方都和29的相同次方对于这个除数同余,当然余数大小随次方变化。4对于同一个除数，若三个数ab（mod m），bc（mod m），那么a，b,c三个数对于除数m都同余 （传递性)例如60和76同余于模8，76和204同余于模8,那么60,76,204都同余于模8.5。 对于同一个除数， 若四个数ab（mod m),cd（mod m)，那么accd（mod m)，（可加减性）6。 对于同一个除数， 若四个数ab（mod m),cd(mod m）,那么accd（mod m），（可乘性）二、中国剩余定理解法一个数被3除余1，被4除余2，被5除余4，这个数最小是几?解法：求3个数:第一个:能同时被3和4整除，但除以5余4，即12X224第二个:能同时被4和5整除，但除以3余1，即20X240第三个：能同时被3和5整除，但除以4余2，即15x230这3个数的最小公倍数为60，所以满足条件的最小数字为2440+30-60=3412X224 20X240 15x230中2的来历.三、解题技巧同余口诀：“差同减差，和同加和，余同取余，最小公倍n倍加”这是同余问题的口诀。1）、差同减差：用一个数除以几个不同的数,得到的余数，与除数的差相同,此时反求的这个数，可以选除数的最小公倍数,减去这个相同的差数，称为：“差同减差”。例:“一个数除以4余1,除以5余2，除以6余3，因为4-1=5-2=63=3,所以取3，表示为603或者60n-32）、和同加和:用一个数除以几个不同的数，得到的余数，与除数的和相同，此时反求的这个数，可以选除数的最小公倍数，加上这个相同的和数，称为:“和同加和”.例：“一个数除以4余3,除以5余2,除以6余1”，因为4+3=5+2=6+1=7,所以取+7，表示为60n+7。3)、余同取余：用一个数除以几个不同的数，得到的余数相同，此时反求的这个数，可以选除数的最小公倍数,加上这个相同的余数，称为:“余同取余”.例：“一个数除以4余1,除以5余1，除以6余1”，因为余数都是1，所以取+1,表示为60n+1。4）、最小公倍加：所选取的数加上除数的最小公倍数的任意整数倍（即上面1、2、3中的60n)都满足条件，称为：“最小公倍n倍加”，也称为:“公倍数作周期. 三、例题解评例1:判定288和214对于模37是否同余思路点拨：可直接由定义判断.解：288214=74=372288214(mod 37）例2、 用412、133和257除以一个相同的自然数,所得的余数相同，这个自然数最大是几？【解析】假设这个自然数是a,因为412、133和257除以a所得的余数相同，所以a(412133），a(412257）,a(257133)，说明a是以上三个数中任意两数差的约数，要求最大是几，就是求这三个差的最大公约数。（155,124,279）=31，所以a最大是31。 例3、 249388234除以19,余数是几？【解析】如果把三个数相乘的积求出来再除以19,就太麻烦了,利用同余思想解决就容易了。因为2492（mdo19）, 3888（mdo19)，2346（mdo19),所以2493882342861（mdo19）此题应用了同余的可乘性，同余的传递性。例4：求199259除以7的余数。思路点拨：可应用性质2,将199259转化为求1992除以7和59除以7的余数的乘积,使计算简化。解:19924（mod 7），593（mod 7）根据性质5可得：19925943（mod 7)，余数为127的余数。答：199259除以7的余数是5.例5:自然数16520、14903、14177除以m的余数相同，m的最大值是多少？思路点拨：自然数16520、14903、14177除以m的余数相同,也就是165201490314177（mod m）根据同余补充定义,这三个数同余，那么它们的差就能被m整除.要求m最大是多少，就是求它们差的最大公约数是多少。解：因为16520-14903=16171652014177=23431490314177=726（1617、2343、726)=33所以m的最大值是33。评注实际上，这三个差数还可以继续两两相减,得到1617726=891，891-726=165，算出726和165的最大公约数即可，通常其结果与上面相同。例6：在除13511,13903，及14598时能剩下相同余数的最大整数是几？思路点拨：根据同余的性质，若几个数被同一个数除，余数相同，则这几个数中两两相减的差必能被这个数整除.所以这个数应是这三个数两两相减后所得数的最大公约数。解：这两个数两两只减的差是 ：13903-13511=3921459813903=68614589-13511=1078因为(392,686，1078）=98，所以这个数是98。也可以以上三个差再两两相减，得686392=294，再392-294=98答：这个最大整数是98.例7:一个三位数除以9余7，除以5余2，除以4余3。这样的三位数共有几个?思路点拨:由中国剩余定理解法求.解法：求3个数:第一个:能同时被9和5整除，但除以4余3，即45X3135第二个:能同时被4和5整除，但除以9余7，即20X8160第三个：能同时被9和4整除，但除以5余2，即36x272这3个数的最小公倍数为180，所以满足条件的最小数字为135160+72-180=18771805=907 100071806=10871000所以符合条件的三位数共有5个。分别是7180n（n=1，2，4,5).答:这样的三位数共有5个.例8、 有一个1997位数,它的每个数位都是2,这个数除以13，商的第100位是几？最后余数是几？【解析】这个数除以13，商是有规律的。 商是170940六个数循环,那么，即，我们从左向右数“170940”的第4个数就是我们找的那个数“9”，所以商的第100位是9。 余数是几呢？ 则解析过程：本题商共有1996位，每6位循环,共有332次循环后余4， 所以商的个位数字应是“170940”中的第4个,商应是9,个位的余数就对应商为9时的余数5。三、练习题1. 求下列算式中的余数。 （1) （2）（3）（4)2. 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，被3除余2，被2除余1,求N的最小值。7、两个数除以11分别余9和10，这两个数的和除以11余几？8、甲、乙、丙三个数之和是100,甲数除以乙数，或丙数除以甲数,得数都商5余1，乙数是多少？9、求下列各式的余数。（1) 26 （2）485（3）求20的200次方 除以13的余数.（4）求80的1000次方 除以12的余数。