15、同余法解題

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

2、記作：A三B(modM)2、同余的性質(zhì)(1) A= A(modM)(每個(gè)整數(shù)都與自身同余，稱為同余的反身性。)(2) 若A三B(modM)那么B三A(modM)(這稱作同余的對(duì)稱性)(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ù)，同余還有一個(gè)非常有趣的現(xiàn)象： 如果A三B(modM)那么M| (A B) (A-B的差

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

4、余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 中的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支，因?yàn)?89-6= 481,所以水彩筆的支數(shù)除以6 一定余1,故只能是49支。例2、用412、133和257除以一個(gè)相同的自然數(shù)，所得的余數(shù)相同，這個(gè)自然數(shù)最大 是幾？【解析】假設(shè)這個(gè)自然數(shù)是a,因?yàn)?12、133和257除以a所得的余數(shù)相同，所以a|(412 - 133),a | (412 257),a | (25

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

7、余數(shù)是幾？2222* 廠 d【解析】 八 這個(gè)數(shù)除以13,商是有規(guī)律的。2222raw 13=170940170940商是170940六個(gè)數(shù)循環(huán)，那么I1 . - 1-,即川一-.二八F，我們從左向右數(shù)“ 170940的第4個(gè)數(shù)就是我們找的那個(gè)數(shù)“ 9”，所以商的第100位是9余數(shù)是幾呢？2222凹訪瓦-13 = 170940170940則 I 八所以商的個(gè)位數(shù)字應(yīng)是“ 170940中的第4個(gè)，商應(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,這個(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除余2,被2除余1,求N的