《初中數(shù)學(xué)競賽輔導(dǎo) 第四十六講《同余式》教案1 北師大版》由會(huì)員分享，可在線閱讀，更多相關(guān)《初中數(shù)學(xué)競賽輔導(dǎo) 第四十六講《同余式》教案1 北師大版（9頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、初中數(shù)學(xué)競賽輔導(dǎo) 第四十六講《同余式》教案1 北師大版 　　數(shù)論有它自己的代數(shù)，稱為同余理論．最先引進(jìn)同余的概念與記號(hào)的是數(shù)學(xué)王子高斯． 　　先看一個(gè)游戲：有n＋1個(gè)空格排成一行，第一格中放入一枚棋子，甲乙兩人交替移動(dòng)棋子，每步可前移1，2或3格，以先到最后一格者為勝．問是先走者勝還是后走者勝？應(yīng)該怎樣走才能取勝？ 　　取勝之道是：你只要設(shè)法使余下的空格數(shù)是4的倍數(shù)，以后你的對(duì)手若走i格(i=1，2，3)，你走4-i格，即每一次交替，共走了4格．最后只剩4個(gè)空格時(shí)，你的對(duì)手就必輸無疑了．因此，若n除以4的余數(shù)是1，2或3時(shí)，那么先走者甲勝；若n除以4的余數(shù)是0的話，那么后走者乙勝． 　

2、　在這個(gè)游戲里，我們可以看出，有時(shí)我們不必去關(guān)心一個(gè)數(shù)是多少，而要關(guān)心這個(gè)數(shù)用m除后的余數(shù)是什么．又例如，xx年元旦是星期五，xx年有365天，365=7×52＋1，所以xx年的元旦是星期六．這里我們關(guān)心的也是余數(shù)．這一講中，我們將介紹同余的概念、性質(zhì)及一些簡單的應(yīng)用． 　　同余，顧名思義，就是余數(shù)相同． 　　定義1 給定一個(gè)正整數(shù)m，如果用m去除a，b所得的余數(shù)相同，則稱a與b對(duì)模m同余，記作 a≡b(modm)， 　　并讀作a同余b，模m． 　　若a與b對(duì)模m同余，由定義1，有 a=mq1＋r，b=mq2+r． 　　所以 a-b=m(q1-q2)， 　　即 m｜a-b．

3、　　反之，若m｜a-b，設(shè) a=mq1＋r1，b=mq2＋r2，0≤r1，r2≤m-1， 　　則有m｜r1-r2．因｜r1-r2｜≤m-1，故r1-r2=0，即r1＝r2． 　　于是，我們得到同余的另一個(gè)等價(jià)定義： 　　定義2 若a與b是兩個(gè)整數(shù)，并且它們的差a-b能被一正整數(shù)m整除，那么，就稱a與b對(duì)模m同余． 　　同余式的寫法，使我們聯(lián)想起等式．其實(shí)同余式和代數(shù)等式有一些相同的性質(zhì)，最簡單的就是下面的定理1． 　　定理1 (1)a≡a(modm)． 　　(2) 若a≡b(modm)，則b≡a(modm)． 　　(3) 若a≡b(modm)，b≡c(modm)，則a≡c(mo

4、dm)． 　　在代數(shù)中，等式可以相加、相減和相乘，同樣的規(guī)則對(duì)同余式也成立． 　　定理2 若a≡b(modm)，c≡d(modm)，則 　　a±c≡b±d(modm)，ac≡bd(modm)． 　　證 由假設(shè)得m｜a-b，m｜c(diǎn)-d，所以 m｜(a±c)-(b±d)， m｜c(diǎn)(a-b)＋b(c-d)， 　　即 a±c≡b±d(modm)，ac≡bd(modm)． 　　由此我們還可以得到：若a≡b(modm)，k是整數(shù)，n是自然數(shù)，則 a±k≡b±k(modm)， ak≡bk(modm)，an≡bn(modm)． 　　對(duì)于同余式ac≡bc(modm)，我們是否能約去公約數(shù)c

5、，得到一個(gè)正確的同余式a≡b(modm)？ 　　在這個(gè)問題上，同余式與等式是不同的．例如 25≡5(mod 10)， 　　約去5得 5≡1(mod 10)． 　　這顯然是不正確的．但下面這種情形，相約是可以的． 　　定理3 若ac≡bc(modm)，且(c，m)=1，則 　　a≡b(modm)． 　　證 由題設(shè)知 ac-bc=(a-b)c=mk． 　　由于(m，c)=1，故m｜a-b，即a≡b(modm)． 　　定理4 若n≥2， a≡b(modm1)， a≡b(modm2)， ………… a≡b(modmn)， 　　且M=[m1，m2，…，mn]表示m1，m2，

