初中數(shù)學競賽輔導 第四十六講《同余式》教案1 北師大版

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

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

2、個數(shù)是多少，而要關心這個數(shù)用m除后的余數(shù)是什么又例如，xx年元旦是星期五，xx年有365天，365=7521，所以xx年的元旦是星期六這里我們關心的也是余數(shù)這一講中，我們將介紹同余的概念、性質及一些簡單的應用同余，顧名思義，就是余數(shù)相同定義1 給定一個正整數(shù)m，如果用m去除a，b所得的余數(shù)相同，則稱a與b對模m同余，記作ab(modm)，并讀作a同余b，模m若a與b對模m同余，由定義1，有a=mq1r，b=mq2+r所以 a-b=m(q1-q2)，即 ma-b反之，若ma-b，設a=mq1r1，b=mq2r2，0r1，r2m-1，則有mr1-r2因r1-r2m-1，故r1-r2=0，即r1r2

3、于是，我們得到同余的另一個等價定義：定義2 若a與b是兩個整數(shù)，并且它們的差a-b能被一正整數(shù)m整除，那么，就稱a與b對模m同余同余式的寫法，使我們聯(lián)想起等式其實同余式和代數(shù)等式有一些相同的性質，最簡單的就是下面的定理1定理1 (1)aa(modm)(2) 若ab(modm)，則ba(modm)(3) 若ab(modm)，bc(modm)，則ac(modm)在代數(shù)中，等式可以相加、相減和相乘，同樣的規(guī)則對同余式也成立定理2 若ab(modm)，cd(modm)，則acbd(modm)，acbd(modm)證 由假設得ma-b，mc-d，所以m(ac)-(bd)， mc(a-b)b(c-d)，即

4、acbd(modm)，acbd(modm)由此我們還可以得到：若ab(modm)，k是整數(shù)，n是自然數(shù)，則akbk(modm)，akbk(modm)，anbn(modm)對于同余式acbc(modm)，我們是否能約去公約數(shù)c，得到一個正確的同余式ab(modm)？在這個問題上，同余式與等式是不同的例如255(mod 10)，約去5得51(mod 10)這顯然是不正確的但下面這種情形，相約是可以的定理3 若acbc(modm)，且(c，m)=1，則ab(modm)證 由題設知ac-bc=(a-b)c=mk由于(m，c)=1，故ma-b，即ab(modm)定理4 若n2，ab(modm1)，ab(

5、modm2)，ab(modmn)，且M=m1，m2，mn表示m1，m2，mn的最小公倍數(shù)，則ab(modM)前面介紹了同余式的一些基本內容，下面運用同余這一工具去解決一些具體問題應用同余式的性質可以簡捷地處理一些整除問題若要證明m整除a，只需證a0(modm)即可例1 求證：(1)8(55xx17)；(2) 8(32n7)；(3)17(191000-1)證 (1)因55-1(mod 8)，所以55xx-1(mod 8)，55xx17-117=160(mod 8)，于是8(55xx17)(2)32=91(mod 8)，32n1(mod 8)，所以32n7170(mod 8)，即8(32n7)(3

6、)192(mod 17)，19424=16-1(mod 17)，所以191000=(194)250(-1)2501(mod 17)，于是17(191000-1)例2 求使2n-1為7的倍數(shù)的所有正整數(shù)n解 因為2381(mod 7)，所以對n按模3進行分類討論(1) 若n=3k，則2n-1(23)k-18k-11k-10(mod 7)；(2) 若n=3k1，則2n-1=2(23)k-1=28k-121k-11(mod 7)；(3) 若n=3k2，則2n-1=22(23)k-1=48k-141k-13(mod 7)所以，當且僅當3n時，2n-1為7的倍數(shù)例3 對任意的自然數(shù)n，證明A=2903n

7、-803n-464n261n能被1897整除證 1897=7271，7與271互質因為29035(mod 7)，8035(mod 7)，4642(mod 7)，2612(mod 7)，所以A=2903n-803n-464n+261n5n-5n-2n+2n=0(mod 7)，故7A又因為2903193(mod 271)，803261(mod 271)，464193(mod 271)，所以故271A因(7，271)=1，所以1897整除A例4 把1，2，3，127，128這128個數(shù)任意排列為a1，a2，a128，計算出a1-a2，a3-a4 ，a127-a128，再將這64個數(shù)任意排列為b1，b

