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

1、同余的概念與應(yīng)用概念與性質(zhì) 1. 定義：若整數(shù)a,b被整數(shù)m(m1)除的余數(shù)相同,則稱a同余于b模m,或a,b對(duì)模m同余.記為ab(modm).余數(shù)r:0r<1.2. 性質(zhì)：()ab(modm)m|a-b,即a=b+mk,kZ. ()若ab(modm),bc(modm),則ac(modm). ()若a1b1(modm),a2b2(modm)，則a1±a2b1±b2(modm),a1a2b1b2(modm); ()設(shè)f(x)=anxn+an-1xn-1+a1x+a0,g(x)=bnxn+bn-1xn-1+b1x+b0是兩個(gè)整系數(shù)多項(xiàng)式,滿足aibi(modm)(0in)

2、.若ab(modm),則f(a)f(b)(modm).()acbc(modm)ab(mod), ()若m1,(a,m)=1,則存在整數(shù)c使得ac1(modm).稱c為a對(duì)模m的逆或倒數(shù),記為c=a-1(modm); ()同時(shí)成立(modm1,m2);()若ab(modm1),ab(modm2),且(m1,m2)=1,則ab(modm1m2).3. 剩余類：設(shè)m為正整數(shù)，把全體整數(shù)按對(duì)模m的余數(shù)分成m類，相應(yīng)m個(gè)集合記為：K0,K1,Km-1,其中Kr=qm+r|qZ,0余數(shù)rm-1稱為模m的一個(gè)剩余類。性質(zhì)：()且KiKj=(ij). ()每一整數(shù)僅在K0,K1,Km-1一個(gè)里. ()對(duì)任意a

3、、bZ，則a、bKrab(modm).4. 完全剩余系：設(shè)K0,K1,Km-1為模m的全部剩余類，從每個(gè)Kr里任取一個(gè)ar，得m個(gè)數(shù)a0,a1,am-1組成的數(shù)組，叫做模m的一個(gè)完全剩余系。0,1,2,m-1叫做模m的最小非負(fù)完全剩余系。性質(zhì)：()m個(gè)整數(shù)構(gòu)成模m的一完全剩余系兩兩對(duì)模m不同余。 ()若(a,m)=1，則x與ax+b同時(shí)跑遍模m的完全剩余系。5. 既約剩余系：如果Kr里的每一個(gè)數(shù)都與m互質(zhì)，則Kr叫與m互質(zhì)的剩余類，在與模m互質(zhì)的全部剩余類中，從每一類任取一個(gè)數(shù)所做成的數(shù)組，叫做模m的一個(gè)既約剩余系。性質(zhì)：()Kr與模m互質(zhì)Kr中有一個(gè)數(shù)與m互質(zhì)； ()與模m互質(zhì)的剩余類的個(gè)數(shù)

4、等于; ()若(a,m)=1,則x與ax+b同時(shí)跑遍模m的既約剩余系。 ()設(shè)(a,p)=1,則d0是a對(duì)于模p的階ado1(modp),且1,a,ado-1對(duì)模p兩兩不同余.特別地,do=(p)1,a,a(p)-1構(gòu)成模p的一個(gè)既約剩余系.例1. 設(shè)xi-1,1,i=1,2,101,證明:x1+2x2+100x1010. 證明:x1+2x2+100x1011+2+101511(mod2)成立.例2. 設(shè)p為質(zhì)數(shù).求證:.證明:n0,1,2,p-1(modp)必有某一個(gè)i(0ip-1)使得ni(modp),從而.n(n-1)(n-i+1)(n-i-1)(n-p+1)i(i-1)1(p-1)(i

5、+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)!(modp),因(p-1)!,p)=1.例3. 設(shè)m>0,證明必有一個(gè)僅由0或1構(gòu)成的自然數(shù)a是m的倍數(shù). 證明：考慮數(shù)字全為1的數(shù):1,11,111,1111,中必有兩個(gè)在modm的同一剩余類中,它們的差即為所求的a.例4. 證明從任意m個(gè)整數(shù)a1,a2,am中,必可選出若干個(gè)數(shù),它們的和(包括只一個(gè)加數(shù))能被m整除. 證明：考慮m個(gè)數(shù)a1,a1+a2,a1+a2+a3,a1+a2+am,如果其中有一個(gè)數(shù)能被m整除,則結(jié)論成

