用同余理论解决整除问题重庆沙坪坝杨公桥小学 蒋焘摘 要：在数的整除理论中，经常要判断一个数能否被另一个数整除。

虽然用初等方法也能证明判断的正确性，但其技巧性很强,而技巧性的东西是一时难于捕捉到的。

如果用同余理论解决这类问题，就简捷明了。

本文主要利用同余性质给出一些整除问题的判别方法并阐述同余理论在整除问题中的一些应用。

关键词：同余;整除;判别方法1 同余的基本概念和性质整除性的证明被公认为是中学数学、特别是数学竞赛的难题之一，但用同余思想方法指导解决整除性问题就要容易和易于掌握得多。

本文主要阐述同余理论在整除问题中的一些应用。

定义1.１ 设a,b 是任意两个整数，其中b ≠0，如果存在一个整数q 使得等式a ＝bq 成立，我们就说b 能整除a 或a 能被b 整除，记作b|a ，否则记作b a 。

定义1.２ 给定一个正整数m ，把它叫做模。

如果用ｍ去除任意两个整数a 和b 所得的余数相同，我们就说a ，b 对模ｍ同余，记做()mod a b m ≡。

如果余数不相同，我们就说a ，b 对模ｍ不同余，记做a ()mod b m 。

定理1.1 ()mod a b m ≡的充分必要条件是|m a b -。

性质1.1 ()mod a a m ≡。

性质1.2 若()mod a b m ≡，则()mod b a m ≡。

性质1.3 若()mod a b m ≡，()mod b c m ≡，则()mod a c m ≡。

性质1.4 若()11mod a b m ≡，()22mod a b m ≡，则1a ±2a 1b ≡±2b ()mod m 。

若(mod )a b c m +≡，则(mod )a c b m ≡-。

性质1.5 若()11mod a b m ≡，()22mod a b m ≡，则()1212mod a a bb m ≡，()11mod a c b c m ≡，c 为任意整数。

性质1.6 若()mod a b m ≡，且11,,(,)1a a d b b d d m ===，则11(mod )a b m ≡。

性质1.7 若()mod a b m ≡，k o >，则()mod ak bk mk ≡。

若()mod a b m ≡，d 为a,b 及m 的任一正公因数，则(mod )a b md d d≡。

性质1.8 同余式组()mod i a b m ≡，i=1,2,,k,同时成立的充要条件是[]()12mod ,,,k a b m m m ≡。

性质1.9 若()mod a b m ≡，,0d m d >，则()mod a b d ≡。

定理1.2[3] 设()110n n n n f x a x a x a --=+++是整系数多项式，若()mod m αβ≡，则()()()mod f f m αβ≡。

定理1.3[1]（Euler ） 设m 是大于1的整数，(),1a m =,则()()1mod m a m ϕ≡。

定理1.4[4] 若m ()11≥=，ａ,ｍ,则存在c Z ∈,使()1mod ca m ≡，我们称c 是a 对模m 的逆，记作1a -。

2 利用同余性质给出一些整除的判别法例２.１ 任何一个整数110n n a a a a a -=，其中010,0i n a a ≤<≠，0,1,2,,.i n = 则025|a 25|a ⇔、、证法一 设11010n n a a a a a -=⨯+∵2|1110n n a a a -⨯∴2|11010n n a a a a -⨯+⇔2|0a故02|a 2|a ⇔同理可证0|5|5a a ⇔。

证法二 设()110n n n n f x a x a x a --=+++是整系数多项式。

∵()100mod2≡∴由定理1.2得()()()100mod2f f ≡ 即a ≡0a ()mod2 则02|a 2|a ⇔对模m=5的情形同理论证。

例2．2 1210n n a a a a a a -=，其中010,0i n a a ≤<≠，0,1,2,,.i n = 则10425|a 425|a a ⇔、、证明 ∵1210100n n a a a a a a -=⨯+又∵()1000mod4≡ ∴()12121000mod4n n n n a a a a a a --⨯≡⨯于是()10mod4a a a ≡ 故104|4|a a a ⇔对模m=25的情形同理论证。

例２.3 1210n n a a a a a a -=，其中010,0i n a a ≤<≠，0,1,2,,.i n =则2108125|8125|a a a a ⇔、、证明 ∵132101000n n a a a a a a a -=⨯+又∵ ()10000mod8≡ ∴()131310000mod8n n n n a a a a a a --⨯≡⨯于是()210mod8a a a a ≡ 故2108|8|a a a a ⇔对模m=125的情形同理论证。

例2.4 任何一个整数110n n a a a a a -=，其中010,0i n a a ≤<≠，则039|39|ni i a a =⇔∑、、证法一 ∵110n n a a a a a -=1110101010n n n n a a a a --=⨯+⨯++⨯+()()()1110919191nn n n a a a a --=⨯++⨯+++⨯++()()()1110919191n n n n a q a q a a --=⨯++⨯+++⨯++1109n n q a a a a -=+++++09ni i q a ==+∑∴03|3|n i i a a =⇔∑同理可证∑=⇔ni i a a 0|9|9。

证法二 设()110nn n n f x a x a xa --=+++是整系数多项式。

∵101(mod3)≡∴由定理1.2得()()()101mod3f f ≡ 又()10f a = ()01ni i f a ==∑所以0(mod3)n i i a a =≡∑即03|3|ni i a a =⇔∑同理可证∑=⇔ni i a a 0|9|9。

