2012江蘇省數(shù)學(xué)競(jìng)賽《提優(yōu)教程》教案：第36講__同_余

《2012江蘇省數(shù)學(xué)競(jìng)賽《提優(yōu)教程》教案：第36講__同_余》由會(huì)員分享，可在線閱讀，更多相關(guān)《2012江蘇省數(shù)學(xué)競(jìng)賽《提優(yōu)教程》教案：第36講__同_余（13頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、 第 17 講 同 余 同余是數(shù)論中的重要概念，同余理論是研究整數(shù)問(wèn)題的重要工具之一。 設(shè)m是一個(gè)給定的正整數(shù)，如果兩個(gè)整數(shù)a與b用m除所得的余數(shù)相同，則稱(chēng)a與b對(duì)模同余，記作，否則，就說(shuō)a與b對(duì)模m不 同余，記作， 顯然，； 1、 同余是一種等價(jià)關(guān)系，即有自反性、對(duì)稱(chēng)性、傳遞性 1).反身性：； 2).對(duì)稱(chēng)性：； 3). 傳遞性：若，則; 2、加、減、乘、乘方運(yùn)算 若 （mod m） （mod m） 則 （mod m），（mod m），（mod m） 3、除法 設(shè) （mod m）則 （mod）。 A類(lèi)例題 例1．證明： 一個(gè)數(shù)的各位數(shù)字的和被9除的余數(shù)等

2、于這個(gè)數(shù)被9除的余數(shù)。 分析 20≡2(mod9)，500≡5(mod9)，7000≡7(mod9)，……，由于10n－1=9M，則10n≡1(mod9)，故an×10n≡an (mod9)?？梢钥紤]把此數(shù)變?yōu)槎囗?xiàng)式表示an×10n+ an-1×10n-1+…+ a1×10+a0后處理。 證明 設(shè)a==an×10n+ an-1×10n-1+…+ a1×10+a0， ∵10≡1(mod9)，∴10n≡1(mod9)， ∴an×10n+ an-1×10n-1+…+ a1×10+a0≡an+ an-1+…+ a1+a0。 說(shuō)明 要熟練記憶并應(yīng)用常見(jiàn)的數(shù)據(jù)模的特征。 例2．A，B兩人玩

3、一種32張撲克牌的取牌游戲，A先取，以后輪流進(jìn)行，每次只能從剩下的牌中取1張，或者質(zhì)數(shù)張牌，誰(shuí)取到最后一張牌獲勝，問(wèn)：誰(shuí)有必勝策略？ 分析 原有32張牌，如果A總?cè)∑鏀?shù)張牌，B只要取1張牌，使A面臨偶數(shù)張牌就可以了，此時(shí)A總不能取完偶數(shù)張牌。但2是質(zhì)數(shù)，A可以取兩張牌。注意到32是4的倍數(shù)，A只能取奇數(shù)張牌或2張牌，B的應(yīng)對(duì)方案稍作調(diào)整，可以有必勝的策略。 解 B有必勝策略。由于32≡0（mod 4）， 而A取的牌不能是4及其倍數(shù)，從而A取后，剩下的牌張數(shù)x≡3（mod 4），或x≡2（mod 4），或x≡1（mod 4）， 于是B可以通過(guò)取1，2或3張牌，使得剩下的牌的張數(shù)y≡0

4、（mod 4）， 所以，B依次此策略，在A取后，剩下的牌張數(shù)不同余于0（mod 4），總是有牌，而B(niǎo)取后剩下的牌的張數(shù)y≡0（mod 4），從而B(niǎo)能取到最后一張牌。 例3 在已知數(shù)列1，4，8，10，16，19，21，25，30，43中，相鄰若干數(shù)之和，能被11整除的數(shù)組共有多少組。 分析 相鄰若干數(shù)之和可通過(guò)，中來(lái)實(shí)現(xiàn)。 解 記數(shù)列各對(duì)應(yīng)項(xiàng)為并記 依次為1、5、13、23、39、58、79、104、134、177它們被11除的余數(shù)依次為1、5、2、1、6、3、2、5、2、1。由此可得 由于是數(shù)列相鄰項(xiàng)之和，且當(dāng)時(shí) ，則滿(mǎn)足條件的數(shù)組有：3+1+3=7組。 說(shuō)明 在解題的適當(dāng)