6、立,否則,必有兩個(gè)數(shù)屬于modm的同一剩余類,這兩個(gè)數(shù)的差即滿足要求.例5. 證明數(shù)11,111,1111,中無(wú)平方數(shù). 證明：因任意整數(shù)n20或1(mod4),而1111111113(mod4),所以,數(shù)11,111,1111,中無(wú)平方數(shù).例6. 確定n5=1335+1105+845+275. 解：因n535+05+45+753+4+74(mod10),所以n個(gè)位數(shù)字為4,顯然n的首位數(shù)字為1,進(jìn)一步估計(jì):n5<2×1335+(84+27)5<3×1335<,所以,n<<167,所以n可取134,144,154,164,又n515+(-1)5

7、3(mod3),故n=144.注：歐拉猜測(cè)4個(gè)自然數(shù)的5次方之和不是5次方,于1962年被三位美國(guó)數(shù)學(xué)家推翻,例6就是他們舉的反例.例7. 求32006的個(gè)位數(shù)及末兩位數(shù)字.解：(1)即求a(0a9),使得32006a(mod10).329-1(mod10),341(mod10),3200632004+234X501+232(mod10),故32006的個(gè)位數(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(

8、mod25)320-241(mod25) ;321(mod4)3201(mod4) ,由,得3201(mod100),32006320 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個(gè)奇數(shù)之積，M1 X3 X57(mod8), 125m5m7(mod8)，m3(mod8)，M125m125X3375(mod8)

9、，M125m375(mod8).即1 X3 X5 X 7 XX2005的末3位數(shù)字為375.例9. 求大于5的素?cái)?shù)平方被30除的余數(shù).解：設(shè)p是大于5的素?cái)?shù),且pr(mod30)(r<30)，(p,30)=1(r,30)=1,r=1,7,11,13,17,19,23,29，121121922921(mod30), 7213217223219(mod30)，p21或19(mod30)例10. 設(shè)n,k為正整數(shù),求證:存在無(wú)限多個(gè)形如n2k-7的平方數(shù).解：即求使得m2+70(mod2k)成立的整數(shù)m.當(dāng)k=1,2,3時(shí),取m=1+4r(r為正奇數(shù)),則有m2+70(mod2k).設(shè)對(duì)k(3

10、)有整數(shù)m使得m2+70(mod2k),顯然m為奇數(shù),對(duì)于k+1，(m+a2k-1)2+7m2+7+ma2k2k(am+b)(mod2k+1),其中b=Z+,取正整數(shù)a,b同奇偶,則有(m+a2k-1)2+70(mod2k+1)，對(duì)任意正整數(shù)k存在無(wú)限多個(gè)整數(shù)m使得m2+70(mod2k).例11. 設(shè)對(duì)任意正整數(shù)n1,b的質(zhì)因數(shù)都大于n.證明：n!|a(a+b)(a+2b)(a+3b)a+(n-1)b 證明：b的質(zhì)因數(shù)都大于n，(b,n!)=1bb-11(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)

11、ab-1+(n-1)0(modn!)，(b-1,n!)=1，n!|a(a+b)(a+2b)(a+3b)a+(n-1)b例12. 設(shè)m>n1,求最小的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)

12、251(mod53),197860(25+1)(50+1)76(mod53),197880(50+1)2101(mod53),1978100(25+1)(100+1)1(mod53),100|kk最小=100, m+n=m-n+2n最小=106.例13. 設(shè)是整數(shù)序列,其中有無(wú)窮多項(xiàng)為正整數(shù),也有無(wú)窮多項(xiàng)為負(fù)整數(shù).假設(shè)對(duì)每個(gè)正整數(shù),數(shù)被除的余數(shù)都各不相同.證明:在數(shù)列中,每個(gè)整數(shù)都剛好出現(xiàn)一次. 證明：數(shù)列各項(xiàng)同時(shí)減去一個(gè)整數(shù)不改變本題的條件和結(jié)論,故不妨設(shè)a1=0.此時(shí)對(duì)每個(gè)正整數(shù)k必有ak<k:若akk,取n=ak,則a1ak0(mod n),矛盾.現(xiàn)在對(duì)k歸納證明a1,a2,ak適

