同余法解題之歐陽學創(chuàng)編

1、五年級奧數(shù)培訓資料時間:2021.03. 03創(chuàng)作：歐陽學第六講同余法解題一、同余這個概念最初是由德國數(shù)學家高斯發(fā)明的。同余 的定義是這樣的：兩個整數(shù)，a,b,如果他們同時除以一個 自然數(shù) m, 所得的余數(shù)相同，則稱a,b對于模 m 同余。記作a三b (mod.m) o 讀作：a同余于b模 m。同余的性質(zhì)也比較多，主要有以下一些：1. 對于同一個除數(shù)，兩個數(shù)的乘積與它們余數(shù)的乘積同 余。例如 201 x95的乘積對于除數(shù)7,與 2014-7的余數(shù)5和957的余數(shù)4的乘積20對于7同余。2. 對于同一個除數(shù)，如果有兩個整數(shù)同余，那么它們的差 就一定能被這個除數(shù)整除。例如519和399對于一個除數(shù)

2、同余，那么這個除數(shù)一定是 519與399的差的因數(shù)，即519與399的差一 定能披這個 除數(shù)整除。3. 對于同一個除數(shù)，如果兩個數(shù)同余，那么他們的乘方仍 然同余。例如日20和 29對于一個除數(shù)同余，那么20的任何次方都和 29 的相同次方對于這個除數(shù)同余，當然余數(shù)大小隨次 方變化。4. 對于同一個除數(shù)，若三個數(shù) a=b (mod m) , b三c (mod m), 那么a,b,c三個數(shù)對于除數(shù) m 都同余 (傳遞 性)例如 60和 76同余于模 8, 76和 204同余于模 8, 那么60,76,204都同余于模8O5. 對于同一個除數(shù)，若四個數(shù) a三b (mod m) , c三d(mod m

3、),那么 a土c三c±d (mod m),(可加減性)6. 對于同一個除數(shù)， 若四個數(shù) a三b (mod m) , c三d(mod m),那么 ac三cd (mod m),(可乘性)二、中國剩余定理解法一個數(shù)披3除余1, 披4除余2,披5除余4, 這個數(shù)最小是幾9解法求3個數(shù)：第一個：能同時被3和4整除，但除以5余4,即12X2=24笫二個：能同時被4和5整除，但除以3余1,即20X2 =40笫三個：能同時被3和5整除，但除以4余2,即15x2 =30這 3 個數(shù)的最小公倍數(shù)為 60,所以滿足條件的最小數(shù)字為24 + 40+3060=3412X2 = 2420X2 = 4015x2

4、= 30 中 2 的來歷。三、解題技巧同余口訣："差同減差，和同加和，余同取余，最小公倍 n 倍加”這是同余問題的口 訣。1）、差同減差：用一個數(shù)除以幾個不同的數(shù)，得到的余 數(shù)，與除數(shù)的差相同，此時反求的這個數(shù)，可以選除數(shù)的 最小公倍數(shù)，減去這個相同的差數(shù)，稱為：“差同減差二 例：“一個數(shù)除以4余1,除以5余2,除以6余3",因為 41=52=63=3,所以取3,表示為603或者60n32）、和同加和：用一個數(shù)除以幾個不同的數(shù)，得到的余 數(shù)，與除數(shù)的和相同，此時反求的這個數(shù)，可以選除數(shù)的 最小公倍數(shù)，加上這個相同的和數(shù)，稱為：“和同加和二 例：“一個數(shù)除以4余3,除以5余2

5、,除以6余 T',因為 4+3=5+2=64-1 =7,所以取+7,表示為 60n+7o3）、余同取余：用一個數(shù)除以幾個不同的數(shù)，得到的余 數(shù)相同，此時反求的這個數(shù)，可以選除數(shù)的最小公倍數(shù)， 加上這個相同的余數(shù)，稱為：“余同取余例：“一個數(shù) 除以4余1,除以5余1,除以6余1",因為余數(shù)都是1, 所以取+1,表示為60n+lo4）、最小公倍加：所選取的數(shù)加上除數(shù)的最小公倍數(shù)的 任意整數(shù)倍（即上面1、2、3中的 60n）都滿足條件，稱 為：“最小公倍n倍加： 也稱為：“公倍數(shù)作周期二三、例題解評例1 :判定288和214對于模37是否同余思路點撥：可直接由定義判斷。解：7288

6、214=74=37x2.*.288=214 (mod 37)例2、用412、133和257除以一個相同的自然數(shù)，所傅 的余數(shù)相同，這個自然數(shù)最大是幾？【解析】 假設這個自 然數(shù)是a,因為412、133和257除以 a 所傅的余數(shù)相同，所以 a | (412 - 133),a | (412-257),a | (257- 133),說明a是以上三個數(shù)中任意兩數(shù)差的約數(shù)，要 求最大是幾，就是求這三個差的最大公約數(shù)。 (155,124,279)=31，所以 a 最大是 31。例3、249x388x234除以19,余數(shù)是幾？【解析】如果把三個數(shù)相乘的積求出來再除以19, 就太麻 煩了，利用同余思想解決就