5、時(shí)候取模的運(yùn)算會(huì)使運(yùn)算量減少，并使過(guò)程變得簡(jiǎn)潔。 情景再現(xiàn) 1．能否把1，2，……，1980這1980個(gè)數(shù)分成四組，令每組數(shù)之和為，且滿(mǎn)足。 2．兩人做一種游戲：輪流報(bào)數(shù)，報(bào)出的數(shù)只能是1，2，3，4，5，6，7，8，9，10，把兩人報(bào)出的數(shù)連加起來(lái)，如果得數(shù)是2003，最后報(bào)數(shù)的人就獲勝．現(xiàn)在甲、乙兩人已經(jīng)依次報(bào)過(guò)3，5，7，5，6，乙再接著報(bào)下一個(gè)數(shù)，那么乙經(jīng)過(guò)動(dòng)腦筋，發(fā)現(xiàn)應(yīng)該報(bào)某一號(hào)就有贏的把握．試問(wèn)乙應(yīng)該報(bào)哪一號(hào)？以后各次報(bào)數(shù)時(shí)乙應(yīng)如何報(bào)數(shù)才能保證贏？ 3．（前南斯拉夫數(shù)學(xué)競(jìng)賽，1988年）有27個(gè)國(guó)家參加的一次國(guó)際會(huì)議，每個(gè)國(guó)家有兩名代表．求證：不可能將54位代表安排在

6、一張圓桌的周?chē)妥?，使得任一?guó)家的兩位代表之間都夾有9個(gè)人． B類(lèi)例題 例4．共1998個(gè)小朋友圍坐一圈，從某人開(kāi)始逆時(shí)針?lè)较驁?bào)數(shù)，從1報(bào)到64，一直報(bào)下去，直到每人報(bào)過(guò)10次為止． ⑴ 有沒(méi)有報(bào)過(guò)5，又報(bào)過(guò)10的人？ ⑵ 有沒(méi)有報(bào)過(guò)5，又報(bào)過(guò)11的人？ 分析 報(bào)過(guò)5（10）的人的編號(hào)模64的同余特征是本題的突破口。 解 把這些學(xué)生依次編為1——1998號(hào)． ⑴設(shè)既報(bào)過(guò)5又報(bào)過(guò)10 的人原編為x號(hào)，則有 x+1998k≡5 (mod 64) x+1998l≡10(mod 64) ∴ 1998(l－k)≡5(mod 64)，即1998(l

7、－k)=5+64n，這不可能． ⑵ 既報(bào)5又報(bào)11的人原來(lái)編為x 號(hào)． x+1998k≡5 (mod 64) x+1998l≡11(mod 64) ∴ 1998(l－k)≡6(mod 64)，即14(l－k)=6+64n，T7(l－k)=3+32n，取n=1，得l－k=5，即第k圈報(bào)5的人，第k+5圈后報(bào)11， ∵ 1998×5=64×156+6，這說(shuō)明前5圈報(bào)5的人共157個(gè)，即共有157人既報(bào)5又報(bào)11． 說(shuō)明 本題是同余在解不定方程（組）上的一個(gè)簡(jiǎn)單應(yīng)用。 例5 （1992年友誼杯國(guó)際數(shù)學(xué)競(jìng)賽）求最大的正整數(shù)x，使得對(duì)任意y∈N，有x|（）。 分析 x最大不超過(guò)的

8、最小值18，（mod18）（mod2）, （mod9）。 解 由條件，x |（7＋12－1），x |18，故x≤18。下證：對(duì)任意y∈N，有18|（）。 事實(shí)上，首先是偶數(shù)，所以2|（）；其次，當(dāng)y=3k（k∈N*）時(shí)，≡≡－1≡0（mod 9），當(dāng)y=3k＋1（k∈N*）時(shí)，≡≡7＋3－1≡0（mod 9），當(dāng)y=3k＋2時(shí)，≡≡49－4≡0（mod 9）。故對(duì)任意y∈N*，有9|。∵（2，9）=1 ∴18| 所求的x為18 說(shuō)明 本題中將模18分解為模2與模9來(lái)處理充分觀察到模9的特征。 例6 試求出一切可使被3整除的自然數(shù)。 分析 。對(duì)n按6的同余類(lèi)分類(lèi)處理