13、當(dāng)重排后是絕對(duì)值小于k的k個(gè)相鄰整數(shù).k=1顯然.設(shè)a1,a2,ak適當(dāng)重排后為(k1i),0,i (0i k1),由于a1,a2,ak,ak+1是(mod k+1)的一個(gè)完全剩余系,故必ak+1i+1(mod k+1), 但ak+1<k+1,因此ak+1只能是i+1或(ki),從而a1,a2,ak,ak+1適當(dāng)重排后是絕對(duì)值小于k+1的k+1個(gè)相鄰整數(shù). 由此得到:1).任一整數(shù)在數(shù)列中最多出現(xiàn)一次;2).若整數(shù)u和v (u<v) 都出現(xiàn)在數(shù)列中,則u與v之間的所有整數(shù)也出現(xiàn)在數(shù)列中.最后由正負(fù)項(xiàng)均無(wú)窮多個(gè)（即數(shù)列含有任意大的正整數(shù)及任意小的負(fù)整數(shù)）就得到:每個(gè)整數(shù)在數(shù)

14、列中出現(xiàn)且只出現(xiàn)一次.例14. 偶數(shù)個(gè)人圍著一張圓桌討論，休息后，他們依不同次序重新圍著圓桌坐下，證明至少有兩個(gè)人，他們中間的人數(shù)在休息前與休息后是相等的。證明：將座號(hào)依順時(shí)針次序記為1,2,2n，每個(gè)人休息前后的座號(hào)記為(i,j)，則i與j跑遍完全剩余系mod2n。如果兩個(gè)人(i1,j1)，(i2,j2)休息前后在他們中間的人數(shù)不相等，則有j2-j1i2-i1mod2n，即j2-i2j1-i1(mod2n)，因此，ji也跑遍完全剩余系mod2nji的和=0(mod2n)，而任一完全剩余系mod2n的和1+2+2n-1n(2n-1)0(mod2n),矛盾！故結(jié)論成立。例15. 證明：不論n和k

15、是怎樣的正整數(shù),2n3k+4nk+10不可能是連續(xù)正整數(shù)之積. 證明：令p=nk,則2n3k+4nk+10=2p3+4p+10是偶數(shù),取mod3,2p3+4p+10=(3p3+3p+9)-(p-1)p(p+1)+12p3+4p+101(mod3),從而2p3+4p+10不是3個(gè)或3個(gè)以上連續(xù)正整數(shù)之積,而兩個(gè)連續(xù)正整數(shù)之積按mod3分類: 3m(3m+1)0(mod3),(3m+1)(3m+2)2(mod3),(3m+3)(3m+2)0(mod3)原式也不是兩個(gè)正整數(shù)之積.綜上知:2n3k+4nk+10不可能是連續(xù)正整數(shù)之積.例16. 設(shè)正整數(shù)a,b使得15a+16b和16a-15b都是正整數(shù)

16、的平方，求這兩個(gè)平方數(shù)所可能取的最小值(IMO374)。解：設(shè)15a+16b=x2和16a-15b=y2,x,yZ+,則15x2+16y2=(13·37)a,16x2-15y2=(13·37)b,若(37,y)=1,設(shè)yy11(mod37),則由15x2+16y20(mod37),16x2-15y20(mod37),得15(xy1)2-16(mod37),16(xy1)215(mod37) (xy1)2-6(mod37)，這是不可能的，因僅有r20,±1,±3,±4,±7,±9,±10,±12,±

17、;16(mod37)x=37u,y=37v,015u2+16v22u2+3v2(mod13),016u2-15v23u2-2v2(mod13),若(13,u)=1，設(shè)uu11(mod13),則2(vu1)2-3(mod13),3(vu1)22(mod13)(vu1)25(mod13),這是不可能的,因僅有r20,±1,±3,±4(mod13)u=13s,v=13t,x=37·13s,y=37·13t,取s=t=1得x2，y2的最小值為x2=y2=(13·37)2=231361，此時(shí)，a=13·37·31，b=13&

18、#183;37。練習(xí)題1. 設(shè)a,b,x0N*,xn=axn-1+b ,n=1,2, .證明x1,x2,不可能都是質(zhì)數(shù). 證明：設(shè)x1=p是質(zhì)數(shù),則p>a,(p,a)=1, x2,x3,xp+2這p+1個(gè)數(shù)中必有兩個(gè)屬于modp的同一剩余類,即有m>n2,使得xmxn(modp),由題意有xm-xna(xm-1-xn-1)0(modp),依次類推,有xm-n+1-x10(modp),即有p|xm-n+1,因數(shù)列增,所以xm-n+1>p, xm-n+1不是質(zhì)數(shù).2. 確定所有正整數(shù)n,使方程xn+(2+x)n+(2-x)n=0有整數(shù)解. 解：顯然,若n為偶數(shù),則方程無(wú)實(shí)數(shù)根,若

