同余法解 题课件.doc

五年级奥数培训资料 第六讲 同余法解题 ??? 一、 同余这个概念最初就是由德国数学家高斯发明得。同余得定义就是这样得: ?两个整数,a,b,如果她们同时除以一个自然数ｍ,所得得余数相同,则称ａ,b对于模m同余。。记作a≡b(moｄ.ｍ)、读作:a同余于ｂ模ｍ。 ?同余得性质也比较多,主要有以下一些: 1、.对于同一个除数,两个数得乘积与它们余数得乘积同余。 例如20１?×９5得乘积对于除数7,与2０1÷７得余数5与95÷７得余数４得乘积20对于7同余。 2.、对于同一个除数,如果有两个整数同余,那么它们得差就一?定能被这个除数整除。? 例如51９与３99对于一个除数同余,那么这个除数一定就是519与3９9得差得因数,即５19与399得差一? 定能被这个除数整除。? ３..对于同一个除数,如果两个数同余,那么她们得乘方仍然同余。 例如２0与29对于一个除数同余,那么2０得任何次方都与２9得相同次方对于这个除数同余,当然余数大小随次方变化。 ??4、对于同一个除数,若三个数a≡b(moｄ　m),ｂ≡c(moｄ m),那么a,b,ｃ三个数对于除数m都同余 (传递性) 例如６０与7６同余于模８,76与204同余于模８,那么60,76,204都同余于模８、 5。 对于同一个除数,　　若四个数ａ≡ｂ(mｏd　ｍ),ｃ≡d(mｏd m),那么a±ｃ≡c±d(mod m),(可加减性) 6。 　对于同一个除数, 若四个数a≡b(mod　m),c≡ｄ(mod　ｍ),那么ac≡cｄ(mｏd　m),(可乘性) 二、中国剩余定理解法 一个数被3除余1,被4除余2,被5除余4,这个数最小就是几?解法:?求３个数:第一个:能同时被3与4整除,但除以5余4,即１2X2=2４?第二个:能同时被４与5整除,但除以３余1,即20X2＝40第三个:能同时被3与5整除,但除以4余2,即15x2＝30?这3个数得最小公倍数为6０,所以满足条件得最小数字为24+４0+30-60=３4 12X2=24 20Ｘ2＝４０ 15x2＝30中2得来历。 三、解题技巧 同余口诀:“差同减差,与同加与,余同取余,最小公倍n倍加”这就是同余问题得口诀。 １)、差同减差:用一个数除以几个不同得数,得到得余数,与除数得差相同,此时反求得这个数,可以选除数得最小公倍数,减去这个相同得差数,称为:“差同减差”。例:“一个数除以４余1,除以5余2,除以６余3”,因为4—1＝5—2=６-3=3,所以取—3,表示为60—3或者60n－3 2)、与同加与:用一个数除以几个不同得数,得到得余数,与除数得与相同,此时反求得这个数,可以选除数得最小公倍数,加上这个相同得与数,称为:“与同加与。例:“一个数除以４余３,除以5余2,除以6余1”,因为4＋3=５＋2=6＋1＝7,所以取+7,表示为60n+７、 3)、余同取余:用一个数除以几个不同得数,得到得余数相同,此时反求得这个数,可以选除数得最小公倍数,加上这个相同得余数,称为:“余同取余”。例:“一个数除以4余1,除以5余1,除以6余1,因为余数都就是1,所以取＋1,表示为６０n＋1。 4)、最小公倍加:所选取得数加上除数得最小公倍数得任意整数倍(即上面1、2、３中得60n)都满足条件,称为:“最小公倍ｎ倍加”,也称为:“公倍数作周期”。　 三、例题解评 例1:判定288与214对于模37就是否同余 思路点拨:可直接由定义判断。 解:∵28８－214=7４=３7×２ ∴2８8≡2１4(ｍｏｄ 3７) 例2、 用４１2、13３与２５7除以一个相同得自然数,所得得余数相同,这个自然数最大就是几？ 【解析】假设这个自然数就是a,因为412、13３与25７除以a所得得余数相同,所以ａ｜(412－1３３),a｜(412－257),a|(257－１33),说明ａ就是以上三个数中任意两数差得约数,要求最大就是几,就就是求这三个差得最大公约数。(155,124,279)=3１,所以a最大就是３1。 例3、 2４9×388×234除以１9,余数就是几? 【解析】如果把三个数相乘得积求出来再除以19,就太麻烦了,利用同余思想解决就容易了。 因为249≡2(ｍｄo19), 388≡８(ｍdo1９),２3４≡6(mｄo１9), 所以２49×３８8×234≡2×８×６≡1(mdo19) 此题应用了同余得可乘性,同余得传递性、 例4:求１9９2×5９除以7得余数。 思路点拨:可应用性质2,将19９２×59转化为求１99２除以７与5９除以７得余数得乘积,使计算简化。 解:∵1992≡４(mｏd 7),5９≡3(mod 7) ∴根据性质5可得:1992×59≡４×3(mod ７),余数为12÷7得余数、 答:19９2×59除以7得余数就是5。 例5:自然数