高中数学竞赛讲座---专题训练_(同余部分的例题与习题)

同余的概念与应用概念与性质1.定义：若整数a,b被整数m(m≥1)除的余数相同,则称a同余于b模m,或a,b对模m同余.记为a≡b(modm).余数r:0≤r1.2.性质：(ⅰ)a≡b(modm)m|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+b0是两个整系数多项式,满足ai≡bi(modm)(0≤i≤n).若a≡b(modm),则f(a)≡f(b)(modm).(ⅴ)ac≡bc(modm)a≡b(mod),(mcm),(ⅵ)若m≥1,(a,m)=1,则存在整数c使得ac≡1(modm).称c为a对模m的逆或倒数,记为c=a-1(modm);(ⅶ))(mod)(mod21mbamba同时成立ab(mod[m1,m2]);(ⅷ)若a≡b(modm1),a≡b(modm2),且(m1,m2)=1,则a≡b(modm1m2).3.剩余类：设m为正整数，把全体整数按对模m的余数分成m类，相应m个集合记为：K0,K1,…,Km-1,其中Kr={qm+r|q∈Z,0≤余数r≤m-1}称为模m的一个剩余类。性质：(ⅰ)imiKZ10且Ki∩Kj=φ(i≠j).(ⅱ)每一整数仅在K0,K1,…,Km-1一个里.(ⅲ)对任意a、b∈Z，则a、b∈Kra≡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的完全剩余系。5.既约剩余系：如果Kr里的每一个数都与m互质，则Kr叫与m互质的剩余类，在与模m互质的全部剩余类中，从每一类任取一个数所做成的数组，叫做模m的一个既约剩余系。性质：(ⅰ)Kr与模m互质Kr中有一个数与m互质；(ⅱ)与模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,…,101,证明:x1+2x2+…+100x101≠0.证明:∵x1+2x2+…+100x101≡1+2+…+101≡51≡1(mod2)∴成立.例2.设p为质数.求证:)(modppnCpn.证明:∵n≡0,1,2,…,p-1(modp)∴必有某一个i(0≤i≤p-1)使得n≡i(modp),从而pinpn.∴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)!pnC=(p-1)!n(n-1)…(n-i+1)(n-i-1)…(n-p+1)!pin≡(p-1)!pin(modp),即(p-1)!pnC≡(p-1)!pin(modp),因((p-1)!,p)=1∴)(modppnpinCpn)(modppnpinCpn.例3.设m0,证明必有一个仅由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,1111,…中无平方数.证明：因任意整数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,进一步估计:n52×1335+(84+27)53×13355513345,所以,n13345167,所以n可取134,144,154,164,又n5≡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).注意到:4X25=100且(4,25)=1,34≡81≡1(mod5),∵34≡81≡6(mod25),38≡36≡11(mod25),∴312≡66≡-9(mod25),316≡-54≡-4(mod25)∴320≡-24≡1(mod25)①;∵32≡1(mod4)∴320≡1(mod4)②,由①,②得320≡1(mod100),∴32006≡320X100•36≡29(mod100),故32006的末两位数字是29.例8.求1X3X5X7X…X2005的末3位数字.解：注意到:8X125=1000且(8,125)=1，∵(2n-3)(2n-1)(2n+1)(2n+3)≡(4n2-9)(4n2-1)≡1(mod8)，及M=1X3X5X7X…X2005=125m是1003个奇数之积，∴M≡1X3X5≡7(mod8),125m≡5m≡7(mod8)，∴m≡3(mod8)，∴M≡125m≡125X3≡375(mod8)，∴M≡125m≡375(mod8).即1X3X5X7X…X2005的末3位数字为375.例9.求大于5的素数平方被30除的余数.解：设p是大于5的素数,且p≡r(mod30)(r30)，∵(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)，∴p2≡1或19(mod30)例10.设n,k为正整数,求证:存在无限多个形如n•2k-7的平方数.解：即求使得m2+7≡0(mod2k)成立的整数m.当k=1,2,3时,取m=1+4r(r为正奇数),则有m2+7≡0(mod2k).设对k(≥3)有整数m使得m2+7≡0(mod2k),显然m为奇数,对于k+1，∵(m+a•2k-1)2+7≡m2+7+ma•2k≡2k(am+b)(mod2k+1),其中b=km272∈Z+,取正整数a,b同奇偶,则有(m+a•2k-1)2+7≡0(mod2k+1)，∴对任意正整数k存在无限多个整数m使得m2+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)na(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]例12.设mn≥1,求最小的m+n使得1000|1978m-1978n.解：令k=m-n,则1978m-1978n≡0(mod1000)2n•989n(1978k-1)≡0(mod23•53))5(mod0119783)2(mod0233knn，∵1978≡3(mod5)∴19784≡1(mod5)，∵1978≡3(mod25)∴197820≡320≡1(mod25)，∵1978≡-22(mod53),(-22)20≡(25-3)20≡320≡(243)4≡74≡(50-1)2≡26(mod53)∴197820≡26(mod53),∴197840≡(25+1)2≡51(mod53),197860≡(25+1)(50+1)≡76(mod53),197880≡(50+1)2≡101(mod53),1978100≡(25+1)(100+1)≡1(mod53),∴100|k∴k最小=100,m+n=m-n+2n最小=106.例13.设123,,,aaa是整数序列,其中有无穷多项为正整数,也有无穷多项为负整数.假设对每个正整数n,数123,,,,naaaa被n除的余数都各不相同.证明:在数列123,,,aaa中,每个整数都刚好出现一次.证明：数列各项同时减去一个整数不改变本题的条件和结论,故不妨设a1=0.此时对每个正整数k必有∣ak∣k:若∣ak∣≥k,取n=∣ak∣,则a1≡ak≡0(modn),矛盾.现在对k归纳证明a1,a2,…,ak适当重排后是绝对值小于k的k个相邻整数.k=1显然.设a1,a2,…,ak适当重排后为－(k－1－i),…,0,…,i(0≤i≤k－1),由于a1,a2,…,ak,ak+1是(modk+1)的一个完全剩余系,故必ak+1≡i+1(modk+1),但∣ak+1∣k+1,因此ak+1只能是i+1或－(k－i),从而a1,a2,…,ak,ak+1适当重排后是绝对值小于k+1的k+1个相邻整数.由此得到:1).任一整数在数列中最多出现一次;2).若整数u和v(uv)都出现在数列中,则u与v之间的所有整数也出现在数列中.最后由正负项均无穷多个（即数列含有任意大的正整数及任意小的负整数）就得到:每个整数在数列中出现且只出现一次.例14.偶数个人围着一张圆桌讨论，休息后，他们依不同次序重新围着圆桌坐下，证明至少有两个人，他们中间的人数在休息前与休息后是相等的。证明：将座号依顺时针次序记为1,2,…,2n，每个人休息前后的座号记为(i,j)，则i与j跑遍完全剩余系mod2n。如果两个人(i1,j1)，(i2,j2)休息前后在他们中间的人数不相等，则有j2-j1≡i2-i1mod2n，即j2-i2≡j1-i1(mod2n)，因此，j－i也跑遍完全剩余系mod2n∴j－i的和=ij≡0(mod2n)，而任一完全剩余系mod2n的和≡1+2+…+2n-1≡n(2n-1)≡0(mod2n),矛盾！故结论成立。例15.证明：不论n和k是怎样的正整数,2n3k+4nk+10不可能是连续正整数之积.证明：令p=nk,则2n3k+4nk+10=2p3+4p+10是偶数,取mod3,∵2p3+4p+10=(3p3+3p+9)-(p-1)p(p+1)+1∴2p3+4p+10≡1(mod3),从而2p3+4p+10不是3个或3个以上连续正整数之积,而两个连续正整数之积按mod3分类:3m(3m+1)≡0(mod3),(3m+1)(3m+2)≡2(mod3),(3m+3)(3m+2)≡0(mod3)∴原式也不是两个正整数之积.综上知:2n3k+4nk+10不可能是连续正整数之积.例16.设正整数a,b使得15a+16b和16a-15b都是正整数的平方，求这两个平方数所可能取的最小值(IMO37－4)。解：设15a+16b=x2和16a-15b=y2,