同余法解題(2)

1、五年級(jí)奧數(shù)培訓(xùn)資料第六講同余法解題一、 同余這個(gè)概念最初就是由德國(guó)數(shù)學(xué)家高斯發(fā)明的。同余的定義就是這樣的 : 兩個(gè)整數(shù) ,a,b,如果她們同時(shí)除以一個(gè)自然數(shù) m,所得的余數(shù)相同 ,則稱 a,b 對(duì)于模 m 同余。記作 a b(mod、m)。讀作 :a 同余于 b 模 m。 同余的性質(zhì)也比較多 ,主要有以下一些 :1、對(duì)于同一個(gè)除數(shù) ,兩個(gè)數(shù)的乘積與它們余數(shù)的乘積同余。例如 201 95 的乘積對(duì)于除數(shù) 7,與 2017 的余數(shù) 5 與 957 的余數(shù) 4 的乘積 20 對(duì)于 7 同余。2、對(duì)于同一個(gè)除數(shù) ,如果有兩個(gè)整數(shù)同余 ,那么它們的差就一定能被這個(gè)除數(shù)整除。例如 519 與 399 對(duì)于

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

3、mod m),c d(mod那m),么 a c c d(mod 可m),(加減性 )6、對(duì)于同一個(gè)除數(shù) , 若四個(gè)數(shù) a b(mod m),c d(mod那m),么 ac cd(mod m),(可乘性 )二、中國(guó)剩余定理解法一個(gè)數(shù)被 3 除余 1,被 4 除余 2,被 5 除余 4,這個(gè)數(shù)最小就是幾？解法 :求 3 個(gè)數(shù) :第一個(gè) :能同時(shí)被 3 與 4 整除 ,但除以 5 余 4,即 12X224第二個(gè) :能同時(shí)被 4 與 5 整除 ,但除以 3 余 1,即 20X240第三個(gè) :能同時(shí)被 3 與 5 整除 ,但除以 4 余 2,即 15x230這 3 個(gè)數(shù)的最小公倍數(shù)為 60,所以滿足條件

4、的最小數(shù)字為 2440+30-60=3412X22420X24015x230 中 2 的來歷。三、解題技巧同余口訣 : “差同減差 ,與同加與 ,余同取余 ,最小公倍 n 倍加 ”這就是同余問題的口訣。1)、差同減差 :用一個(gè)數(shù)除以幾個(gè)不同的數(shù),得到的余數(shù) ,與除數(shù)的差相同 ,此時(shí)反求的這個(gè)數(shù) ,可以選除數(shù)的最小公倍數(shù) ,減去這個(gè)相同的差數(shù) ,稱為 : “差同減差 ”。例 : “一個(gè)數(shù)除以 4余 1,除以 5 余 2,除以 6 余 3”,因?yàn)?4-1=5-2=6-3=3,所以取 -3,表示為 60-3 或者 60n-32)、與同加與 :用一個(gè)數(shù)除以幾個(gè)不同的數(shù) ,得到的余數(shù) ,與除數(shù)的與相同

5、,此時(shí)反求的這個(gè)數(shù) ,可以選除數(shù)的最小公倍數(shù) ,加上這個(gè)相同的與數(shù) ,稱為 : “與同加與 ”。例 : “一個(gè)數(shù)除以 4余 3,除以 5 余 2,除以 6 余 1”,因?yàn)?4+3=5+2=6+1=7,所以取 +7,表示為 60n+7。3)、余同取余 :用一個(gè)數(shù)除以幾個(gè)不同的數(shù),得到的余數(shù)相同 ,此時(shí)反求的這個(gè)數(shù) ,可以選除數(shù)的最小公倍數(shù) ,加上這個(gè)相同的余數(shù) ,稱為 : “余同取余 ”。例 : “一個(gè)數(shù)除以 4 余 1,除以 5 余 1,除以 6 余 1”,因?yàn)橛鄶?shù)都就是 1,所以取 +1,表示為 60n+1。4)、最小公倍加 :所選取的數(shù)加上除數(shù)的最小公倍數(shù)的任意整數(shù)倍(即上面 1、2、3

6、中的60n)都滿足條件 ,稱為 : “最小公倍 n 倍加 ”,也稱為 : “公倍數(shù)作周期 ”。三、例題解評(píng)例 1:判定 288 與 214 對(duì)于模 37 就是否同余思路點(diǎn)撥 :可直接由定義判斷。解 :288-214=74=372 288214(mod 37)例 2、 用 412、133 與 257 除以一個(gè)相同的自然數(shù) ,所得的余數(shù)相同 ,這個(gè)自然數(shù)最大就是幾？【解析】假設(shè)這個(gè)自然數(shù)就是 a,因?yàn)?412、133 與 257 除以 a 所得的余數(shù)相同 ,所以 a(412 133),a(412257),a(257133),說明 a 就是以上三個(gè)數(shù)中任意兩數(shù)差的約數(shù) ,要求最大就是幾 ,就就是求這

