高中數(shù)學(xué)競賽專題講座---專題訓(xùn)練_(同余部分的例題與習(xí)題)

1、.同余的概念與應(yīng)用概念與性質(zhì) 1. 定義：若整數(shù)a,b被整數(shù)m(m1)除的余數(shù)相同,則稱a同余于b模m,或a,b對模m同余.記為ab(modm).余數(shù)r:0r0,證明必有一個僅由0或1構(gòu)成的自然數(shù)a是m的倍數(shù). 證明：考慮數(shù)字全為1的數(shù):1,11,111,1111,中必有兩個在modm的同一剩余類中,它們的差即為所求的a.例4. 證明從任意m個整數(shù)a1,a2,am中,必可選出若干個數(shù),它們的和(包括只一個加數(shù))能被m整除. 證明：考慮m個數(shù)a1,a1+a2,a1+a2+a3,a1+a2+am,如果其中有一個數(shù)能被m整除,則結(jié)論成立,否則,必有兩個數(shù)屬于modm的同一剩余類,這兩個數(shù)的差即滿足要

2、求.例5. 證明數(shù)11,111,1111,中無平方數(shù). 證明：因任意整數(shù)n20或1(mod4),而1111111113(mod4),所以,數(shù)11,111,1111,中無平方數(shù).例6. 確定n5=1335+1105+845+275. 解：因n535+05+45+753+4+74(mod10),所以n個位數(shù)字為4,顯然n的首位數(shù)字為1,進一步估計:n521335+(84+27)531335,所以,n167,所以n可取134,144,154,164,又n515+(-1)53(mod3),故n=144.注：歐拉猜測4個自然數(shù)的5次方之和不是5次方,于1962年被三位美國數(shù)學(xué)家推翻,例6就是他們舉的反例

3、.例7. 求32006的個位數(shù)及末兩位數(shù)字.解：(1)即求a(0a9),使得32006a(mod10).329-1(mod10),341(mod10),3200632004+234X501+232(mod10),故32006的個位數(shù)是9;(2)即求b(0b99),使得32006b(mod100).注意到:4 X25=100且(4,25)=1,34811(mod5),34816(mod25),383611(mod25),31266-9(mod25),316-54-4(mod25)320-241(mod25) ;321(mod4)3201(mod4) ,由,得3201(mod100),320063

4、20 X1003629(mod100),故32006的末兩位數(shù)字是29.例8. 求1 X3 X5 X 7 XX2005的末3位數(shù)字.解：注意到:8X125=1000且(8,125)=1，(2n-3)(2n-1)(2n+1)(2n+3)(4n2-9)(4n2-1)1(mod8)，及M=1 X3 X5 X 7 XX2005=125m是1003個奇數(shù)之積，M1 X3 X57(mod8), 125m5m7(mod8)，m3(mod8)，M125m125X3375(mod8)，M125m375(mod8).即1 X3 X5 X 7 XX2005的末3位數(shù)字為375.例9. 求大于5的素數(shù)平方被30除的余