8、2，b64，計算b1-b2，b3-b4，b63-b64如此繼續(xù)下去，最后得到一個數(shù)x，問x是奇數(shù)還是偶數(shù)？解 因為對于一個整數(shù)a，有aa(mod 2)， a-a(mod 2)，所以b1b2b64=a1-a2+a3-a4+a127-a128a1-a2a3-a4+a127-a128a1a2a3a4+a127a128(mod 2)，因此，每經(jīng)過一次“運算”，這些數(shù)的和的奇偶性是不改變的最終得到的一個數(shù)xa1a2a12812128 641290(mod 2)，故x是偶數(shù)如果要求一個整數(shù)除以某個正整數(shù)的余數(shù)，同余是一個有力的工具另外，求一個數(shù)的末位數(shù)字就是求這個數(shù)除以10的余數(shù)，求一個數(shù)的末兩位數(shù)字就是

9、求這個數(shù)除以100的余數(shù)例5 求證：一個十進制數(shù)被9除的余數(shù)等于它的各位數(shù)字之和被9除的余數(shù)101(mod 9)，故對任何整數(shù)k1，有10k1k1(mod 9)因此即A被9除的余數(shù)等于它的各位數(shù)字之和被9除的余數(shù)說明 (1)特別地，一個數(shù)能被9整除的充要條件是它的各位數(shù)字之和能被9整除(2)算術中的“棄九驗算法”就是依據(jù)本題的結論例6 任意平方數(shù)除以4余數(shù)為0和1(這是平方數(shù)的重要特征)證 因為奇數(shù)2=(2k1)2=4k24k+11(mod 4)，偶數(shù)2=(2k)2=4k20(mod 4)，所以例7 任意平方數(shù)除以8余數(shù)為0，1，4(這是平方數(shù)的又一重要特征)證 奇數(shù)可以表示為2k1，從而奇數(shù)

10、2=4k24k+1=4k(k1)+1因為兩個連續(xù)整數(shù)k，k1中必有偶數(shù)，所以4k(k1)是8的倍數(shù)，從而奇數(shù)2=8t+11(mod 8)，偶數(shù)2=(2k)2=4k2(k為整數(shù))(1)若k=偶數(shù)=2t，則4k2=16t20(mod 8)(2)若k=奇數(shù)=2t+1，則4k2=4(2t1)2=16(t2t)+44(mod 8)，所以求余數(shù)是同余的基本問題在這種問題中，先求出與1同余的數(shù)是一種基本的解題技巧例8 (1)求33除2xx的余數(shù)(2)求8除72n+1-1的余數(shù)解 (1)先找與1(mod 33)同余的數(shù)因為2532-1(mod 33)，所以 2101(mod 33)，2xx=(210)1992

11、523-825(mod 33)，所求余數(shù)為25(2)因為7-1(mod 8)，所以72n1(-1)2n1-1(mod 8)，72n1-1-26(mod 8)，即余數(shù)為6例9 形如Fn22n+1，n=0，1，2，的數(shù)稱為費馬數(shù)證明：當n2時，F(xiàn)n的末位數(shù)字是7證 當n2時，2n是4的倍數(shù)，故令2n=4t于是Fn=22n1=24t+1=16t16t17(mod 10)，即Fn的末位數(shù)字是7說明 費馬數(shù)的頭幾個是F03，F(xiàn)15，F(xiàn)217，F(xiàn)3257，F(xiàn)465537，它們都是素數(shù)費馬便猜測：對所有的自然數(shù)n，F(xiàn)n都是素數(shù)然而，這一猜測是錯誤的首先推翻這個猜測的是歐拉，他證明了下一個費馬數(shù)F5是合數(shù)證明

12、F5是合數(shù)，留作練習利用同余還可以處理一些不定方程問題例10 證明方程x4+y4+2=5z沒有整數(shù)解證 對于任一整數(shù)x，以5為模，有x0，1，2(mod 5)，x20，1，4(mod 5)，x40，1，1(mod 5)，即對任一整數(shù)x，x40，1(mod 5)同樣，對于任一整數(shù)yy40，1(mod 5)，所以 x4+y4+22，3，4(mod 5)，從而所給方程無整數(shù)解說明 同余是處理不定方程的基本方法，但這種方法也非常靈活，關鍵在于確定所取的模(本例我們取模5)，這往往應根據(jù)問題的特點來確定練習二十五1求證：17(191000-1)2證明：對所有自然數(shù)n，330(62n-52n-11)4求21000除以13的余數(shù)5求1525359951005除以4所得的余數(shù)6今天是星期天，過3100天是星期幾？再過5xx天又是星期幾？7求n=1357xx的末三位數(shù)字8證明不定方程x2+y2-8z=6無整數(shù)解