奧數(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的話，那么后走者乙勝在這個游戲里，我們可以看出，有時我們不必去關(guān)心一個數(shù)是多少，而要關(guān)心這個數(shù)用m

2、除后的余數(shù)是什么又例如，1999年元旦是星期五，1999年有365天，365=7521，所以2000年的元旦是星期六這里我們關(guān)心的也是余數(shù)這一講中，我們將介紹同余的概念、性質(zhì)及一些簡單的應用同余，顧名思義，就是余數(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ù)等式有一些相同的性質(zhì)，最簡單的就是下面的定理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)，即acbd(modm

4、)，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(modm2)，ab

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

6、，所以=(194)250(-1)2501(mod 17)，于是17(-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-803n-464n261n能被1897整除證 1897=7271，7與271互質(zhì)因為

7、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，b2，b64，計算b1-b2，b3-b4，b63-b64如此繼續(xù)下去，最后得到一個數(shù)x，

8、問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ù)字就是求這個數(shù)除以100的余數(shù)例5 求證：一個十進制數(shù)被9除的余數(shù)等于它的各位數(shù)字之和被9除

9、的余數(shù)101(mod 9)，故對任何整數(shù)k1，有10k1k1(mod 9)因此即A被9除的余數(shù)等于它的各位數(shù)字之和被9除的余數(shù)說明 (1)特別地，一個數(shù)能被9整除的充要條件是它的各位數(shù)字之和能被9整除(2)算術(shù)中的“棄九驗算法”就是依據(jù)本題的結(jié)論例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ù)2=4k24k+1=4k(k1)+1因為兩個連續(xù)整數(shù)k，k1中必有偶數(shù)，所以4k(k1

10、)是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除21998的余數(shù)(2)求8除72n+1-1的余數(shù)解 (1)先找與1(mod 33)同余的數(shù)因為2532-1(mod 33)，所以 2101(mod 33)，21998=(210)1992523-825(mod 33)，所求余數(shù)為25(2)因為7-1(mod 8)，

11、所以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ù)證明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ù)解說明 同余是處理不定方程的基本方法，但這種方法也非常靈活，關(guān)鍵在于確定所取的模(本例我們?nèi)∧?)，這往往應根據(jù)問題的特點來確定練習二十五1求證：17(-1)2證明：對所有自然數(shù)n，330(62n-52n-11)4求