同余法解題(2)

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

2、一個除數(shù)同余 ,那么這個除數(shù)一定就是 519 與 399 的差的因數(shù) ,即 519 與 399 的差一 定能被這個除數(shù)整除。3、對于同一個除數(shù) ,如果兩個數(shù)同余 ,那么她們的乘方仍然同余。例如 20 與 29 對于一個除數(shù)同余 ,那么 20 的任何次方都與 29 的相同次方對于這個除數(shù)同余 ,當(dāng)然余數(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都同余于模 8。5、 對于同一個除數(shù) ,若四個數(shù) a b(

3、mod m),c d(mod那m),么 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ù)最小就是幾？解法 :求 3 個數(shù) :第一個 :能同時被 3 與 4 整除 ,但除以 5 余 4,即 12X224第二個 :能同時被 4 與 5 整除 ,但除以 3 余 1,即 20X240第三個 :能同時被 3 與 5 整除 ,但除以 4 余 2,即 15x230這 3 個數(shù)的最小公倍數(shù)為 60,所以滿足條件

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

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

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

7、三個差的最大公約數(shù)。 (155,124,279)=31,所以 a 最大就是 31。例 3、 249388234 除以 19,余數(shù)就是幾？【解析】如果把三個數(shù)相乘的積求出來再除以 19,就太麻煩了 ,利用同余思想解決就容易了。因為 2492(mdo19), 388 8(mdo19),234 6(mdo19), 所以 2493882342861(mdo19)此題應(yīng)用了同余的可乘性,同余的傳遞性。例 4:求 199259 除以 7 的余數(shù)。思路點撥 :可應(yīng)用性質(zhì) 2,將 199259 轉(zhuǎn)化為求 1992 除以 7 與 59 除以 7 的余數(shù)的乘積 ,使計算簡化。解 :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 的最大值就是多少？思路點撥 :自然數(shù) 16520、 14903、14177 除以 m 的余數(shù)相同 ,也就就是16520 14903 14177(mod m)根據(jù)同余補(bǔ)充定義 ,這三個數(shù)同余 ,那么它們的差就能被 m 整除。要求 m 最大就是多少 ,就就是求它們差的最大公約數(shù)就是多少。解 :因為 16520-14903=161716520-14177=234314903-14

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

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

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

12、商共有 1996 位 ,每 6 位循環(huán) ,共有 332 次循環(huán)后余 4,所以商的個位數(shù)字應(yīng)就是“170940中”的第 4 個,商應(yīng)就是 9,個位的余數(shù)就對應(yīng)商為9 時的余數(shù) 5。三、練習(xí)題1、 求下列算式中的余數(shù)。(1)(2)(3)(4)2、 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,被 8 除余 7,被 7 除余 6,被 6 除余 5,被 5 除余4,被 4 除余 3,被 3 除余