19、n=1,則x=-4.當(dāng)n3且為奇數(shù)時(shí)方程左端是首項(xiàng)為1,常數(shù)項(xiàng)為2n+1的多項(xiàng)式其整解只能是-2t(t為非負(fù)整數(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時(shí),原方程有唯一整解x=-4.3. 問(wèn)是否存在一個(gè)無(wú)限項(xiàng)素?cái)?shù)數(shù)列p1,p2,pn,對(duì)任意n滿足|pn+1-2pn|=1?請(qǐng)說(shuō)明理由.解：若存在,則由pn+1=2pn±1>pn知pn遞增, p3>

20、;3, 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è)三角形的三邊長(zhǎng)分別為整數(shù)L,m,n,且L>m>n.已知,其中x表示x的小數(shù)部分.求三角形周長(zhǎng)的最小值.解：3L,3m,3n的末四位數(shù)相同,從而

21、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*.n>L-m=500r500n小=501，m=n+500s501+500=1001，m小=1001,L500+1001=1501,所求三角形周長(zhǎng)的最小值為501+1001+1501=3003.解法2：由已知

22、得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ù)，L>m>nr>t,即三角形三條邊為500r+n, 500t+n和n,且有n>500(r-t)500僅當(dāng)t=1,r=2,n=501時(shí),1000+501+500+501+501=3003.5. 如果整數(shù)n不是

23、2的倍數(shù),也不是5的倍數(shù).證明n必能整除一個(gè)各位都是1的數(shù)。 證明：若數(shù)中有被n整除者，則問(wèn)題得證；否則必有與(m>r)使得，即，因n不是2和5的倍數(shù)，所以，得證。6. 設(shè)a是45687777的各位數(shù)之和, b是a的各位數(shù)之和,c是b的各位數(shù)之和.求c. 解：45687777<100007777=104×7777共4×7777+1=31109位數(shù)，a<9×31109=279981,b<2+5×9=47,c<4+9=13，456877775777753×2592+15(-1)25925(mod9)，abc5(mod9

24、) c=5.7. 對(duì)于給定的正整數(shù)k,用f1(k)表示k的各位數(shù)之和的平方,并設(shè)fn+1(k)=f1(fn(k)(n1).試求f2005(22006)的值.解：注意到10m1(mod9)正整數(shù)N=an×10n+a1×10+a0an+a1+a0(mod9).設(shè)f1(22006)=a12,則a12200623×66844(mod9), 設(shè)f2(22006)=f1(a12)=a22,則a2a127(mod9),設(shè)f3(22006)= f1(a22)=a32,則a3a224(mod9),，lg22006=2006×lg2<700f1(22006)<(

25、9×700)2<4×107,f2(22006)<(3+9×7)2<4500,f3(22006)<(3+3×9)2=302a3<30a3=4,13,22.，f3(22006)16,169,242, f3(22006)=16時(shí), f4(22006)=72=49, f5(22006)=132=169,f6(22006)=162=256, f7(22006)=132=169,f2n(22006)=162=256,f2n+1(22006)=132=169f2005(22006)=169.8. 試求(100個(gè)7)的末四位數(shù). 解：7-1

26、(mod4)-1(mod4)(98個(gè)7),設(shè)=4k+3(98個(gè)7),kZ+,則=74k+3(99個(gè)7)741(mod100)74k1(mod100),74k+37343(mod100).又設(shè)=7100m+43(100個(gè)7),mZ+.742401(mod10000)784801(mod10000), 7169601(mod10000),7329201(mod10000), 7648401(mod10000),7100747327642401920184011(mod10000),7100m1(mod10000),7100m+4374373787322343 (mod10000)，(100個(gè)7)7

27、100m+432343(mod10000),(100個(gè)7)的末四位數(shù)為2343.三. 重要定理及應(yīng)用 1. Euler定理：設(shè)整數(shù)m>1,且(a,m)=1.則有a(m)1(modm).2. Fermat定理：設(shè)p是素?cái)?shù),則對(duì)任意正整數(shù)a有apa(modp).證明：若p|a,則顯然成立.若(p,a)=1,則a,2a,(p-1)a對(duì)modp余數(shù)各不相同(若p|(m-n)a(n<mp-1),則p|m-n,m=n,矛盾!).所以,a2a(p-1)a12(p-1)(modp),即ap-1(p-1)!(p-1)!(modp)，(p,p-1)=1，apa(modp).3. 設(shè)(a,m)=1,c是

