應(yīng)用同余解題

1、笫八講應(yīng)用同余解題笫八講應(yīng)用同余解題在五年級(jí)我們己初步學(xué)習(xí)了同余的有關(guān)知識(shí).同余在解答競(jìng)賽題中有著廣泛的應(yīng)用.在這一講中，我們將深入理解同余的概念和性質(zhì)，悟?qū)缢囊恍┻\(yùn) 用技巧和方法.例 1 躲以 5 余 1,滁以 5 余 4,如果 3ab,那么 33-瞬以 5 余幾？分析與余數(shù)有關(guān)的問(wèn)題考慮用同余式可以使解題簡(jiǎn)便.解 2 .* a 1 (mod5),3a=3 (mod 5),或者 3a=8 (mod 5)(1)又 T b=4 (mod 5),(2)(1) -(2)得：3a b84=4 (mod 5).因此，3a-瞞以 5 余 4例例 2 若 a 為自然數(shù)，證明 10|(H-沖).分析 如果換

2、一種方式表達(dá)，所要證明的即是要證 a 欣與 a 歸個(gè)位數(shù)字相 同.用對(duì)于模 10 兩數(shù)同余來(lái)解，可以使解題過(guò)程簡(jiǎn)化.證明：Ta 加=尹侏一】三 a (modlO),a； (mod 10), a*?;- = aa0 (mod 10)即0 | (al3S5a1949)說(shuō)明：這里用到一個(gè)事實(shí)：對(duì)于任何自然數(shù) a,孑與 a 的個(gè)位數(shù)字相同.例例 3 計(jì)算機(jī)錄入員平均每分鐘可以輸入 72 個(gè)漢字，輸入一篇有而務(wù) 個(gè)汶字的文章所用的分鐘數(shù)恰好是整數(shù)，求五位數(shù)而莎.分析這道題實(shí)質(zhì)是求一個(gè)能被 72 整除的五位數(shù)而莎解：解：.72=8X9,又 72|而莎由能被 8、9 整除的特征，得Jx+ 6 + 7 + 9

3、 + y0 (mod 9) (1)|700+ 90 + y=0 (mod 8).(2)由(2)得 y=2 (mod 8)因 0yv9且、是整數(shù)*.y= 2 扌巴 y=2代入(1)得x+ 6+ 7 + 9 + 2=0 (mod 9)x=3 (mod 9)由 x 是一位整數(shù)得：x=3.所求五位數(shù)是 36792.例例4n=19191919-1919,求 n 被 9 除后所得商的個(gè)位數(shù)是幾？ 1919個(gè)1919分析 設(shè) 曠 9=商=,那么 9 | (nr),根據(jù) 11-廠=商乂 9,以及 n-r 的個(gè)位數(shù)字，可推算岀商的個(gè)位數(shù)字.抓住一個(gè)整數(shù)與它的各位數(shù)字之和對(duì)于模 9同余這性質(zhì)，可以很快 的化大數(shù)為

4、小數(shù).解解：丁H=19191919 1919M1919X (1+9 + 1 + 9)=1919X20=2X2 三-一1919個(gè)19194 (mod 9),.* 9 | (n4),即 n - 4=9X 商,又的個(gè)位數(shù)字是 5,J 被滁所得的商的個(gè)位數(shù)字是 5 例例 5 設(shè) 2n+l 是質(zhì)數(shù),證明：2, 2,小被 2n+l 除所得的余數(shù)各不相 同.分析分析 這道題肯定不可能通過(guò)各數(shù)被 2n+l 除去求余數(shù).那么我們可以考慮 從反面入手，假設(shè)存在兩個(gè)相同的余數(shù)的話，就會(huì)發(fā)生矛盾.而中間的推導(dǎo)是 步步有根據(jù)的，所以發(fā)生矛盾的原因是假設(shè)不合理.從而說(shuō)明假設(shè)不成立，因 此原來(lái)的結(jié)論是正確的.證明：假設(shè)有兩

5、個(gè)數(shù) a、b, (ab,設(shè) ba,且 lan, lb19即 1919 個(gè)1919 ”有 3838 個(gè)“19 ”，三組三組取走19 ”后還剩下一組. a= 19(mod 13).a=6 (mod 13)即躲以 13 余數(shù)是 6.例例 7 求被 3 除余 2,被 5除余 3,被 7 除余 5 的最小三位數(shù).解：設(shè) x 為所求數(shù)，由題意x=2 (mod 3),(1)x=3 (mod 5),(2)x=5 (mod 7),(3)(3)即 x=7k+5 (k整數(shù))代入(2)得 k+ 5=3 (mod 5),2k=3 (mod 5),2k8 (mod 5).k=4 (mod 5),即 k= 5m + 4 是

6、整數(shù)) .x=7k+5 = 7(5m+4)+5 =35m+33, 上式代入(1)得：35m+ 33=2 (mod 3),1.*.m= 1 (mod 3),即 m =3t+l (堤整數(shù))./.x=35m+33 = 35(3t+ 1) +33= 105t+68,當(dāng) t=l時(shí)，x=173.所求的最小三位數(shù)為 173.例 8 給岀 12 個(gè)彼此不同的兩位數(shù)， 證明： 由它們中一定可以選岀兩個(gè)數(shù)，它們的差是兩個(gè)相同數(shù)字組成的兩位數(shù).分析證這道題要考慮到以下三點(diǎn).1兩位數(shù)的數(shù)碼相同時(shí)，它一定能被 11 整除.2遇到數(shù)是任意的，需排個(gè)序，這樣討論表述起來(lái)比較方便.3用12個(gè)數(shù)中最大的數(shù)依次地分別減去其余11