7、三個(gè)差的最大公約數(shù)。 (155,124,279)=31,所以 a 最大就是 31。例 3、 249388234 除以 19,余數(shù)就是幾？【解析】如果把三個(gè)數(shù)相乘的積求出來再除以 19,就太麻煩了 ,利用同余思想解決就容易了。因?yàn)?2492(mdo19), 388 8(mdo19),234 6(mdo19), 所以 2493882342861(mdo19)此題應(yīng)用了同余的可乘性,同余的傳遞性。例 4:求 199259 除以 7 的余數(shù)。思路點(diǎn)撥 :可應(yīng)用性質(zhì) 2,將 199259 轉(zhuǎn)化為求 1992 除以 7 與 59 除以 7 的余數(shù)的乘積 ,使計(jì)算簡(jiǎn)化。解 :19924(mod 7),59

8、3(mod 7)根據(jù)性質(zhì) 5 可得 :1992 5943(mod,余7)數(shù)為 127 的余數(shù)。答 :1992 59 除以 7 的余數(shù)就是 5。例 5:自然數(shù) 16520、 14903、14177 除以 m 的余數(shù)相同 ,m 的最大值就是多少？思路點(diǎn)撥 :自然數(shù) 16520、 14903、14177 除以 m 的余數(shù)相同 ,也就就是16520 14903 14177(mod m)根據(jù)同余補(bǔ)充定義 ,這三個(gè)數(shù)同余 ,那么它們的差就能被 m 整除。要求 m 最大就是多少 ,就就是求它們差的最大公約數(shù)就是多少。解 :因?yàn)?16520-14903=161716520-14177=234314903-14

9、177=726(1617、 2343、 726)=33所以 m 的最大值就是33。評(píng)注實(shí)際上 ,這三個(gè)差數(shù)還可以繼續(xù)兩兩相減 ,得到 1617-726=891,891-726=165,算出 726 與 165 的最大公約數(shù)即可 ,通常其結(jié)果與上面相同。例 6:在除 13511,13903,及 14598 時(shí)能剩下相同余數(shù)的最大整數(shù)就是幾？思路點(diǎn)撥 :根據(jù)同余的性質(zhì) ,若幾個(gè)數(shù)被同一個(gè)數(shù)除 ,余數(shù)相同 ,則這幾個(gè)數(shù)中兩兩相減的差必能被這個(gè)數(shù)整除。所以這個(gè)數(shù)應(yīng)就是這三個(gè)數(shù)兩兩相減后所得數(shù)的最大公約數(shù)。解 :這兩個(gè)數(shù)兩兩只減的差就是 : 13903-13511=392 14598-13903=686

10、14589-13511=1078因?yàn)?(392,686,1078)=98,所以這個(gè)數(shù)就是98。也可以以上三個(gè)差再兩兩相減 ,得 686-392=294,再 392-294=98 答 :這個(gè)最大整數(shù)就是 98。例 7:一個(gè)三位數(shù)除以 9 余 7,除以 5 余 2,除以 4 余 3。這樣的三位數(shù)共有幾個(gè)？思路點(diǎn)撥 :由中國(guó)剩余定理解法求。解法 :求 3 個(gè)數(shù) :第一個(gè) :能同時(shí)被 9 與 5 整除 ,但除以 4 余 3,即 45X3135第二個(gè) :能同時(shí)被 4 與 5 整除 ,但除以 9 余 7,即 20X8160第三個(gè) :能同時(shí)被 9 與 4 整除 ,但除以 5 余 2,即 36x272這 3

11、個(gè)數(shù)的最小公倍數(shù)為 180,所以滿足條件的最小數(shù)字為 135 160+72-180=18771805=907 100071806=10871000所以符合條件的三位數(shù)共有 5 個(gè)。分別就是 7180n(n=1,2,4,5)、答 :這樣的三位數(shù)共有 5 個(gè)。例 8、 有一個(gè) 1997 位數(shù) ,它的每個(gè)數(shù)位都就是2,這個(gè)數(shù)除以13,商的第 100位就是幾？最后余數(shù)就是幾？【解析】這個(gè)數(shù)除以 13,商就是有規(guī)律的。商就是 170940 六個(gè)數(shù)循環(huán) ,那么,即,我們從左向右數(shù)“ 170940的”第 4 個(gè)數(shù)就就是我們找的那個(gè)數(shù) “ 9”,所以商的第 100 位就是 9。余數(shù)就是幾呢？則解析過程 :本題

12、商共有 1996 位 ,每 6 位循環(huán) ,共有 332 次循環(huán)后余 4,所以商的個(gè)位數(shù)字應(yīng)就是“170940中”的第 4 個(gè),商應(yīng)就是 9,個(gè)位的余數(shù)就對(duì)應(yīng)商為9 時(shí)的余數(shù) 5。三、練習(xí)題1、 求下列算式中的余數(shù)。(1)(2)(3)(4)2、 6254 與 37 的積除以 7,余數(shù)就是幾？3、 如果某數(shù)除 482,992,1094都余 74,這個(gè)數(shù)就是幾？4、300、262、 205 被同一個(gè)整數(shù)除 ,得到相同的余數(shù) ,這個(gè)整數(shù)就是幾？5、一個(gè)自然數(shù)被 247 除余 63,被 248 除余 63,求這個(gè)自然數(shù)被26 除的余數(shù)。6、一個(gè)自然數(shù) N 被 10 除余 9,被 9 除余 8,被 8 除余 7,被 7 除余 6,被 6 除余 5,被 5 除余4,被 4 除余 3,被 3 除余