同余的概念与应用
概念与性质
1. 定义：若整数a,b 被整数m(m≥1)除的余数相同,则称a 同余于b 模m,或a,b 对模m 同余.记为a≡b(modm).余数r:0≤r<1.
2. 性质：(ⅰ)a≡b(modm)⇔m|a-b,即a=b+mk,k ∈Z.
(ⅱ)若a≡b(modm),b≡c(modm),则a≡c(modm).
(ⅲ)若a 1≡b 1(modm),a 2≡b 2(modm)，则a 1±a 2≡b 1±b 2(modm),a 1a 2≡b 1b 2(modm);
(ⅳ)设f(x)=a n x n +a n-1x n-1+…+a 1x+a 0,g(x)=b n x n +b n-1x n-1+…+b 1x+b 0是两个整系数多项式,满足a i ≡ b i (modm)(0≤i≤n).若a≡b(modm),则f(a)≡f(b)(modm).(ⅴ)ac≡bc(modm)⇔a≡b(mod )
,(m c m ), (ⅵ)若m≥1,(a,m)=1,则存在整数c 使得ac≡1(modm).称c 为a 对模m 的逆或倒数,记为c=a -1(modm);
(ⅶ)⎩⎨⎧≡≡)
(mod )(mod 21m b a m b a 同时成立⇔≡a b (mod[m 1,m 2]);(ⅷ)若a≡b(modm 1),a≡b(modm 2),且(m 1,m 2)= 1,则a≡b(modm 1m 2).
3. 剩余类：设m 为正整数，把全体整数按对模m 的余数分成m 类，相应m 个集合记为：K 0,K 1,…,K m-1,其中K r ={qm+r|q ∈Z,0≤余数r≤m -1}称为模m 的一个剩余类。
性质：(ⅰ)i m i K Z 10-≤≤= 且K i ∩K j =φ(i≠j).
(ⅱ)每一整数仅在K 0,K 1,…,K m-1一个里.
(ⅲ)对任意a 、b ∈Z ，则a 、b ∈K r ⇔a≡b(modm).
4. 完全剩余系：设K 0,K 1,…,K m-1为模m 的全部剩余类，从每个K r 里任取一个a r ，得m 个数a 0,a 1,…,a m-1组成的数组，叫做模m 的一个完全剩余系。0,1,2,…,m-1叫做模m 的最小非负完全剩余系。
性质：(ⅰ)m 个整数构成模m 的一完全剩余系⇔两两对模m 不同余。
(ⅱ)若(a,m)=1，则x 与ax+b 同时跑遍模m 的完全剩余系。
5. 既约剩余系：如果K r 里的每一个数都与m 互质，则K r 叫与m 互质的剩余类，在与模m 互质的全部剩余类中，从每一类任取一个数所做成的数组，叫做模m 的一个既约剩余系。
性质：(ⅰ)K r 与模m 互质⇔K r 中有一个数与m 互质；
(ⅱ)与模m 互质的剩余类的个数等于)m (ϕ;
(ⅲ)若(a,m)=1,则x 与ax+b 同时跑遍模m 的既约剩余系。
(ⅳ)设(a,p)=1,则d 0是a 对于模p 的阶⇔a d o≡1(modp),且1,a,…,a do-1对模p 两两不同余.特别地,d o = Φ(p)⇔1,a,…,a Φ(p)-1构成模p 的一个既约剩余系.
例1. 设x i ∈{-1,1},i=1,2,…,101,证明:x 1+2x 2+…+100x 101≠0.
证明:∵x 1+2x 2+…+100x 101≡1+2+…+101≡51≡1(mod2)∴成立.
例2. 设p 为质数.求证:)(mod p p n C p n ⎥⎦
⎤⎢⎣⎡≡. 证明:∵n≡0,1,2,…,p -1(modp)∴必有某一个i(0≤i≤p -1)使得n≡i(modp),从而p i n p n -=⎥⎦
⎤⎢⎣⎡.∴n(n- 1)…(n -i+1)(n-i-1)…(n -p+1)≡i(i -1)…1(p -1)…(i+1)≡(p -1)!(modp)，∴(p-1)!p
n C =(p-1)!n(n-1)…(n -i+1)(n-i-
1)…(n -p+1)!
p i n -≡(p -1)!p i n -(modp),即(p-1)!p n C ≡(p -1)!p i n -(modp),因((p-1)!,p)=1∴(mod p p n p i n C p n ⎥⎦⎤⎢⎣⎡≡-≡ )(mod p p n p i n p n
⎥⎦⎤⎢⎣⎡≡-≡. 例3. 设m>0,证明必有一个仅由0或1构成的自然数a 是m 的倍数.
证明：考虑数字全为1的数:1,11,111,1111,…中必有两个在modm 的同一剩余类中,它们的差即为所求的a.
例4. 证明从任意m 个整数a 1,a 2,…,a m 中,必可选出若干个数,它们的和(包括只一个加数)能被m 整除. 证明：考虑m 个数a 1,a 1+a 2,a 1+a 2+a 3,…,a 1+a 2+…+a m ,如果其中有一个数能被m 整除,则结论成立,否则,必有两个数属于modm 的同一剩余类,这两个数的差即满足要求.
例5. 证明数11,111,1111,…中无平方数.
证明：因任意整数n 2≡0或1(mod4),而11≡111≡1111≡…≡3(mod4),所以,数11,111,1111,…中无平方数. 例6. 确定n 5=1335+1105+845+275.
解：因n 5≡35+05+45+75≡3+4+7≡4(mod10),所以n 个位数字为4,显然n 的首位数字为1,进一步估
计:n 5<2×1335+(84+27)5<3×1335<55
13345⨯⎪⎭
⎫ ⎝⎛,所以,n<13345⨯<167,所以n 可取134,144,154,164,又n 5≡15+(-1)5≡3(mod3),故n=144.
注：欧拉猜测4个自然数的5次方之和不是5次方,于1962年被三位美国数学家推翻,例6就是他们举的反例.
例7. 求32006的个位数及末两位数字.
解：(1)即求a(0≤a≤9),使得32006≡a(mod10).∵32≡9≡-1(mod10),∴34≡1(mod10),32006≡32004+2≡34X501+2≡ 32(mod10),故32006的个位数是9;(2)即求b(0≤b≤99),使得32006≡b(mod100).注意到:4 X25=100且(4,25)=1,34≡81≡1(mod5),∵34≡81≡6(mod25),38≡36≡11(mod25),∴312≡66≡-9(mod25),316≡-54≡-4(mod2
5)∴320≡-24≡1(mod25) ①;∵32≡1(mod4)∴320≡1(mod4) ②,由①,②得320≡1(mod100),∴32006≡ 320 X100•36≡29(mod100),故32006的末两位数字是29.
例8. 求1 X3 X5 X 7 X…X2005的末3位数字.
解：注意到:8X125=1000且(8,125)=1，∵(2n-3)(2n-1)(2n+1)(2n+3)≡(4n 2-9)(4n 2-1)≡1(mod8)，及M= 1 X3 X5 X 7 X…X2005=125m 是1003个奇数之积，∴M≡1 X3 X5≡7(mod8), 125m≡5m≡7(mod8)，∴m≡ 3(mod8)，∴M≡125m≡125X3≡375(mod8)，∴M≡125m≡375(mod8).即1 X3 X5 X 7 X…X2005的末3位数字为375.
例9. 求大于5的素数平方被30除的余数.
解：设p 是大于5的素数,且p≡r(mod30)(r<30)，∵(p,30)=1∴(r,30)=1,r=1,7,11,13,17,19,23,29，∵12≡ 112≡192≡292≡1(mod30), 72≡132≡172≡232≡19(mod30)，∴p 2≡1或19(mod30)
例10. 设n,k 为正整数,求证:存在无限多个形如n•2k -7的平方数.
解：即求使得m 2+7≡0(mod2k )成立的整数m.当k=1,2,3时,取m=1+4r(r 为正奇数),则有m 2+7≡0(mod2k ).设对k(≥3)有整数m 使得m 2+7≡0(mod2k ),显然m 为奇数,对于k+1，∵(m+a•2k-1)2+7≡m 2+7+ma•2k ≡
2k (am+b)(mod2k+1),其中b=k m 272+∈Z +,取正整数a,b 同奇偶,则有(m+a•2k-1)2+7≡0(mod2k+1)，∴对任意正整数k 存在无限多个整数m 使得m 2+7≡0(mod2k ).
例11. 设对任意正整数n≥1,b 的质因数都大于n.证明：n!|a(a+b)(a+2b)(a+3b)…[a+(n -1)b]
证明：∵b 的质因数都大于n ，∴(b,n!)=1∴bb -1≡1(modn!)，∴(b -1)n a(a+b)(a+2b)(a+3b)…[a+(n -1)b]≡ (ab -1)(ab -1+1)(ab -1+2)(ab -1+3)…[ab -1+(n-1)]≡0(modn!)，∵(b -1,n!)=1，∴n!|a(a+b)(a+2b)(a+3b)…[a+(n -1)b]