9、。 說(shuō)明 要體會(huì)模6的選取。中對(duì)n按模3分類(lèi)，對(duì)按模2分類(lèi)可以分別確定結(jié)果，所以選擇按模6分類(lèi)。 情景再現(xiàn) 4．設(shè)a為小于100的自然數(shù)，且a3+23能被24整除，這樣的a有多少個(gè)？ 5．求除以13的余數(shù)。 6． 有三堆棋子的個(gè)數(shù)分別為19，8，9．現(xiàn)進(jìn)行如下操作：每次從三堆中的任意兩堆中分別取出1個(gè)棋子，然后把這2個(gè)棋子都加到另一堆上去．試問(wèn)：能否經(jīng)過(guò)若干次這樣的操作使得（1）三堆的棋子數(shù)目分別為2，12，22；（2）三堆棋子的數(shù)目均為12． C類(lèi)例題 例7（第20屆IMO試題）數(shù)1978n與1978m的最末三位數(shù)相等，試求正整數(shù)m和n，使得n+m取最小

10、值，這里 分析 數(shù)1978n與1978m的最末三位數(shù)相等等價(jià)于1978n-m≡1（mod1000），尋找最小的n-m及m。 解 由已知1000=8×125，所以 ① ② 因，且（1978m，125）=1，則由②式知1978n-m≡1（mod125）③ 又直接驗(yàn)證知，1978的各次方冪的個(gè)位數(shù)字是以8、4、2、6循環(huán)出現(xiàn)的，所以只有n－m為4的倍數(shù)時(shí)，③式才能成立，因而可令n－m=4k.由于. n+m=（ n－m）+2m=4k+2m，因而只需確定

11、出k和m的最小值. 先確定k的最小值：因?yàn)?9784=（79×25+3）4≡34≡1（mod5），19784≡34≡6（mod25）.故可令19784=5t+1，而5不整除t，從而0≡1978n-m－1=19784k－1=（5k+1）k－1≡+，顯然，使上式成立的k的最小值為25. 再確定m的最小值：因1978≡2（mod8），則由①式知， ④ 由于④式顯然對(duì)m=1，2不成立，從而m的最小值為3. 故合于題設(shè)條件的n+m的最小值為106. 說(shuō)明 此例中我們用了這樣一個(gè)結(jié)論：1978的各次方冪的個(gè)位數(shù)字是以8，4，2，6循環(huán)出現(xiàn)，即，當(dāng)r=1，2，3，4時(shí)，這種現(xiàn)象在數(shù)學(xué)上

12、稱(chēng)為“模同期現(xiàn)象”.一般地，我們有如下定義： 整數(shù)列各項(xiàng)除以m（m≥2，m∈N*）后的余數(shù)組成數(shù)列.若是一個(gè)周期數(shù)列，則稱(chēng)是關(guān)于模m的周期數(shù)列，簡(jiǎn)稱(chēng)模m周期數(shù)列.滿(mǎn)足（或（modm））的最小正整數(shù)T稱(chēng)為它的周期. 例8 （第29屆IMO預(yù)選題）設(shè)a是方程的最大正根，求證：17可以整除[a1788]與[a1988].其中[x]表示不超過(guò)x的最大整數(shù). 分析 探求是本題的關(guān)鍵，而a的值無(wú)法準(zhǔn)確計(jì)算得到。所以本題通過(guò)韋達(dá)定理尋求了的遞推形式。 證明 根據(jù)如下符號(hào)表可知，若設(shè)三根依次為， 則 x －1 － 1

13、 3 f(x)符號(hào) － + + － － + 。 另一方面，由韋達(dá)定理知， 為了估計(jì)[]、[]，先一般考察[an]，為此定義： 直接計(jì)算可知： 又因 當(dāng)時(shí)， 由此知，命題變?yōu)樽C明：能被17整除. 現(xiàn)考察在模17的意義下的情況： 可見(jiàn)，在模17意義下，是16為周期的模周期數(shù)列，即由于 1788 故命題得證. 說(shuō)明 本題利用導(dǎo)數(shù)估計(jì)了根的分布，遞推式的構(gòu)造需要仔細(xì)體味。 情景再現(xiàn) 7．設(shè)三角形的三邊長(zhǎng)分別是整數(shù)且已知其中而表示不超過(guò)的最大整數(shù). 求這種三角形周長(zhǎng)的

