15、同余法解題

1、第十五講 同余法解題一、知識要點 在平時解題中，我們經(jīng)常會遇到把著眼點放在余數(shù)上的問題。如：現(xiàn)在時刻是 7 時 30分，再過52小時是幾時幾分？我們知道一天是 24小時，52- 24=24,也就是說 52小時里包含兩個整天再加上 4小時，這樣就在 7時 30分的基礎(chǔ)上加上 4小時，就是 11時 30分。很明顯這個問題的著眼點是放在余數(shù)上了。1、同余的表達(dá)式和特殊符號 :37 和 44同除以 7，余數(shù)都是 2，把除數(shù) 7 稱作“模 7”，37、44對于模7同余。記作：37三44(mod7), “三”讀作同余。一般地，兩個整數(shù) A 和B,除以大于1的自然數(shù)M所得的余數(shù)相同，就稱A、B對于模M同余，

2、記作：A三B(modM)2、同余的性質(zhì)(1) A= A(modM)(每個整數(shù)都與自身同余，稱為同余的反身性。)(2) 若A三B(modM)那么B三A(modM)(這稱作同余的對稱性)(3) 若A三B(modM) B三C(modM)貝U A三C(modM)(這稱為同余的傳遞性)(4) 若A三B(modM) AD(modM)貝U A AB D(modM)(這稱為同余的可加性、可減 性)貝U AX A BX D(modM)(稱為同余的可乘性)(5) 若A= B(modM)則An = Bn (modM)，n為正整數(shù)，同余還有一個非常有趣的現(xiàn)象： 如果A三B(modM)那么M| (A B) (A-B的差

3、一定能被M整除),這是為什么呢？3、同余口訣：“差同減差，和同加和，余同取余，最小公倍加”這是同余問題的口訣。1) 、差同減差：用一個數(shù)除以幾個不同的數(shù)，得到的余數(shù)，與除數(shù)的差相同，此時反 求的這個數(shù)，可以選除數(shù)的最小公倍數(shù)，減去這個相同的差數(shù)，稱為：“差同減差”。 例：“一個數(shù)除以 4余1，除以 5余2，除以 6余3”，因為 4-1=5-2=6-3=3，所以取-3， 表示為 60n-3 。2) 、和同加和：用一個數(shù)除以幾個不同的數(shù)，得到的余數(shù)，與除數(shù)的和相同，此時反 求的這個數(shù)，可以選除數(shù)的最小公倍數(shù)，加上這個相同的和數(shù)，稱為：“和同加和”。 例：“一個數(shù)除以 4余3，除以 5余2，除以 6

4、余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 中的60n)都滿足條件，稱為：“最小公倍加”，也稱為：“公倍數(shù)作周期”。二、精典例題例1:有8只盒子，每只盒子內(nèi)放有同一種筆。8只盒子所裝筆的支數(shù)分別為17、23、33、36、38、42、

5、49、51支。在這些筆中，圓珠筆的支數(shù)是鋼筆的支數(shù)的 2倍，鋼筆的 支數(shù)是鉛筆支數(shù)的-，只有一只盒子里放的是水彩筆。這盒水彩筆共有多少支？3【解析】“鋼筆的支數(shù)是鉛筆支數(shù)的-”可換為“鉛筆的支數(shù)是鋼筆的支數(shù)的 3倍”，那3么圓珠筆、鉛筆、鋼筆的總和一定是6的倍數(shù)，8盒一共有289支，因為289-6= 481,所以水彩筆的支數(shù)除以6 一定余1,故只能是49支。例2、用412、133和257除以一個相同的自然數(shù)，所得的余數(shù)相同，這個自然數(shù)最大 是幾？【解析】假設(shè)這個自然數(shù)是a,因為412、133和257除以a所得的余數(shù)相同，所以a|(412 - 133),a | (412 257),a | (25

6、7 - 133),說明a是以上三個數(shù)中任意兩數(shù)差的約數(shù)， 要求最大是幾，就是求這三個差的最大公約數(shù)。(155,124,279)=31,所以a最大是31。例3、249 X 388X 234除以19,余數(shù)是幾？【解析】如果把三個數(shù)相乘的積求出來再除以 19,就太麻煩了，利用同余思想解決就容 易了。因為 249三2 (mdo19 , 388 三 8 (mdo19 ,234 三6 (mdo19 ,所以 249X 388X 234三2X 8X 6三 1 (mdo19此題應(yīng)用了同余的可乘性，同余的傳遞性。2222*萌 d例4、有一個1997位數(shù)，它的每個數(shù)位都是2,這個數(shù)除以13,商的第100位是幾？最后

7、余數(shù)是幾？2222* 廠 d【解析】 八 這個數(shù)除以13,商是有規(guī)律的。2222raw 13=170940170940商是170940六個數(shù)循環(huán)，那么I1 . - 1-,即川一-.二八F，我們從左向右數(shù)“ 170940的第4個數(shù)就是我們找的那個數(shù)“ 9”，所以商的第100位是9余數(shù)是幾呢？2222凹訪瓦-13 = 170940170940則 I 八所以商的個位數(shù)字應(yīng)是“ 170940中的第4個，商應(yīng)是9,相應(yīng)的余數(shù)是5二、練習(xí)題1.求下列算式中的余數(shù)。1111叫廠#(1)3333V. /(3)-:2222、z /(2) i-.4444、 *(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除余2,被2除余1,求N的