同余法解题0.doc

(完整word)同余法解题(完整word)同余法解题(完整word)同余法解题五年级奥数培训资料第六讲同余法解题一、同余这个概念最初是由德国数学家高斯发明的。同余的定义是这样的：两个整数，a，b，如果他们同时除以一个自然数m,所得的余数相同，则称a，b对于模m同余。。记作a≡b（mod.m）。读作：a同余于b模m。同余的性质也比较多，主要有以下一些：1..对于同一个除数,两个数的乘积与它们余数的乘积同余。例如201×95的乘积对于除数7，与201÷7的余数5和95÷7的余数4的乘积20对于7同余。2..对于同一个除数，如果有两个整数同余，那么它们的差就一定能被这个除数整除。例如519和399对于一个除数同余,那么这个除数一定是519与399的差的因数,即519与399的差一定能被这个除数整除。3.。对于同一个除数，如果两个数同余，那么他们的乘方仍然同余。例如20和29对于一个除数同余，那么20的任何次方都和29的相同次方对于这个除数同余,当然余数大小随次方变化。4．对于同一个除数，若三个数a≡b（modm），b≡c（modm），那么a，b,c三个数对于除数m都同余（传递性)例如60和76同余于模8，76和204同余于模8,那么60,76,204都同余于模8.5。对于同一个除数，若四个数a≡b（modm),c≡d（modm)，那么a±c≡c±d（modm)，（可加减性）6。对于同一个除数，若四个数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＝4015x2＝30中2的来历.三、解题技巧同余口诀：“差同减差，和同加和，余同取余，最小公倍n倍加”这是同余问题的口诀。1）、差同减差：用一个数除以几个不同的数,得到的余数，与除数的差相同,此时反求的这个数，可以选除数的最小公倍数,减去这个相同的差数，称为：“差同减差”。例:“一个数除以4余1,除以5余2，除以6余3"，因为4-1=5-2=6—3=3,所以取—3，表示为60—3或者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是否同余思路点拨：可直接由定义判断.解：∵288—214=74=37×2∴288≡214(mod37）例2、用412、133和257除以一个相同的自然数,所得的余数相同，这个自然数最大是几？【解析】假设这个自然数是a,因为412、133和257除以a所得的余数相同，所以a｜(412－133），a｜(412－257）,a｜(257－133)，说明a是以上三个数中任意两数差的约数，要求最大是几，就是求这三个差的最大公约数。（155,124,279）=31，所以a最大是31。例3、249×388×234除以19,余数是几？【解析】如果把三个数相乘的积求出来再除以19,就太麻烦了,利用同余思想解决就容易了。因为249≡2（mdo19）,388≡8（mdo19)，234≡6（mdo19),所以249×388×234≡2×8×6≡1（mdo19）此题应用了同余的可乘性，同余的传递性。例4：求1992×59除以7的余数。思路点拨：可应用性质2,将1992×59转化为求1992除以7和59除以7的余数的乘积,使计算简化。解:∵1992≡4（mod7），59≡3（mod7）∴根据性质5可得：1992×59≡4×3（mod7)，余数为12÷7的余数。答：1992×59除以7的余数是5.例5:自然数16520、14903、14177除以m的余数相同，m的最大值是多少？思路点拨：自然数16520、14903、14177除以m的余数相同,也就是16