28、使得ac1(modm)的最小正整數(shù),則c|(m).4. Wilson定理：設(shè)p是素?cái)?shù),則(p -1)!-1(mod p).5.中國(guó)剩余定理：設(shè)K2,而m1,m2,mk是K個(gè)兩兩互質(zhì)的正整數(shù)，令M=m1m2mk=m1M1=m2Mk=mkMk，則下列同余式組：的正整數(shù)解是xa1M1M1-1+a2M2M2-1+akMkMk-1(modM).例1. （）設(shè)n為大于1的整數(shù)，證明2n-1不能被n整除。 （）試求所有能使2n+1被n2整除的素?cái)?shù)n。 證明：（）若n為偶數(shù)，則結(jié)論成立；若n為奇素?cái)?shù)，則2n-11(modn),結(jié)論成立；若n為奇合數(shù)，則n的質(zhì)因數(shù)(奇素?cái)?shù))都不整除2n-1，即n不整除2n-1，

29、故結(jié)論為真。 （）易知使2n+10(modn2)的素?cái)?shù)n為奇數(shù)，(2,n)=1，2n2(modn)2n+10(modn)30(modn)即n|3，n=3顯然滿足題意。例2. 證明對(duì)任意整數(shù)x,是整數(shù). 證明：即,由Fermat定理得x5x(mod5),3x5+5x3+7x3x+7x10x0(mod5)，x3x(mod3)3x5+5x3+7x5x+7x12x0(mod3)，(3,5)=13x5+5x3+7x0(mod15),得證.例3. 設(shè)p是大于3的素?cái)?shù).求證:42p|3p-2p-1.證明：42=2×3×7,2|3p-2p-1,3|3p-2p-1,由Fermat定理得3p3

30、(modp), 2p2(modp)，3p-2p-10(modp)361(mod7), 261(mod7),p>3是素?cái)?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)=12,4,2m也構(gòu)成modm的完系即(m,2n-1)=1，得證.例5. 求與數(shù)列中所有項(xiàng)都互質(zhì)的所有正整數(shù).解：顯然(1,an)=1.設(shè)m&g

31、t;1是與an中所有項(xiàng)都互質(zhì)的正整數(shù),p為m的一個(gè)質(zhì)因數(shù),若p>3,則由費(fèi)馬小定理得:,，記,(),則=，由ap-2為整數(shù),，6|3m+2n+t,這與(m,ap-2)=1矛盾!若p=2或3,則a2=48=243,p|a2也矛盾!故與中所有項(xiàng)都互質(zhì)的正整數(shù)只有1.例6. 求使得7d1(mod2r)(整數(shù)r3)的最小正整數(shù)d0.解：(2r)=2r(1-)=2r-1及d0|(2r)d0=2k, 0kr-1.先證:對(duì)任意奇數(shù)a,必有:歸納法,設(shè)a=2t+1,當(dāng)r=3時(shí),a2=4t(t+1)+11(mod23),設(shè)當(dāng)r=n時(shí),則當(dāng)r=n+1時(shí),可被2n+1整除,即有,故結(jié)論成立. 由此可知d0=2

32、k中的k滿足0kr-2.我們證明:對(duì)任意整數(shù)r3,必有1(mod2r):歸納法,當(dāng)r=3時(shí),顯然成立,設(shè)當(dāng)r=n時(shí),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ù)對(duì)(p,n)滿足:()p是素?cái)?shù); ()n2p; ()np-1|(p-1)n+1.解：顯然(p,1)和(2,2)是滿足題意的正整數(shù)對(duì)，下設(shè)n2,p3.(p-1)n+1為奇數(shù)n為奇數(shù)且n<2p，記q為n的最小素因子，則q|(p-1)n+1即(p-1)n-1(modq),且