5、數(shù).解：設(shè)p是大于5的素數(shù),且pr(mod30)(rn1,求最小的m+n使得1000|1978m-1978n.解：令k=m-n,則1978m-1978n0(mod1000)2n989n(1978k-1) 0(mod2353)，19783(mod5) 197841(mod5)，19783(mod25) 1978203201(mod25)，1978-22(mod53),(-22)20(25-3)20320(243)474(50-1)226(mod53)19782026 (mod53), 197840(25+1)251(mod53),197860(25+1)(50+1)76(mod53),19788

6、0(50+1)2101(mod53),1978100(25+1)(100+1)1(mod53),100|kk最小=100, m+n=m-n+2n最小=106.例13. 設(shè)是整數(shù)序列,其中有無窮多項為正整數(shù),也有無窮多項為負整數(shù).假設(shè)對每個正整數(shù),數(shù)被除的余數(shù)都各不相同.證明:在數(shù)列中,每個整數(shù)都剛好出現(xiàn)一次. 證明：數(shù)列各項同時減去一個整數(shù)不改變本題的條件和結(jié)論,故不妨設(shè)a1=0.此時對每個正整數(shù)k必有akk:若akk,取n=ak,則a1ak0(mod n),矛盾.現(xiàn)在對k歸納證明a1,a2,ak適當(dāng)重排后是絕對值小于k的k個相鄰整數(shù).k=1顯然.設(shè)a1,a2,ak適當(dāng)重排后為(k1i),0,

7、i (0i k1),由于a1,a2,ak,ak+1是(mod k+1)的一個完全剩余系,故必ak+1i+1(mod k+1), 但ak+1k+1,因此ak+1只能是i+1或(ki),從而a1,a2,ak,ak+1適當(dāng)重排后是絕對值小于k+1的k+1個相鄰整數(shù).由此得到:1).任一整數(shù)在數(shù)列中最多出現(xiàn)一次;2).若整數(shù)u和v (ua,(p,a)=1, x2,x3,xp+2這p+1個數(shù)中必有兩個屬于modp的同一剩余類,即有mn2,使得xmxn(modp),由題意有xm-xna(xm-1-xn-1)0(modp),依次類推,有xm-n+1-x10(modp),即有p|xm-n+1,因數(shù)列增,所以x

8、m-n+1p, xm-n+1不是質(zhì)數(shù).2. 確定所有正整數(shù)n,使方程xn+(2+x)n+(2-x)n=0有整數(shù)解. 解：顯然,若n為偶數(shù),則方程無實數(shù)根,若n=1,則x=-4.當(dāng)n3且為奇數(shù)時方程左端是首項為1,常數(shù)項為2n+1的多項式其整解只能是-2t(t為非負整數(shù))形式:若t=0,1,2則x=-1,-2,-4都不是方程的根;若t3,則-2nt+(2-2t)n+(2+2t)n=0-2n(t-1)+(1-2t-1)n+(1+2t-1)n=0，-2n(t-1)+(1-2t-1)n+(1+2t-1)n2(mod4)左端0.綜上知,僅當(dāng)n=1時,原方程有唯一整解x=-4.3. 問是否存在一個無限項素

9、數(shù)數(shù)列p1,p2,pn,對任意n滿足|pn+1-2pn|=1?請說明理由.解：若存在,則由pn+1=2pn1pn知pn遞增, p33, p31或2(mod3).若p31(mod3),則p4=2p3-1即p41(mod3)p5=2p4-1,pn=2pn-1-1pn=2n-3p3-2n-3+1,取n-3=p3-1則由1(modp3)知pn0(modp3),矛盾!若p32(mod3), 則p4=2p3+1,即p42(mod3)p5=2p4+1,pn=2pn-1+1,pn=2n-3p3+2n-3-1,取n-3=p3-1則由1(modp3)知pn0(modp3),矛盾!4. 設(shè)三角形的三邊長分別為整數(shù)L

10、,m,n,且Lmn.已知,其中x表示x的小數(shù)部分.求三角形周長的最小值.解：3L,3m,3n的末四位數(shù)相同,從而104|3L-3m=3m(3L-m-1),104|3L-m-1L-m=4k,其中kN*.3L-m=81k=(1+80)k=1+104|3L-m-1104|125|=k(40k-39)+5|5|k, 125|，125|k(40k-39)+，125|k(40k-39)540k-3912540k-39125|k,k=125r,其中rN*.即L-m=4k=500r,同理m-n=500s,sN*.nL-m=500r500n小=501，m=n+500s501+500=1001，m小=1001,L

11、500+1001=1501,所求三角形周長的最小值為501+1001+1501=3003.解法2：由已知得3L3m3n(mod104)即3L3m3n(mod24) ，3L3m3n(mod54) ，由得3m-n1(mod24) 341(mod24) 4|m-n,m-n=4k,由得3m-n34k1(mod54),現(xiàn)求滿足此式的k:34k-1(1+524)k-15k24+5228+532120(mod54)k=53t,m-n=500t,同理L-n=500r,其中t,r為正整數(shù)，Lmnrt,即三角形三條邊為500r+n, 500t+n和n,且有n500(r-t)500僅當(dāng)t=1,r=2,n=501時,

12、1000+501+500+501+501=3003.5. 如果整數(shù)n不是2的倍數(shù),也不是5的倍數(shù).證明n必能整除一個各位都是1的數(shù)。 證明：若數(shù)中有被n整除者，則問題得證；否則必有與(mr)使得，即，因n不是2和5的倍數(shù)，所以，得證。6. 設(shè)a是45687777的各位數(shù)之和, b是a的各位數(shù)之和,c是b的各位數(shù)之和.求c. 解：45687777100007777=1047777共47777+1=31109位數(shù)，a931109=279981,b2+59=47,c4+9=13，4568777757777532592+15(-1)25925(mod9)，abc5(mod9) c=5.7. 對于給定的

13、正整數(shù)k,用f1(k)表示k的各位數(shù)之和的平方,并設(shè)fn+1(k)=f1(fn(k)(n1).試求f2005(22006)的值.解：注意到10m1(mod9)正整數(shù)N=an10n+a110+a0an+a1+a0(mod9).設(shè)f1(22006)=a12,則a1220062366844(mod9), 設(shè)f2(22006)=f1(a12)=a22,則a2a127(mod9),設(shè)f3(22006)= f1(a22)=a32,則a3a224(mod9),，lg22006=2006lg2700f1(22006)(9700)24107,f2(22006)(3+97)24500,f3(22006)(3+39

14、)2=302a31,且(a,m)=1.則有a(m)1(modm).2. Fermat定理：設(shè)p是素數(shù),則對任意正整數(shù)a有apa(modp).證明：若p|a,則顯然成立.若(p,a)=1,則a,2a,(p-1)a對modp余數(shù)各不相同(若p|(m-n)a(n3是素數(shù)，p1(mod6)或p5(mod6)，3p-2p-136k+1-26k+1-13-2-10(mod7)或3p-2p-136k+5-26k+5-15-4-10(mod7)即7|3p-2p-142p|3p-2p-1.例4. 已知m,n為正整數(shù),且m為奇數(shù),(m,2n-1)=1.證明:m|.證明：1,2,m構(gòu)成modm的完系,(m,2)=1

15、2,4,2m也構(gòu)成modm的完系即(m,2n-1)=1，得證.例5. 求與數(shù)列中所有項都互質(zhì)的所有正整數(shù).解：顯然(1,an)=1.設(shè)m1是與an中所有項都互質(zhì)的正整數(shù),p為m的一個質(zhì)因數(shù),若p3,則由費馬小定理得:,，記,(),則=，由ap-2為整數(shù),，6|3m+2n+t,這與(m,ap-2)=1矛盾!若p=2或3,則a2=48=243,p|a2也矛盾!故與中所有項都互質(zhì)的正整數(shù)只有1.例6. 求使得7d1(mod2r)(整數(shù)r3)的最小正整數(shù)d0.解：(2r)=2r(1-)=2r-1及d0|(2r)d0=2k, 0kr-1.先證:對任意奇數(shù)a,必有:歸納法,設(shè)a=2t+1,當(dāng)r=3時,a2

16、=4t(t+1)+11(mod23),設(shè)當(dāng)r=n時,則當(dāng)r=n+1時,可被2n+1整除,即有,故結(jié)論成立. 由此可知d0=2k中的k滿足0kr-2.我們證明:對任意整數(shù)r3,必有1(mod2r):歸納法,當(dāng)r=3時,顯然成立,設(shè)當(dāng)r=n時,1(mod2n)1(mod2n-1) =1+s2n-1,其中整數(shù)2s,21+s2n-2,即1(mod2n+1)1(mod2r),由此推得:1(mod2r),0jr-3,故d0=2r-2為所求.例7求所有的正整數(shù)對(p,n)滿足:()p是素數(shù); ()n2p; ()np-1|(p-1)n+1.解：顯然(p,1)和(2,2)是滿足題意的正整數(shù)對，下設(shè)n2,p3.(

17、p-1)n+1為奇數(shù)n為奇數(shù)且n2p，記q為n的最小素因子，則q|(p-1)n+1即(p-1)n-1(modq),且(q,p-1)=1,(n,q-1)=1,存在u,vZ使得un+v(q-1)=1,由Fermat小定理得：p-1(p-1)nu(p-1)v(q-1) (-1)u (modq)q為奇數(shù)u必為奇數(shù),p-1-1(modq)，從而p=q，n2p=2q及q是n的最小素因子n=p=q.(p-1)p+1=pp-1|(p-1)p+1p3p=3,滿足題意的所有的正整數(shù)對為(p,1)、(2,2)、(3,3)其中p為任意質(zhì)數(shù)(IMO40). 方法2：對任意素數(shù)p，數(shù)對(p,1)是解；當(dāng)p=2時，僅有數(shù)對

18、(2,1)、(2,2)是解；下設(shè)p3，n2，若(p,n)是解，則n是奇數(shù)，設(shè)n的最小素因子是q，n=qdm(qm)，則(p-1)q(p-1)(modq)(p-1)(modq)q|(p-1)n+1，(p-1)2m1(modq)，q|(p-1)2m-1，(p-1)q-11(modq)，q|(p-1)q-1-1q是n的最小素因子(2m,q-1)=2，設(shè)p-1對模q的階為r,則r|2m,r|q-1，r=2q|(p-1)2-1=p(p-2)，(m,q-1)=1,若q|p-2,則q|(p-1)m+1=(p-2)+1m+1= (p-2)m+m(p-2)+2q|2與n是奇數(shù)矛盾q|p,必有q=p，n=qdm=

19、pdm2p=2qn=q=p,又由()得pp-1|(p-1)p+1=pp-1-+p2展開式僅有4項n=p=3。故滿足條件的所有的正整數(shù)對為(p,n)=(p,1)、(2,2)、(3,3)。例8. 已知p為奇素數(shù).證明：.證明：p-1為偶數(shù)，k2p-1+(p-k)2p-1=，k2p-1+(p-k)2p-1p(2p-1)k2p-2(modp2),由Fermat定理知kp-11(modp)，(2p-1)k2p-22p-1-1(modp)即(2p-1)k2p-2=pm-1，p(2p-1)k2p-2p2m-p-p(modp2)，練習(xí)題1. 求所有的素數(shù)對(x,y)滿足xy-yx=xy2-19.解：xy=yx

20、+xy2-19及Fermat定理xyx(mody)，xyx-19(mody)y|x+19,同理x|y-19,xy|(x+19)(y-19),即xy|19(y-x-19)xy|y-x-19.()當(dāng)x=2時,2y=3y2-19,由y|x+19=21得y=3,7,檢驗知(2,3)和(2,7)都是解.()當(dāng)y=2時,x2=2x+4x-19,且x|(-17)x=17檢驗知(17,2)非解.()當(dāng)x3時,當(dāng)y3時,由xy|y-x-19及yx+19得:3xxyx+19-yx+16即3xx+16x8,x=3,5,7.此時,由y|x+19=22,24,26得y=11,3,13不滿足x|y-19,非解.滿足xy-

21、yx=xy2-19的所有素數(shù)對(x,y)=(2,3)和(2,7).2. 證明：不存在非負整數(shù)k和m,使得k!+48=48(k+1)m.證明：k=0,m=0顯然不是解.下設(shè)k,m為正整數(shù).10.若k+1為合數(shù),則k+1|k!, k+1|4848|k!k6, k=7,11,23,47檢驗知都不是解.20.若k+1為素數(shù),由Wilson定理知k!-1(modk+1),即k+1|k!+1，k!+48=48(k+1)mk+1|47,k=46.方程為46!+48=4847m即=47m,取mod4得1(-1)m(mod4)m為偶數(shù),令m=2m1.則有=232|,，232|，46m1+1(mod232)，23

22、2|232|46m123|m1m=2m146,故有46!+482,則由Fermat定理得2p-11(modp),令n=(mp-1)(p-1),m為任意正整數(shù),則n1(modp),2n1(modp)2n-n0(modp),即有p|2n-n.故結(jié)論成立.5. 已知k為正整數(shù),k2, p1,p2,pk為奇素數(shù),且(a,p1p2pk)=1.證明a-1有不同于p1,p2,pk的奇素數(shù)因數(shù).證明：(a,p1p2pk)=1(a,p1)=1, 由Fermat定理得:,又為正整數(shù)，即,同理得,為偶數(shù)，且4,即有異于p1,p2,pk的奇素數(shù)因數(shù)有異于p1,p2,pk的奇素數(shù)因數(shù).6. 已知p為素數(shù).證明,存在一個

23、素數(shù)q,使得對任意正整數(shù)n,qnp-p. 證明：，中至少有一個素因子q滿足q1(modp2).若存在正整數(shù)n使得npp(modq),則有(p|pp-1),由Fermat定理得: nq-11(modq)及p2q-1,(p2,q-1)|p(p2,q-1)=1或p)，np1(modq)npp(modq)p1(modq)1+p+p2+pp-1p(modq)，q是1+p+p2+pp-1的一個質(zhì)因子p0(modq)與p1(modq)矛盾!7. 設(shè)正整數(shù)a,b,c,d,m,n滿足:a+b+c+d=m2, a2+b2+c2+d2=1989,且其中a,b,c,d 的最大者為n2.試求m,n的值.解:顯然,a,b

24、,c,d不全為偶數(shù)(1奇或3奇),從而m為奇數(shù).m2=a+b+c+da2+b2+c2+d2=1989m2即m245m2=49或81.若m2=49即a+b+c+d=49.a,b,c,d 的最大者為d=n24n4a2+b2+c2+d2=1989n5,a+b+c=49-n25n6即n=5或6,d=25或36.a+b+c=24或13, a2+b2+c2 =1364或693,(a+b+c)2=242=576a2+b2+c2或(a+b+c)2=132=169a2+b2+c2 ,此時方程無解.m2=a+b+c+n2=81, a2+b2+c2+n4=1989,4n281n51989-n43即n419925n6

25、即n=5或6. 當(dāng)n=5時,a+b+c=56,a2+b2+c2 =1364,4|1364=a2+b2+c2a,b,c均為偶數(shù):a=2a1,b=2b1,c=2c1且a12+b12+c12 =341, a1+b1+c1=28a12+b12+c12 =3411(mod4)a1,b1,c1必定兩個偶數(shù)一個奇數(shù): a1=2a2,b1=2b2,c1=2k-1且2(a2+b2+k)=29矛盾!當(dāng)n=6時,a+b+c=45,a2+b2+c2 =693,6931(mod4)a=2a1,b=2b1,c=2k-1且a1+b1+k=23,a12+b12+k(k-1) =173,k(k-1)為偶數(shù)a1,b1一奇一偶:

26、a1=2a2,b1=2r-1且2a2+2r+k=24,4a22+4r(r-1)+k(k-1) =1722|k,4|k(k-1)4|k,又173-k(k-1) =,即有k2-16k+6107k9,4|kk=8,a2+r=8,a22+r(r-1)=29,消去a2得2r2-17r+35=0,解得r=5,(a,b,c,d)=(12,18,15,36)m2=81,n2=36,(m,n)=(9,6).8. 求方程2x3y-5z7w=1的所有非負整數(shù)解(x,y,z,w).解:(1)若y=0,則2x-5z7w=1,當(dāng)z0時, 2x1(mod5)241(mod5)4|x,從而3|2x-1=5z7w,這不可能z=

27、0, 2x-7w=1,當(dāng)x=1,2,3時,(x,w)=(1,0),(3,1);當(dāng)x4時, 7w=2x-1-1(mod16),但當(dāng)w為偶數(shù)時7w1(mod16),當(dāng)w為奇數(shù)時7w7(mod16),矛盾.這時解為(1,0,0,0),(3,0,0,1);(2)若y0.當(dāng)x=1時,23y-5z7w=1,則5z7w-1(mod3),即(-1)z-1(mod3)z為奇數(shù)23y1(mod5)341(mod5),y1(mod4)即y=4m+1.當(dāng)w0時, 23y1(mod7)361(mod7)y4(mod6),y=6n+4=4m+1,即6n=4m-3矛盾必有w=0, 23y-5z=1,當(dāng)y=1時,z=1;當(dāng)y2時,5z-1(mod9)561(mod9)z3(mod6),53+1|5z+1,7|5z+1=23y矛盾! 這時解為(1,1,1,