初中數學競賽專題培訓第二十五講* 同余式
數論有它自己的代數，稱為同餘理論．最先引進同餘的概念與記號的是數學王子高斯．
先看乙個遊戲：有n＋1個空格排成一行，第一格中放入一枚棋子，甲乙兩人交替移動棋子，每步可前移1，2或3格，以先到最後一格者為勝．問是先走者勝還是後走者勝？應該怎樣走才能取勝？
取勝之道是：你只要設法使餘下的空格數是4的倍數，以後你的對手若走i格(i=1，2，3)，你走4-i格，即每一次交替，共走了4格．最後只剩4個空格時，你的對手就必輸無疑了．因此，若n除以4的餘數是1，2或3時，那麼先走者甲勝；若n除以4的餘數是0的話，那麼後走者乙勝．
在這個遊戲裡，我們可以看出，有時我們不必去關心乙個數是多少，而要關心這個數用m除后的餘數是什麼．又例如，2023年元旦是星期五，2023年有365天，365=7×52＋1，所以2023年的元旦是星期六．這裡我們關心的也是餘數．這一講中，我們將介紹同餘的概念、性質及一些簡單的應用．
同餘，顧名思義，就是餘數相同．
定義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．
反之，若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(modm)．
在代數中，等式可以相加、相減和相乘，同樣的規則對同余式也成立．
定理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，得到乙個正確的同余式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，…，mn的最小公倍數，則
a≡b(modm)．
前面介紹了同余式的一些基本內容，下面運用同餘這一工具去解決一些具體問題．
應用同余式的性質可以簡捷地處理一些整除問題．若要證明m整除a，只需證a≡0(modm)即可．
例1 求證：
(1)8｜(551999＋17)；
(2) 8(32n＋7)；
(3)17｜(191000-1)．
證 (1)因55≡-1(mod 8)，所以551999≡-1(mod 8)，551999＋17≡-1＋17=16≡0(mod 8)，於是8｜(551999＋17)．
(2)32=9≡1(mod 8)，32n≡1(mod 8)，所以32n＋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)；
(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．又因為
2903≡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是奇數還是偶數？
解因為對於乙個整數a，有
｜a｜≡a(mod 2)， a≡-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的餘數，求乙個數的末兩位數字就是求這個數除以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≡0(mod 4)，
所以例7 任意平方數除以8餘數為0，1，4(這是平方數的又一重要特徵)．
證奇數可以表示為2k＋1，從而
奇數2=4k2＋4k+1=4k(k＋1)+1．
因為兩個連續整數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)，
所以求餘數是同餘的基本問題．在這種問題中，先求出與±1同餘的數是一種基本的解題技巧．
例8 (1)求33除21998的餘數．
(2)求8除72n+1-1的餘數．
解 (1)先找與±1(mod 33)同餘的數．因為
25＝32≡-1(mod 33)，
所以 210≡1(mod 33)，
21998=(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，…
的數稱為費馬數．證明：當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
沒有整數解．
證對於任一整數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)，這往往應根據問題的特點來確定．
競賽培訓專題4 同余式與不定方程
同余式和不定方程是數論中古老而富有魅力的內容.考慮數學競賽的需要,下面介紹有關的基本內容.1.同余式及其應用 定義 設a b m為整數 m 0 若a和b被m除得的餘數相同，則稱a和b對模m同餘.記為或 一切整數n可以按照某個自然數m作為除數的餘數進行分類，即n pm r r 0，1，m 1 恰好m個...
競賽培訓專題4同余式與不定方程
同余式和不定方程是數論中古老而富有魅力的內容.考慮數學競賽的需要,下面介紹有關的基本內容.1.同余式及其應用 定義 設a b m為整數 m 0 若a和b被m除得的餘數相同，則稱a和b對模m同餘.記為或 一切整數n可以按照某個自然數m作為除數的餘數進行分類，即n pm r r 0，1，m 1 恰好m個...
初中數學競賽專題培訓
數學事業部 第一講 因式分解 一1 第二講 因式分解 二4 第三講實數的若干性質和應用7 第四講分式的化簡與求值10 第五講恒等式的證明13 第六講代數式的求值16 第七講根式及其運算19 第八講非負數23 第九講一元二次方程26 第十七講 集合與簡易邏輯52 第十八講歸納與發現57 第十九講特殊化...