《初中數學競賽輔導 第四十六講《同余式》教案1 北師大版》由會員分享，可在線閱讀，更多相關《初中數學競賽輔導 第四十六講《同余式》教案1 北師大版（9頁珍藏版）》請在裝配圖網上搜索。

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

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

3、　　反之，若m｜a-b，設 a=mq1＋r1，b=mq2＋r2，0≤r1，r2≤m-1， 　　則有m｜r1-r2．因｜r1-r2｜≤m-1，故r1-r2=0，即r1＝r2． 　　于是，我們得到同余的另一個等價定義： 　　定義2 若a與b是兩個整數，并且它們的差a-b能被一正整數m整除，那么，就稱a與b對模m同余． 　　同余式的寫法，使我們聯想起等式．其實同余式和代數等式有一些相同的性質，最簡單的就是下面的定理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)． 　　在代數中，等式可以相加、相減和相乘，同樣的規(guī)則對同余式也成立． 　　定理2 若a≡b(modm)，c≡d(modm)，則 　　a±c≡b±d(modm)，ac≡bd(modm)． 　　證 由假設得m｜a-b，m｜c-d，所以 m｜(a±c)-(b±d)， m｜c(a-b)＋b(c-d)， 　　即 a±c≡b±d(modm)，ac≡bd(modm)． 　　由此我們還可以得到：若a≡b(modm)，k是整數，n是自然數，則 a±k≡b±k(modm)， ak≡bk(modm)，an≡bn(modm)． 　　對于同余式ac≡bc(modm)，我們是否能約去公約數c

5、，得到一個正確的同余式a≡b(modm)？ 　　在這個問題上，同余式與等式是不同的．例如 25≡5(mod 10)， 　　約去5得 5≡1(mod 10)． 　　這顯然是不正確的．但下面這種情形，相約是可以的． 　　定理3 若ac≡bc(modm)，且(c，m)=1，則 　　a≡b(modm)． 　　證 由題設知 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的最小公倍數，則 a≡b(modM)． 　　前面介紹了同余式的一些基本內容，下面運用同余這一工具去解決一些具體問題． 　　應用同余式的性質可以簡捷地處理一些整除問題．若要證明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的倍數的所有正整數n． 　　解 因為23≡8≡1(mod 7)，所以對n按模3進行分類討論． 　　(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)． 　　所以，當且僅當3｜n時，2n-1為7的倍數． 　　例3 對任意的自然數n，證明 A=2903n-803n-464n＋261n 　　能被1897整除． 　　證 1897=7×271，7與271互質．因為 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．又因為 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個數任意排列為a1，a2，…，a128，計算出 ｜a1-a2｜，｜a3-a4｜ ，…，｜a127-a128｜， 　　再將這64個數任意排列為b1，b2，…，b64，計算 ｜b1-b2｜，｜b3-b4｜，…，｜b63-b64｜． 　　如此繼續(xù)下去，最后得到一個數x，問x是奇數還是偶數？ 　　解 因為對于一個整數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)， 　　因此，每經過一次“運算”，這些數的和的奇偶性是不改變的．最終得到的一個數 　　x≡a1＋a2＋…＋a128＝1＋2＋…＋128 　　 ＝64×129≡0(mod 2)， 　　故x是偶數． 　　如果要求一個整數除以某個正整數的余數，同余是一個有力的工具．另外，求一個數的末位數字就是求這個數除以10的余數，求一個數的末兩位數字就

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

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

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

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

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