6、…，mn的最小公倍數(shù)，則 a≡b(modM)． 　　前面介紹了同余式的一些基本內(nèi)容，下面運(yùn)用同余這一工具去解決一些具體問題． 　　應(yīng)用同余式的性質(zhì)可以簡捷地處理一些整除問題．若要證明m整除a，只需證a≡0(modm)即可． 　　例1 求證： 　　(1)8｜(55xx＋17)； 　　(2) 8(32n＋7)； 　　(3)17｜(191000-1)． 　　證 (1)因55≡-1(mod 8)，所以55xx≡-1(mod 8)，55xx＋17≡-1＋17=16≡0(mod 8)，于是8｜(55xx＋17)． 　　(2)32=9≡1(mod 8)，32n≡1(mod 8)，所以32n

7、＋7≡1＋7≡0(mod 8)，即8｜(32n＋7)． 　　(3)19≡2(mod 17)，194≡24=16≡-1(mod 17)，所以191000=(194)250≡(-1)250≡1(mod 17)，于是 17｜(191000-1)． 　　例2 求使2n-1為7的倍數(shù)的所有正整數(shù)n． 　　解 因?yàn)?3≡8≡1(mod 7)，所以對(duì)n按模3進(jìn)行分類討論． 　　(1) 若n=3k，則 2n-1＝(23)k-1＝8k-1≡1k-1＝0(mod 7)； 　　(2) 若n=3k＋1，則 2n-1=2·(23)k-1=2·8k-1 　　　≡2·1k-1＝1(mod 7)； 　　(

8、3) 若n=3k＋2，則 2n-1=22·(23)k-1=4·8k-1 　　　≡4·1k-1＝3(mod 7)． 　　所以，當(dāng)且僅當(dāng)3｜n時(shí)，2n-1為7的倍數(shù)． 　　例3 對(duì)任意的自然數(shù)n，證明 A=2903n-803n-464n＋261n 　　能被1897整除． 　　證 1897=7×271，7與271互質(zhì)．因?yàn)? 2903≡5(mod 7)， 803≡5(mod 7)， 464≡2(mod 7)， 261≡2(mod 7)， 　　所以 A=2903n-803n-464n+261n 　　≡5n-5n-2n+2n=0(mod 7)， 　　故7｜A．又因?yàn)? 290

9、3≡193(mod 271)， 803≡261(mod 271)， 464≡193(mod 271)， 　　所以 　　故271｜A．因(7，271)=1，所以1897整除A． 　　例4 把1，2，3…，127，128這128個(gè)數(shù)任意排列為a1，a2，…，a128，計(jì)算出 ｜a1-a2｜，｜a3-a4｜ ，…，｜a127-a128｜， 　　再將這64個(gè)數(shù)任意排列為b1，b2，…，b64，計(jì)算 ｜b1-b2｜，｜b3-b4｜，…，｜b63-b64｜． 　　如此繼續(xù)下去，最后得到一個(gè)數(shù)x，問x是奇數(shù)還是偶數(shù)？ 　　解 因?yàn)閷?duì)于一個(gè)整數(shù)a，有 ｜a｜≡a(mod 2)， a≡

10、-a(mod 2)， 　　所以 　　b1＋b2＋…＋b64 　　=｜a1-a2｜+｜a3-a4｜+…+｜a127-a128｜ 　　≡a1-a2＋a3-a4+…+a127-a128 　　≡a1＋a2＋a3＋a4+…+a127＋a128(mod 2)， 　　因此，每經(jīng)過一次“運(yùn)算”，這些數(shù)的和的奇偶性是不改變的．最終得到的一個(gè)數(shù) 　　x≡a1＋a2＋…＋a128＝1＋2＋…＋128 　　 ＝64×129≡0(mod 2)， 　　故x是偶數(shù)． 　　如果要求一個(gè)整數(shù)除以某個(gè)正整數(shù)的余數(shù)，同余是一個(gè)有力的工具．另外，求一個(gè)數(shù)的末位數(shù)字就是求這個(gè)數(shù)除以10的余數(shù)，求一個(gè)數(shù)的末兩位數(shù)字就

11、是求這個(gè)數(shù)除以100的余數(shù)． 　　例5 求證：一個(gè)十進(jìn)制數(shù)被9除的余數(shù)等于它的各位數(shù)字之和被9除的余數(shù)． 　　 10≡1(mod 9)， 　　故對(duì)任何整數(shù)k≥1，有 10k≡1k＝1(mod 9)． 　　因此 　　即A被9除的余數(shù)等于它的各位數(shù)字之和被9除的余數(shù)． 　　說明 (1)特別地，一個(gè)數(shù)能被9整除的充要條件是它的各位數(shù)字之和能被9整除． 　　(2)算術(shù)中的“棄九驗(yàn)算法”就是依據(jù)本題的結(jié)論． 　　例6 任意平方數(shù)除以4余數(shù)為0和1(這是平方數(shù)的重要特征)． 　　證 因?yàn)? 奇數(shù)2=(2k＋1)2=4k2＋4k+1≡1(mod 4)， 偶數(shù)2=(2k)2=4k2