14、最小值. 習(xí)題17 A 1．證明對(duì)于任何整數(shù),能被7整除； 2．試判斷能被3整除嗎？ 3．求14＋24＋34＋…＋20044的末位數(shù)。 4．試證：對(duì)一切正整數(shù)n，能被8整除。 B 5．設(shè)是最初的幾個(gè)質(zhì)數(shù)的乘積，這里。證明p-1和p+1都不是完全平方數(shù)。 6．設(shè)a，b，c，d是4個(gè)整數(shù)，證明：差b－a，c－a，d－a，c－b，d－b，d－c的積能被12整除。 7．正整數(shù)n滿(mǎn)足：十進(jìn)制表示下的末三位數(shù)為888，求滿(mǎn)足條件的最小的n值 。 8．在每張卡片上各寫(xiě)出11111到99999的五位數(shù)，然后把這些卡片按任意順序排成一列，證明所得到的444445位數(shù)不可能是2的冪；

15、 C 9．在1，2，3，…1989，…1994中最多可以取多少個(gè)數(shù)，使得所取的 數(shù)中任意3個(gè)數(shù)之和能被18整除。 10．給出一個(gè)數(shù)198519841983…654321，它是由大到小依次寫(xiě)出自然數(shù)1985、1984、…、直到寫(xiě)出3、2、1后連接成一個(gè)數(shù)而成，現(xiàn)從其首位起，把首位數(shù)字乘以2加上第二位數(shù)字，把結(jié)果再乘以2后加上第三位數(shù)字，再把結(jié)果乘以2后加上第四位數(shù)字，…，這樣一直算下去，直到個(gè)位數(shù)字為止，于是得到一個(gè)新的數(shù)，把新的數(shù)再按上述方法做一次，又得第二個(gè)數(shù)，…這樣一直做下去，直到得到一個(gè)一位數(shù)為止，問(wèn)得到的一位數(shù)是多少？ 11．設(shè)a,b,c 是三個(gè)互不相等的正整數(shù)，求證：a3b－

16、ab3，b3c－bc3,c3a－ca3三個(gè)數(shù)中，至少有一個(gè)數(shù)能被10整除． 12．連結(jié)正n邊形的頂點(diǎn)，得到一個(gè)閉的n年折線形，證明：當(dāng)n為 偶數(shù)，則在連線中有兩條平行線。 “情景再現(xiàn)”解答： 1． 2．解：3＋5＋7＋5＋6=26， 2003≡1(mod 11)，26＋x≡1(mod 11)Tx=8，即只要報(bào)8． 以后每次甲報(bào)k時(shí)，乙就報(bào)11－k即可． 3．將54個(gè)座位按逆時(shí)針由1開(kāi)始編號(hào)：1，2，3，…… 如果滿(mǎn)足要求的排法存在，則不妨設(shè)1和11是同一國(guó)的代表，從而11和21不是同一國(guó)的代表，故21和31是同一國(guó)家代表．進(jìn)一步可以得出：和是同一國(guó)家的代

17、表（若和大于54，則取它們被54除的余數(shù)為號(hào)碼的位置，比如61即等同于7）． 特別地，取時(shí)，261和271是同一國(guó)家的代表，然而 ，． 即1和45是同一國(guó)家的代表，與1和11是同一國(guó)家的代表矛盾．命題得證． 4． a3+23=a3－1+24, ∴a3－1≡0 (mod 24), ∴3|a3－1，8|a3－1． 由a≡0,1,2 (mod 3)得a3≡0,1,2 (mod 3)； 若a為偶數(shù)，則 a3≡0 (mod 8),若a為奇數(shù)，則a2≡1,故a3≡a (mod 8)． 從而 a≡1 (mod 24); 于是 a=1，25，49，73，97，共有5個(gè)數(shù)． 5． 10

