资源描述：
《高中数学竞赛专题讲座---专题训练-(同余部分的例题与习题).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、同余的概念与应用概念与性质1.定义：若整数a,b被整数m(m≥1)除的余数相同,则称a同余于b模m,或a,b对模m同余.记为a≡b(modm).余数r:0≤r<1.2.性质：(ⅰ)a≡b(modm)m
2、a-b,即a=b+mk,k∈Z.(ⅱ)若a≡b(modm),b≡c(modm),则a≡c(modm).(ⅲ)若a1≡b1(modm),a2≡b2(modm)，则a1±a2≡b1±b2(modm),a1a2≡b1b2(modm);(ⅳ)设f(x)=anxn+an-1xn-1+…+a1x+a0,g(x)=bnxn+bn-1xn-1+…+b1x+
3、b0是两个整系数多项式,满足ai≡bi(modm)(0≤i≤n).若a≡b(modm),则f(a)≡f(b)(modm).(ⅴ)ac≡bc(modm)a≡b(mod),(ⅵ)若m≥1,(a,m)=1,则存在整数c使得ac≡1(modm).称c为a对模m的逆或倒数,记为c=a-1(modm);(ⅶ)同时成立(mod[m1,m2]);(ⅷ)若a≡b(modm1),a≡b(modm2),且(m1,m2)=1,则a≡b(modm1m2).3.剩余类：设m为正整数，把全体整数按对模m的余数分成m类，相应m个集合记为：K0,K1,…,Km-1,其中K
4、r={qm+r
5、q∈Z,0≤余数r≤m-1}称为模m的一个剩余类。性质：(ⅰ)且Ki∩Kj=φ(i≠j).(ⅱ)每一整数仅在K0,K1,…,Km-1一个里.(ⅲ)对任意a、b∈Z，则a、b∈Kra≡b(modm).4.完全剩余系：设K0,K1,…,Km-1为模m的全部剩余类，从每个Kr里任取一个ar，得m个数a0,a1,…,am-1组成的数组，叫做模m的一个完全剩余系。0,1,2,…,m-1叫做模m的最小非负完全剩余系。性质：(ⅰ)m个整数构成模m的一完全剩余系两两对模m不同余。(ⅱ)若(a,m)=1，则x与ax+b同时跑遍模m的完全剩余
6、系。5.既约剩余系：如果Kr里的每一个数都与m互质，则Kr叫与m互质的剩余类，在与模m互质的全部剩余类中，从每一类任取一个数所做成的数组，叫做模m的一个既约剩余系。性质：(ⅰ)Kr与模m互质Kr中有一个数与m互质；(ⅱ)与模m互质的剩余类的个数等于;(ⅲ)若(a,m)=1,则x与ax+b同时跑遍模m的既约剩余系。(ⅳ)设(a,p)=1,则d0是a对于模p的阶ado≡1(modp),且1,a,…,ado-1对模p两两不同余.特别地,do=Φ(p)1,a,…,aΦ(p)-1构成模p的一个既约剩余系.例1.设xi∈{-1,1},i=1,2,…,
7、101,证明:x1+2x2+…+100x101≠0.证明:∵x1+2x2+…+100x101≡1+2+…+101≡51≡1(mod2)∴成立.例2.设p为质数.求证:.证明:∵n≡0,1,2,…,p-1(modp)∴必有某一个i(0≤i≤p-1)使得n≡i(modp),从而.∴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-1)!n(n-1)…(n-i+1)(n-i-1)…(n-p+1)≡(p-1)!(modp),即(p-1)!≡(p-1)
8、!(modp),因((p-1)!,p)=1∴.例3.设m>0,证明必有一个仅由0或1构成的自然数a是m的倍数.证明：考虑数字全为1的数:1,11,111,1111,…中必有两个在modm的同一剩余类中,它们的差即为所求的a.例4.证明从任意m个整数a1,a2,…,am中,必可选出若干个数,它们的和(包括只一个加数)能被m整除.证明：考虑m个数a1,a1+a2,a1+a2+a3,…,a1+a2+…+am,如果其中有一个数能被m整除,则结论成立,否则,必有两个数属于modm的同一剩余类,这两个数的差即满足要求.例5.证明数11,111,111
9、1,…中无平方数.证明：因任意整数n2≡0或1(mod4),而11≡111≡1111≡…≡3(mod4),所以,数11,111,1111,…中无平方数.例6.确定n5=1335+1105+845+275.解：因n5≡35+05+45+75≡3+4+7≡4(mod10),所以n个位数字为4,显然n的首位数字为1,进一步估计:n5<2×1335+(84+27)5<3×1335<,所以,n<<167,所以n可取134,144,154,164,又n5≡15+(-1)5≡3(mod3),故n=144.注：欧拉猜测4个自然数的5次方之和不是5次方,于
10、1962年被三位美国数学家推翻,例6就是他们举的反例.例7.求32006的个位数及末两位数字.解：(1)即求a(0≤a≤9),使得32006≡a(mod10).∵32≡9≡-1(mod10),
