例談運(yùn)用同余解題的取模技巧

邢忠虎

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

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

例1 求32008除以13的余數(shù).

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

故32008除以13的余數(shù)為3.

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

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

求個位數(shù)與末兩位數(shù)的問題，其實(shí)質(zhì)也就是求一數(shù)被10或100除所得余數(shù).

例2 求4735+5281×27924的末位數(shù)字.

解：∵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的末位數(shù)字是5.

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

例3 求3406的末兩位數(shù).

解：因?yàn)?4≡61(玬od100),916≡41(玬od100),920≡1(玬od100),9203≡920×10+3≡93≡29(玬od100).所以3406的末兩位數(shù)是29.

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

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

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

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

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

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

4 與奇偶性有關(guān)的問題，常以2為模

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

例6 設(shè)a1,a2,…,a64①是自然數(shù)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獆④,……這樣一直作下去，最后得到一個整數(shù)x，求證：x為偶數(shù).

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

5 與數(shù)字和有關(guān)的問題，常以9為模

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

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

解：先對Q值的范圍進(jìn)行估計：由44444444<100004444,100004444共有4×4444+1=17777位數(shù)，得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.