例谈运用同余解题的取模技巧

邢忠虎

由德国数学家高斯引进的同余概念是研究数论问题的一个十分重要的工具.运用同余解题，可以避免繁琐的计算，抓住问题的实质和要害，而运用同余解题其关键则在选取恰当的模.本文通过若干例题介绍几种基本的取模技巧，供参考.

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.