12、≡0(mod 4)， 　　所以 　　例7 任意平方數(shù)除以8余數(shù)為0，1，4(這是平方數(shù)的又一重要特征)． 　　證 奇數(shù)可以表示為2k＋1，從而 奇數(shù)2=4k2＋4k+1=4k(k＋1)+1． 　　因?yàn)閮蓚€(gè)連續(xù)整數(shù)k，k＋1中必有偶數(shù)，所以4k(k＋1)是8的倍數(shù)，從而 奇數(shù)2=8t+1≡1(mod 8)， 偶數(shù)2=(2k)2=4k2(k為整數(shù))． 　　(1)若k=偶數(shù)=2t，則 4k2=16t2＝0(mod 8)． 　　(2)若k=奇數(shù)=2t+1，則 4k2=4(2t＋1)2=16(t2＋t)+4≡4(mod 8)， 　　所以 　　求余數(shù)是同余的基本問題．在這

13、種問題中，先求出與±1同余的數(shù)是一種基本的解題技巧． 　　例8 (1)求33除2xx的余數(shù)． 　　(2)求8除72n+1-1的余數(shù)． 　　解 (1)先找與±1(mod 33)同余的數(shù)．因?yàn)? 25＝32≡-1(mod 33)， 　　所以 210≡1(mod 33)， 2xx=(210)199·25·23≡-8≡25(mod 33)， 　　所求余數(shù)為25． 　　(2)因?yàn)?≡-1(mod 8)，所以 72n＋1≡(-1)2n＋1＝-1(mod 8)， 72n＋1-1≡-2≡6(mod 8)， 　　即余數(shù)為6． 　　例9 形如 Fn＝22n+1，n=0，1，2，… 　　的

14、數(shù)稱為費(fèi)馬數(shù)．證明：當(dāng)n≥2時(shí)，F(xiàn)n的末位數(shù)字是7． 　　證 當(dāng)n≥2時(shí)，2n是4的倍數(shù)，故令2n=4t．于是 Fn=22n＋1=24t+1=16t＋1 ≡6t＋1≡7(mod 10)， 　　即Fn的末位數(shù)字是7． 　　說明 費(fèi)馬數(shù)的頭幾個(gè)是 F0＝3，F(xiàn)1＝5，F(xiàn)2＝17，F(xiàn)3＝257，F(xiàn)4＝65537， 　　它們都是素?cái)?shù)．費(fèi)馬便猜測：對(duì)所有的自然數(shù)n，F(xiàn)n都是素?cái)?shù)．然而，這一猜測是錯(cuò)誤的．首先推翻這個(gè)猜測的是歐拉，他證明了下一個(gè)費(fèi)馬數(shù)F5是合數(shù)．證明F5是合數(shù)，留作練習(xí)． 　　利用同余還可以處理一些不定方程問題． 　　例10 證明方程 x4+y4+2=5z 　　沒有整

15、數(shù)解． 　　證 對(duì)于任一整數(shù)x，以5為模，有 x≡0，±1，±2(mod 5)， x2≡0，1，4(mod 5)， x4≡0，1，1(mod 5)， 　　即對(duì)任一整數(shù)x， x4≡0，1(mod 5)． 　　同樣，對(duì)于任一整數(shù)y y4≡0，1(mod 5)， 　　所以 x4+y4+2≡2，3，4(mod 5)， 　　從而所給方程無整數(shù)解． 　　說明 同余是處理不定方程的基本方法，但這種方法也非常靈活，關(guān)鍵在于確定所取的模(本例我們?nèi)∧?)，這往往應(yīng)根據(jù)問題的特點(diǎn)來確定． 練習(xí)二十五 　　1．求證：17｜(191000-1)． 　　2．證明：對(duì)所有自然數(shù)n，330｜(62n-52n-11)． 　　 　　4．求21000除以13的余數(shù)． 　　5．求15＋25＋35＋…＋995＋1005除以4所得的余數(shù)． 　　6．今天是星期天，過3100天是星期幾？再過5xx天又是星期幾？ 　　7．求n=1×3×5×7×…×xx的末三位數(shù)字． 　　8．證明不定方程x2+y2-8z=6無整數(shù)解． 　　?