18、01≡0（mod13） 108≡1000≡－1（mod13） 106≡1（mod13） 10≡4（mod13） 102≡16≡10（mod6） 103≡102≡10（mod6） 10n≡10n-1≡…≡10≡4（mod6） 10n＝6k＋4 ∴≡106k+4≡(106)k×104≡1k×104≡104≡3（mod13） 6． （1） ． （2）不可能完成．由于每次操作后，每堆棋子數(shù)目或者減1，或者加2，不妨寫(xiě)為 ． 若被3除的余數(shù)均不相等，則操作后得到的三個(gè)數(shù)，，被3除的余數(shù)的變化為 ，，． 也就是說(shuō)，每次操作后不改變?nèi)齻€(gè)數(shù)被3除的余數(shù)互不相

19、等這樣一個(gè)事實(shí)． 由于一開(kāi)始給的三個(gè)數(shù)被3除的余數(shù)各不相等，而所要求達(dá)到的結(jié)果被3除的余數(shù)都為0，故不能完成． 7． 由題設(shè)可知, 于是 由于(3,2)=(3,5)=1,∴由①可知. 現(xiàn)在設(shè)是滿(mǎn)足的最小正整數(shù),則對(duì)于任意滿(mǎn)足的正整數(shù),我們有,即u整除v.事實(shí)上,若不整除, 則由帶余除法可知,存在非負(fù)整數(shù)及, 使得,其中。 從而可以推出,而這顯然與的定義矛盾, 所以. 注意到 ，從而可以設(shè),其中為正整數(shù). 同理可由推出.故. 現(xiàn)在我們求滿(mǎn)足的正整數(shù). 因?yàn)?所以 即 或 即有,并代入該式得 即有. 即,其中為正整數(shù), 故,s為正整數(shù). 同理可以證得, 為正整

20、數(shù). 由于,所以有. 這樣一來(lái),三角形的三個(gè)邊為和.由于兩邊之差小于第三邊,故,因此,當(dāng)時(shí)三角形的周長(zhǎng)最小,其值為(1000+501)+(500+501)+501=3003. “習(xí)題”解答： A 1． 都能被7整除； 2． 3．解：記14＋24＋34＋…＋20044＝N，設(shè)N的末位數(shù)為a，則N≡a（mod 10） ∴N4≡a4（mod 10） ∵14≡1（mod 10）　24≡6（mod 10）　34≡1（mod 10）　44≡6（mod 10） 54≡5（mod 10）　64≡6（mod 10）　74≡1（mod 10）　84≡6（mod 10）　94≡

21、1（mod 10） ∴14＋24＋34＋…＋20044≡200×（14＋24＋34＋…＋104）＋14＋24＋34＋44≡14≡4（mod 10）即末位數(shù)為4 4．證明：若k為奇數(shù)，則或±3（mod 8）,（mod8） ∴當(dāng)k為奇數(shù)?。╩od 8）,∴（mod 8） 若n為正奇數(shù)， （mod 8） 若n為正偶數(shù)， （mod 8） ∴得證. B 5．對(duì)任意（mod 3） 所以或1（mod 3） 而3︱p 故 p-1（mod 3） p-1不是完全平方數(shù) 又 都是奇數(shù)，設(shè)＝2 k+1. 則（mod 4），而完全平方數(shù)0或1（mod 4）, （mod 4） 不是完全

22、平方數(shù)。 6．考慮這4個(gè)數(shù)模4的結(jié)果，如果有某兩個(gè)數(shù)對(duì)于模4同余，則這二數(shù)是4的倍數(shù)，如果這4個(gè)數(shù)對(duì)于模4沒(méi)有兩數(shù)同余，則這四數(shù)必兩奇兩偶，奇偶相同二數(shù)的差能被2整除，于是其積是4的倍數(shù)，即得。 再考慮這4個(gè)數(shù)模3的結(jié)果，由于任何整數(shù)模3后只能與0，1，2，這三個(gè)數(shù)同余，則必有二數(shù)對(duì)于模3同余，這二數(shù)的差能被3整除。 綜上即得。 7．依題意，知（mod1000）故n的末位數(shù)字為2，設(shè)n=10k+2， 則分別有 即（mod25） 故 25 ，所以 設(shè)，則 即，所以m=5r+3. 則 n=500r+192 ∴最小的n為192 8． C 9．設(shè)a，b，c，d是