7、個(gè)數(shù)可得到11個(gè)差.若差中有相同數(shù)碼組成的兩位數(shù)，問(wèn)題得證；若差中沒(méi)有合條件的兩位數(shù)，這時(shí)這 11 個(gè)(差)數(shù)各自除以 11,所得余數(shù)只可能在1, 2, 3,10中，必有兩個(gè)差數(shù)的余數(shù)相同，考慮用余數(shù)造抽屜解題.證明：設(shè) 12 個(gè)兩位數(shù)從小到大排列為：10ala2allal299,用 al2 分別減去其余的數(shù)，得差：bl = al2- al, b2 = al2 a2,，bll = al2 all.1若上面 11 個(gè)差中有某個(gè)差 b】能被 11 整除，即 111 (al2-ai),那么己證 岀數(shù) al2 與 ai的差 bi 是兩個(gè)相同數(shù)碼組成的兩位數(shù).2若這 11 個(gè)差均不能被 11 整除，則按

8、不能被 11 整除的余數(shù)造 10 個(gè)抽屜，余 數(shù)相同者歸入同一抽屜， 根據(jù)抽屜原理， 11 個(gè)差數(shù)中， 一定存在兩數(shù) bm、 bnM于模 11 同余，即：bm-bn=0 (mod 11),即(al2 am) 一 (al2 an) 0 (mod 11),即 an-am=0 (mod 11),即 11 | (an 一 am),印差 an-am 是一個(gè)由相同數(shù)碼組成的兩位數(shù).綜合（1）、（2）問(wèn)題得 證.說(shuō)明：這道題的證明用到了將數(shù)按被 11 除的余數(shù)分類(lèi)的思想.一般地，任何一個(gè)整數(shù) a 被自然數(shù)滁，余數(shù)只可能是 0, 1, 2,，n-1 這 諦情況，這樣我們可以利用余數(shù)將整數(shù)分為幾類(lèi)，如：整數(shù)按除

9、以 2 余 1 還是 0,分為奇數(shù)和偶數(shù).又如，整數(shù)除以 3,余數(shù)只能是 0,1, 2這三種情況，我們可以把所有整數(shù) 按除以 3 后的殺藪分三類(lèi)，即 3k, 3k+l, 3k+2, （k：整藪）.這種利用余數(shù)分類(lèi)思想，是重要的數(shù)學(xué)思想方法，它可以使研究問(wèn)題時(shí)搜 索的范圍大大縮小.例 9 試證不小于 5 的質(zhì)數(shù)的平方與 1的差必能被 24 整除.證明：質(zhì)數(shù)中僅有一個(gè)偶數(shù) 2,不小于 5 的質(zhì)數(shù)是奇數(shù).戈不小于 5 的自然數(shù)按除以 6 所得的余數(shù)可分為 6 類(lèi)：6n, 6n+l, 6n+2, 6n + 3,6n+4, 6n+5, （n 是自然數(shù)），其中 6n, 6n+ 2, 6n+4 都是偶數(shù)，又

10、 3 I 6n + 3.不小于 5 的質(zhì)數(shù)只可能是 6n+ 1, 6n + 5.又自然數(shù)除以 6 余數(shù)是 5 的這類(lèi)數(shù)換一記法是：6n-l,（不小于 5 的質(zhì)數(shù)）2-1=（6n 1）2-1=36n: 12n= 12n（3n 1）,這里 n 與（3nl）奇偶性不同，其中定有一個(gè)偶數(shù),/.2 | n(3n 1),/. 24 | 12n(3n 1).結(jié)論成立.說(shuō)明：按同余類(lèi)造抽屜是解競(jìng)賽題的常用方法.例 10 任給七個(gè)不同的整數(shù)，證明其中必有兩個(gè)數(shù)，其和或差是 10 的倍數(shù).分析首先考慮什么樣的兩個(gè)整數(shù)的和或差可以被 10 整除.設(shè)兩個(gè)整數(shù) a、 b,若 a=b (mod 10),則 10 | (a-b)；若 ar (mod 10),而 b10r (mod 10),則 10 | (a+b),只有這兩種情況但是如杲按整數(shù)除以 10 的余 數(shù)造抽屜，就有十個(gè)抽屜，對(duì)于己知條件中給定的七個(gè)數(shù)無(wú)法應(yīng)用抽屜原理， 所以要考慮如何造六個(gè)抽屜.根據(jù)首先考慮的兩個(gè)整數(shù)被 1 滁的兩種情況可 以把余數(shù)之和等于 10 的并成一類(lèi)，這樣分為：10k、10k k 10k 2.10k3、10k4.10k