7、容易了。因為 249三2 (mdo!9) , 388=8 (mdol9) ,234三6 (mdol9), 所以 249x388x234三2乂8乂6三1 (mdol9)此題應用了同余的可乘性，同余的傳遞性。例4:求1992x59除以7的余數(shù)。思路點撥：可應用性質(zhì)2,將1992x59轉(zhuǎn)化為求1992除以 7和59除以7的余數(shù)的乘積，使計算簡化。解：V 1992=4 (mod 7) , 59三3 (mod 7)根據(jù)性質(zhì)5可得：1992x59三4x3 (mod 7 ),余數(shù)為 12三7的余數(shù)。答：1992x59除以7的余數(shù)是5。例5:自然數(shù)16520、14903、14177除以m的余數(shù)相同，m的最大值

8、是多少？思路點撥：自然數(shù)16520、14903、14177除以m的余數(shù)相 同，也就是16520三 14903三 14177 (modm)根據(jù)同余補充定義，這三個數(shù)同余，那么它們的差就能被 m 整除。要求 m 最大是多少，就是求它們差的最大公約數(shù) 是多少。解：因為 1652014903=16171652014177=23431490314177=726(1617、 2343、 726) =33所以m的最大值是33。丄評注D實際上，這三個差數(shù)還可以繼續(xù)兩兩相減，得到 1617726=891,891726=165,算出 726 和 165 的最大公約數(shù) 即可，通常其結(jié)果與上面相同。例6:在除1351

9、1, 13903,及14598時能剩下相同余數(shù)的 最大整數(shù)是幾？思路點撥：根據(jù)同余的性質(zhì)，若幾個數(shù)披同一個數(shù)除，余 數(shù)相同，則這幾個數(shù)中兩兩相減的差必矣邑披這個數(shù)整除。 所以這個數(shù)應是這三個數(shù)兩兩相減后所得數(shù)的最大公約 數(shù)。解：這兩個數(shù)兩兩只減的差是：1390313511=3921459813903=6861458913511=1078因為(392, 686, 1078) =98,所以這個數(shù)是98。也可以以上三個差再兩兩相減，得 686392=294, 再392294=98答：這個最大整數(shù)是98。例7: 個三位數(shù)除以9余7,除以5余2,除以4余3。這樣的三位數(shù)共有幾個？思路點撥：由中國剩余定理

10、解法求。解法:求 3個數(shù)：第一個：能同時被 9和 5 整除，但除以 4 余 3,即45X3=135笫二個：能同時披4和5整除，但除以9余7,即20X8 = 160笫三個：能同時被9和4整除，但除以5余2,即36x2 =這 3 個數(shù)的最小公倍數(shù)為 180,所以滿足條件的最小數(shù)字為135 + 160+72180=1877 + 180x5=907 < 10007+ 180x6=1087 >1000所以符合條件的三位數(shù)共有 5 個。分別是 7 + 180xn(n=l,2,4,5) 答：這樣的三位數(shù)共有5個。2222'V'例8、有一個1997位數(shù)，它的每個數(shù)位都是2,1997

11、個2這個數(shù)除以13, 商的弟100位是幾？最后余數(shù)是幾？2222'V'【解析】1997個2 這個數(shù)除以13,商是有規(guī)律的。商是 170940 六個數(shù)循環(huán)，那么10X6=164, 即100三。血加6),我們從左向右數(shù)“ 170940"的笫4個數(shù)就是我們找的那個數(shù)“9",所以商的第100位是9。余數(shù)是幾呢？貝 jj 1996 = 4(mod6)解析過程：本題商共有1996位，每6位循環(huán)，共有332次循環(huán)后余4,所以商的個位數(shù)字應是“170940”中的第 4 個，商應是 9,個位的余數(shù)就對應商為9時的余數(shù)5O三、練習題1.求下列算式中的余數(shù)。(1 ) 1997個 1 +73333'V'(3)1997個 3 十 132222'V'(2) 1997個 2 J4444(4)1997個 4十132. 6254與37的積除以7,余數(shù)是幾？3如果某數(shù)除482, 992, 1094都余74,這個數(shù)是幾？ 4、300、262、205被同一個整數(shù)除，得到相同的余數(shù)，這個整數(shù)是幾?5、一個自 然數(shù)被247除余63,被248除余63,求這個自 然數(shù)被26除的余數(shù)。6、一個自然數(shù)N披10除余9,披9除余& 被8除余7, 披7除余6,披6除余5,被5除余4,披4除余3,披3 除