23、取出來(lái)的數(shù)中任意四個(gè)，由a＋b＋c＝18n，a＋b＋d＝18m，18|(c－d) ，即取出的數(shù)對(duì)摸18的余數(shù)相同，設(shè)為k， 則a＋b＋c≡3k（mod18） k＝0，6，12。 而1994＝18×110×14 最多有6，24，42，…1986或12，30，48，…1992共111個(gè)數(shù)滿(mǎn)足。 10．解 設(shè)所給數(shù)為A，則A被8除的余數(shù)與321被8除的余數(shù)相同，但321=3×100+2×10+1≡3×4+2×2+1(mod 8)，又設(shè)第一次運(yùn)算得到的數(shù)為B，而B(niǎo)被8除的余數(shù)與(3×2+2)×2+1被8除的余數(shù)相同(A的千位以上的數(shù)字在運(yùn)算過(guò)程中均乘以2n?，其中n≥3

24、)。即B被8除的余數(shù)與A被8除的余數(shù)相同。對(duì)B的各位數(shù)字進(jìn)行運(yùn)算的結(jié)果記為C，同理可知，C被8除的余數(shù)與B被8除的余數(shù)相同，…，依此類(lèi)推，知最后所得的一位數(shù)被8除的余數(shù)與A被8被的余數(shù)相同，即余1。而此一位數(shù)由兩個(gè)自然數(shù)相加而得，故不等于1，從而，該一位數(shù)為9。 11．證明 a3b－ab3=ab(a+b)(a－b)；b3c－bc3=bc(b+c)(b－c)；c3a－ca3=ca(c+a)(c－a)． ⑴ 若a≡0(mod 2)或b≡0(mod 2)，則ab(a+b)(a－b)≡0(mod 2)； 若a≡1(mod 2)且b≡1(mod 2)，則a+b≡0(mod 2)且a－b≡0(

25、mod 2) 于是ab(a+b)(a－b)≡0(mod 2)；總之，a3b－ab3≡0(mod 2)， 同理b3c－bc3≡0(mod 2)，c3a－ca3≡0(mod 2)． ⑵ 若a≡0(mod 5)，則ab(a+b)(a－b)≡0(mod 5)且ca(c+a)(c－a)≡0(mod 5)， 故可知，當(dāng)a≡0，或b≡0，或c≡0(mod 5)時(shí)，考察 a3b－ab3，b3c－bc3,c3a－ca3 這三個(gè)數(shù)中，至少有2個(gè)能被5整除． 當(dāng)a 0(mod 5)且b0(mod 5)且c0(mod 5)時(shí)， ①若a≡b(mod 5)，則a－b≡0(mod 5)，于是ab(a+b)(

26、a－b)≡0(mod 5)． 同理若b≡c(mod 5)，則bc≡0 (b+c)(b－c) (mod 5)； 若c≡a(mod 5)，則ca(c+a)(c－a)≡0(mod 5)． ②若ab，bc，ca，則取M={1，4}，N={2，3}兩個(gè)集合． 由于a、b、c被5除的余數(shù)互不相等且只能是1，2，3，4中的某3個(gè)，故必存在兩個(gè)數(shù)，它們被5除的的余數(shù)或同屬于M，或同屬于N，不妨設(shè)a、b這兩個(gè)數(shù)被5除的余數(shù)屬于同一集合，則a+b≡0(mod 5)． 總之，a3b－ab3，b3c－bc3,c3a－ca3三個(gè)數(shù)中，至少有1個(gè)能被5整除． 綜上可知，a3b－ab3，b3c－bc3,c3a－

27、ca3三個(gè)數(shù)中，至少有一個(gè)數(shù)能被10整除． 12．依逆時(shí)針順序?qū)㈨旤c(diǎn)標(biāo)上0，1，…n－1，問(wèn)題中的閉折線可用n個(gè)數(shù)的一個(gè)排列 A0，A1，A2，…An-1，An＝A0 唯一地表示，且AiAi+1//AjAj+1 = Ai＋Ai+1≡Aj＋Aj+1（mod n） n為偶數(shù)，2不能整除(n－1) 模n的非負(fù)最小完全剩余系之和滿(mǎn)足 0＋1＋…＋(n－1)＝0（mod n） 另一方面 ＝2≡2×≡n(n－1)≡0（mod n） ∴Ai＋Ai+1（i＝0，…，n－1）不能構(gòu)成n的完全剩余后，必有i≠j，使Ai＋Ai+1≡Aj＋Aj+Aj+1（mod n）得證。