例2.5 任何一个整数110n n a a a a a -=，其中010,0i n a a ≤<≠，则11|11|(1)ni i i a a =⇔-∑证明 ∵各位数字都是9的偶数位整数都能被11整除，且形如10001 的偶数位整数也能被11整除。

∴若记整数110n n a a a a a -=为111110[10(1)(1)][10(1)(1)][10(1)(1)]n n n n n n n n a a a a a ----=⨯--+-+⨯--+-++⨯--+-+11110[10(1)][10(1)][10(1)](1)n n n n n i n n i i a a a a ---==⨯--+⨯--++⨯--+-∑前n 项中的每一项都有偶数位因数999或100…01，都能被11整除。

因此，若0(1)nii i a =-∑能被11整除，a 就能被11整除；若11|a ，则11|()∑=-ni i ia 01。

例2.6 正整数1110100010001000nn n n a a a a a --=⨯+⨯++⨯+01000,0,0,1,2,,.i n a a i n ≤<≠=则011713|11713|(1)ni i i a a =⇔-∑、、、、证明 设()110nn n n f x a x a x a --=+++是整系数多项式。

∵10001(mod11)≡-∴由定理1.2得()()()10001mod11f f ≡- 又()1000f a = ()()011nii i f a =-=-∑ 所以()()01mod11n i i i a a =≡-∑故()11|11|1nii i a a =⇔-∑对模m=7、13的情形同理论证。

例２.7 []2 1110100010001000n n n n a a a a a --=⨯+⨯++⨯+01000,0,0,1,2,,.i n a a i n ≤<≠=则037|37|n i i a a =⇔∑证明 设()1110n n n n f x a x a x a x a --=+++是整系数多项式。

∵10001(mod37)≡∴由定理1.2得()()()10001mod37f f ≡ 即100(mod37)nn n i i a a a a a -=≡+++=∑故037|37|nii a a=⇔∑例２.８ 设正整数1110100100100n n n n a a a a a --=⨯+⨯++⨯+0100,0,0,1,2,,.i n a a i n ≤<≠=则()∑=-⇔ni i ia a 01|101|101证明 设()1110n n n n f x a x a x a x a --=+++是整系数多项式。

∵1001(mod101)≡-∴由定理1.2得()()()1001mod101f f ≡- 即()()101mod 10∑=-≡ni i ia a故101|a ()∑=-⇔ni iia1|101３ 同余理论在整除问题中的应用例3.1 n 为非负整数,证明n+22157|78n ++证法一 当n=0时，n+22178n ++=49+8=57 ∴n+22157|78n ++当n ＞0时，∵ n+22178n ++n n =497+864⨯⨯nnnn=497+87-87+864⨯⨯⨯⨯ nnn=577+8(64-7)⨯ nn-1n-21=577+8(64-7)(64+647+7n -⨯⨯+nn-1n-2n-1=57[7+8(64+647++7)]⨯∴ n+22n+157|7+8评注 本题的解法之技巧在于加上一项再减去一项,若没有想到此法,则难于得到证明。

证法二 用同余思想方法证明当n=0时，结论显然成立。

当n ＞0时，∵64≡7（mod57） ∴n 64≡n 7（mod57） 于是n+22n+17+8 =497648n n ⋅+⋅()7498n ≡+ ()0mod57≡ 故n+22n+157|7+8例3.2[]8 试证 7|55552222+22225555证法一 ∵2222=7×317+3 ，5555=7×793+4 而55552222+55554 =（2222+4）M =7×318M,M ∈Z 22225555－22224 = (5555－4)N =7×793N ，N ∈Z 于是55552222+22225555=（55552222+55554）+（22225555－22224）－55554+22224 =7×（318M+793N ）－22224（33334－1）而22224（33334－1）=22224()1111341⎡⎤-⎢⎥⎣⎦=22224（34－1）L =63×22224L =7×9p;L,p ∈Z∴55552222+22225555=7(318M+793N+9p) 故7|(55552222+22225555)评注 证法一的技巧性非常强，用加55554，22224再减去55554，22224，再用因式分解公式()()12321n n n n n n a b a b a a b a b b ----+=+-+-+；n 是奇数 ()()12321n n n n n n a b a b a a b a b b -----=-++++；n 是正整数证法二 用同余思想方法证明 ∵22223(mod7),(3,7)1,≡= ∴()(7)31(mod7),76φφ≡= 从而631(mod7)≡55554(m o d 7)≡= ∴(7)6441(mod7)φ=≡于是55552222555522222222555534+≡+692556370252(3)3(4)4340(mod7)=⨯+⨯≡+≡故555522227|(22225555)+例３.３[]7 当n 为正整数时，证明330能整除226511n n -- 证明 因3305611=⨯⨯()()2261mod5611mod5n n ≡⇒≡= ()()250mod550mod5n ≡⇒≡ ()111mod5≡故()2265111010mod5n n --≡--≡ 又因()()260mod660mod6n ≡⇒≡()()()2251mod 6511mod 6nn ≡-⇒≡-≡()111mod6≡-故()()2265110110mod6n n --≡---≡ 又因()()()266mod116363mod11nn n ≡⇒≡=()()255mod115253mod11n n n ≡⇒≡≡ ()110mod11≡故()2265113300mod11n n n n --≡--≡ 由性质1.7得()2265110mod5611n n --≡⨯⨯故330|()226511n n --。