33、(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，n<2p=2q及q是n的最小素因子n=p=q.(p-1)p+1=pp-1|(p-1)p+1p3p=3,滿足題意的所有的正整數(shù)對(duì)為(p,1)、(2,2)、(3,3)其中p為任意質(zhì)數(shù)(IMO40). 方法2：對(duì)任意素?cái)?shù)p，數(shù)對(duì)(p,1)是解；當(dāng)p=2時(shí)，僅有數(shù)對(duì)(2,1)、(2,2)是解；下設(shè)p3，n2，若(p,n)是解，則n是奇數(shù)，設(shè)n的最小素因子是q，n=qdm(

34、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對(duì)模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=pdm<2p=2qn=q=p,又由()得pp-1|(p-1)p+1=pp-1-+p2展開(kāi)式僅有4項(xiàng)n=

35、p=3。故滿足條件的所有的正整數(shù)對(duì)為(p,n)=(p,1)、(2,2)、(3,3)。例8. 已知p為奇素?cái)?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. 求所有的素?cái)?shù)對(duì)(x,y)滿足xy-yx=xy2-19.解：xy=yx+xy2-19及Fermat定理xyx(mody)，xyx-19(mody)y|x+19,同理x|y

36、-19,xy|(x+19)(y-19),即xy|19(y-x-19)xy|y-x-19.()當(dāng)x=2時(shí),2y=3y2-19,由y|x+19=21得y=3,7,檢驗(yàn)知(2,3)和(2,7)都是解.()當(dāng)y=2時(shí),x2=2x+4x-19,且x|(-17)x=17檢驗(yàn)知(17,2)非解.()當(dāng)x3時(shí),當(dāng)y3時(shí),由xy|y-x-19及yx+19得:3xxyx+19-yx+16即3xx+16x8,x=3,5,7.此時(shí),由y|x+19=22,24,26得y=11,3,13不滿足x|y-19,非解.滿足xy-yx=xy2-19的所有素?cái)?shù)對(duì)(x,y)=(2,3)和(2,7).2. 證明：不存在非負(fù)整數(shù)k和m,

37、使得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檢驗(yàn)知都不是解.20.若k+1為素?cái)?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)，232|232|46m123|m1m=2m146,故有46!+48<4847m.綜上所述,不存在非

38、負(fù)整數(shù)k和m,使得k!+48=48(k+1)m.3. 已知p是一個(gè)大于5的素?cái)?shù).求證:至少存在兩個(gè)不同的正整數(shù)q1,q2滿足:()1q1,q2p-1; ()qip-11(modp2)(i=1,2). 證明：引理:若ab1(modc),則必存在素?cái)?shù)q|a且qb1(modc).證明原題:由二項(xiàng)式定理可知(p-1)p-1, (p+1)p-1, (2p-1)p-1, (2p+1)p-1這四個(gè)數(shù)在modp2下的余數(shù)均不為1存在q1|p-1且q1p-11(modp2).()若q12,則令q2=2,易知q2|p+1,且q2p-11(modp2), q1,q2即為所求.()若q1=2,則由2p-1, 2p+1

39、中必有一數(shù)被3整除,可令q2=3,則必有q2|2p-1或2p+1,且q2p-11(modp2)得證.4. 證明,對(duì)于每一個(gè)素?cái)?shù)p,總存在無(wú)窮多個(gè)正整數(shù)n使得p|2n-n. 證明：若p=2,則n取任意偶數(shù),結(jié)論成立;若p>2,則由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為奇素?cái)?shù),且(a,p1p2pk)=1.證明a-1有不同于p1,p2,pk的奇素?cái)?shù)因數(shù).證明：(a,p1p2pk)=1(a,p1)=1, 由F

40、ermat定理得:,又為正整數(shù)，即,同理得,為偶數(shù)，且4,即有異于p1,p2,pk的奇素?cái)?shù)因數(shù)有異于p1,p2,pk的奇素?cái)?shù)因數(shù).6. 已知p為素?cái)?shù).證明,存在一個(gè)素?cái)?shù)q,使得對(duì)任意正整數(shù)n,qnp-p. 證明：，中至少有一個(gè)素因子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的一個(gè)質(zhì)因子p0(modq)與p1(modq)矛盾!7.

41、設(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,c,d不全為偶數(shù)(1奇或3奇),從而m為奇數(shù).m2=a+b+c+d<90,m2只能取12,32,52,72,92,(a+b+c+d)2>a2+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

42、 =1364或693,(a+b+c)2=242=576>a2+b2+c2或(a+b+c)2=132=169>a2+b2+c2 ,此時(shí)方程無(wú)解.m2=a+b+c+n2=81, a2+b2+c2+n4=1989,4n281n51989-n43即n419925n6即n=5或6. 當(dāng)n=5時(shí),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必定兩個(gè)偶數(shù)一個(gè)奇數(shù): a1=2a2,b1=2b2,c1=2k-1且2(a2+b2+k)=29矛盾!當(dāng)n=6時(shí),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一奇一偶: 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,