例談運用同余解題的取模技巧

邢忠虎

由德國數學家高斯引進的同余概念是研究數論問題的一個十分重要的工具.運用同余解題，可以避免繁瑣的計算，抓住問題的實質和要害，而運用同余解題其關鍵則在選取恰當的模.本文通過若干例題介紹幾種基本的取模技巧，供參考.

1 求余數或證明整除性問題，常以除數為模

例1 求32008除以13的余數.

解：∵33=27≡1(玬od13),∴32008=33×669+1=(33)669×3≡1669×3≡3(玬od13).

故32008除以13的余數為3.

注：求余數是同余的基本問題，在這種問題中，先求出與±1同余的數是一種基本技巧.這一技巧在后面的例3與例7中將再次得到運用.

2 求個位數(末兩位數)問題，常以10(100)為模

求個位數與末兩位數的問題，其實質也就是求一數被10或100除所得余數.

例2 求4735+5281×27924的末位數字.

解：∵4735+5281×27924≡735+281×924≡74×8+3+24×20+1×94×5+4≡73+21×94≡3+2×1=5(玬od10).

∴4735+5281×27924的末位數字是5.

注：在求解本題的過程中用到了以下結論：任何正整數的乘方之個位數重復出現的周期為4，即a4k+l=al(玬od10)，其中a是任意正整數，k為自然數，l=1,2,3,4.請讀者自行證明此結論.

例3 求3406的末兩位數.

解：因為94≡61(玬od100),916≡41(玬od100),920≡1(玬od100),9203≡920×10+3≡93≡29(玬od100).所以3406的末兩位數是29.

3 與平方數有關的問題，常以4(或8)為模

偶數的平方是4的倍數，即(2k)2=4(玬od4)，而奇數的平方除以8(4)余1，即有(2k+1)2=4k(k+1)+1≡1(玬od8)和(2k+1)2≡1(玬od4).

例4 證明11，111，1111，…中沒有平方數.

證明：平方數關于模4同余于0或1，換句話說，關于模4同余于2或3的數一定不是平方數.而111…1≡11≡3(玬od4)，故11，111，1111，…中沒有平方數.

例5 能否找到自然數a和b，使a2=2006+b2?

解：不能.設b為自然數，由2006≡2(玬od4),b2≡0(玬od4)或b2≡1(玬od4)，知2006+b2≡2(玬od4)或2006+b2≡2+1≡3(玬od4).這說明2006+b2不是平方數，故找不到自然數a和b，使a2=2006+b2.

4 與奇偶性有關的問題，常以2為模

一個整數與它的相反數以及絕對值奇偶性都相同，兩整數的和與差奇偶性相同，若用同余的語言可敘述如下：-a≡a(玬od2),|a|=a(玬od2),a+b≡a-b(玬od2).

例6 設a1,a2,…,a64①是自然數1，2，…，64的任意一種排列.令b1=|a1-a2|,b2=|a3-a4|,…,b32=|a63-a64獆②，c1=|b1-b2|,c2=|b3-b4|,…,c16=|b31-b32獆③,d1=|c1-c2|,d2=|c3-c4|,…,d8=|c15-c16獆④,……這樣一直作下去，最后得到一個整數x，求證：x為偶數.

證明：因為b1+b2+…+b32=|a1-a2|+|a3-a4|+…+|a63-a64獆≡(a1-a2)+(a3-a4)+…+(a63-a64)≡(a1+a2)+(a3+a4)+…+(a63+a64)(玬od2)，所以經過一步“運算”，①變成②，但和的奇偶性未發生變化.同樣，經多步“運算”依然如此，故x≡a1+a2+a3+a4+…+a63+a64(玬od2)，即x≡1+2+3…+64≡0(玬od2)，x為偶數.

5 與數字和有關的問題，常以9為模

若設十進制正整數N=anan-1…a1a0，則N=anan-1…a1a0=an×10n+an-1×10n-1+…+a1×10+a0≡an+an-1+…+a1+a0(玬od9),即一個十進制正整數與它的各位數字之和關于模9同余.

例7 44444444寫成一個多位數后，它的各位數字之和為M，M的各位數字之和為P，P的各位數字之和為Q，求Q.

解：先對Q值的范圍進行估計：由44444444<100004444,100004444共有4×4444+1=17777位數，得M<9×17777=159993，因此P≤1+5×9=46，從而Q≤4+9=13.又Q≡P≡M≡44444444≡74444≡73×1481+1=(73)1481×7=(343)1481×7≡11481×7≡7(玬od9)，故Q=7.