高中數(shù)學(xué)競(jìng)賽專題講座專題訓(xùn)練

1、競(jìng)賽試卷同余的概念與應(yīng)用概念與性質(zhì)1. 定義：若整數(shù) a,b 被整數(shù) m(m 1) 除的余數(shù)相同 ,則稱 a 同余于 b 模 m, 或 a,b 對(duì)模 m 同余 .記為 a b(modm).余數(shù) r:0 r<1.2. 性質(zhì)： ( )a b(modm)m|a-b, 即 a=b+mk,k Z.( )若 a b(modm),b c(modm),則 a c(modm).( )若 a1 b1(modm),a 2 b2(modm) ，則 a 1±a2 b1±b2(modm),a 1a2 b1b 2(modm);( )設(shè) f(x)=a nxn+a n-1 xn-1 + +a 1 x+

2、a 0,g(x)=b nxn+b n-1 xn-1 + +b 1 x+b 0 是兩個(gè)整系數(shù)多項(xiàng)式,滿足 a ibi(modm)(0 i n)若. a b(modm), 則 f(a) f(b)(modm).( )ac bc(modm)a b(modm),(c, m)( )若 m 1,(a,m)=1, 則存在整數(shù)c 使得 ac 1(modm). 稱 c 為 a 對(duì)模 m 的逆或倒數(shù) ,記為 c=a -1(modm);ab(mod m1 )ab (modm 12若 12且12()同時(shí)成立);(),a)=b(mod m2 ),m)ab(modmb(modm),(m ,ma1, 則 a b(modm 1

3、m2).3. 剩余類： 設(shè) m 為正整數(shù)，把全體整數(shù)按對(duì)模m 的余數(shù)分成 m 類，相應(yīng) m 個(gè)集合記為： K 0,K 1, ,Km-1 ,其中 K r=qm+r|q Z,0 余數(shù) r m-1 稱為模 m 的一個(gè) 剩余類 。性質(zhì)： ()ZK i 且 K iKj= (i j).0 i m 1( )每一整數(shù)僅在K0 ,K 1, ,Km-1 一個(gè)里 .( )對(duì)任意 a、 b Z，則 a 、b Kra b(modm).4. 完全剩余系： 設(shè) K 0,K 1, ,Km-1 為模 m 的全部剩余類，從每個(gè)Kr 里任取一個(gè)a r，得 m 個(gè)數(shù) a0,a1 , ,am-1組成的數(shù)組，叫做模m 的一個(gè) 完全剩余系

4、 。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ì)： ( )K r 與模 m 互質(zhì)K r 中有一個(gè)數(shù)與 m 互質(zhì)；( )與模 m 互質(zhì)的剩余類的個(gè)數(shù)等于(m ) ;( )若 (a,m)=1, 則 x 與 ax+b 同時(shí)跑遍模 m 的既約剩余系。( )設(shè)

5、 (a,p)=1, 則 d0 是 a 對(duì)于模 p 的階ddo-1對(duì)模 p 兩兩不同余 .特別地 ,do=ao 1(modp), 且 1,a, ,a(p)-1構(gòu)成模 p 的一個(gè)既約剩余系 . (p)1,a, ,a例 1. 設(shè) xi - 1,1,i=1,2, ,101,證明 :x1+2x 2+ +100x 101 0.證明 : x1 +2x 2+ +100x 101 1+2+ +101 51 1(mod2)成立 .例 2.設(shè) p 為質(zhì)數(shù) .求證 : Cnpn (mod p) .p證明 : n0,1,2, ,p-1(modp) 必有某一個(gè)nnii(0 i p-1)使得 ni(modp), 從而p.n

6、(n-p1) (n-i+1)(n-i- 1) (n-p+1) i(i-1) 1(p-1) (i+1)-(p1)!(modp) ， (p-1)! Cnp =(p-1)!n(n- 1) (n-i+1)(n-i-pn競(jìng)賽試卷1) (n-p+1)ni (p-1)!ni(modp), 即 (p-1)! Cnp (p-1)!ni(modp), 因 (p-1)!,p)=1 Cnpn in (modp!ppppnin (mod p) .pp例 3. 設(shè) m>0, 證明必有一個(gè)僅由0 或 1 構(gòu)成的自然數(shù)a 是 m 的倍數(shù) .證明 ：考慮數(shù)字全為1 的數(shù) :1,11,111,1111,中必有兩個(gè)在modm

7、 的同一剩余類中,它們的差即為所求的 a.例 4. 證明從任意m 個(gè)整數(shù) a1 ,a2, ,am 中, 必可選出若干個(gè)數(shù),它們的和 (包括只一個(gè)加數(shù))能被 m 整除 .證明 ：考慮 m 個(gè)數(shù) a1 ,a1+a 2,a1+a 2+a 3 , ,a1+a 2+ +a m,如果其中有一個(gè)數(shù)能被 m 整除 ,則結(jié)論成立 ,否則 ,必有兩個(gè)數(shù)屬于 modm 的同一剩余類 ,這兩個(gè)數(shù)的差即滿足要求 .例 5. 證明數(shù) 11,111,1111, 中無(wú)平方數(shù) .證明：因任意整數(shù)n 20或 1(mod4), 而 11 111 1111 3(mod4),所以 ,數(shù) 11,111,1111,中無(wú)平方數(shù) .例 6.

8、確定 n 5=133 5+110 5+84 5+27 5.55555 3+4+7 4(mod10),所以 n個(gè)位數(shù)字為 4,顯然 n的首位數(shù)字為1,進(jìn)一步估解：因 n3+0+4 +7555計(jì) :n5<2×133 5 +(84+27) 5<3×133 5 <1335, 所以 ,n<133 <167, 所以 n可取 134,144,154,164,又44n555 3(mod3), 故 n=144.1+(-1)注： 歐拉猜測(cè)4 個(gè)自然數(shù)的5 次方之和不是5 次方 ,于 1962年被三位美國(guó)數(shù)學(xué)家推翻,例 6就是他們舉的反例 .例 7.求 3 2006

9、的個(gè)位數(shù)及末兩位數(shù)字 .解：(1) 即求 a(0 a9),使得 3200624 1(mod10),320062004+24X501+2 a(mod10). 3 9-1(mod10), 33332 (mod10),故3 2006的個(gè)位數(shù)是9;(2) 即求b(0 b99),使得 32006 b(mod100). 注意到 :4X25=100且(4,25)=1,3 4 81 1(mod5), 34 81 6(mod25),38 36 11(mod25),3 12 66-9(mod25),3 16-54-4(mod25) 320 -24 1(mod25) ; 32 1(mod4) 320 1(mod4)

10、,由 ,得 3 20 1(mod100), 32006 320 X100 ?36 29(mod100), 故 3 2006的末兩位數(shù)字是29.例 8. 求 1X3 X5X7XX2005 的末 3 位數(shù)字.解：注意到 :8X125=1000且 (8,125)=1 ， (2n-3)(2n- 1)(2n+1)(2n+3) (4n2-9)(4n 2 -1) 1(mod8)，及 M=1 X3 X5 X 7 X X2005=125m是 1003個(gè)奇數(shù)之積， M1X3 X5 7(mod8), 125m 5m 7(mod8)， m3(mod8) ， M 125m 125X3 375(mod8) ， M 125

11、m 375(mod8). 即 1 X3 X5 X 7 X X2005的末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， 1211222 1(mod30), 72222， p21或 19(mod30) 19 2913 17 23 19(mod30)例 10.設(shè) n,k 為正整數(shù) ,求證 :存在無(wú)限多個(gè)形如 n?2k-7的平方數(shù) .解：即求使得 m2 +7 0(mod2 k)成立的整數(shù) m. 當(dāng) k=1,2,3 時(shí) ,

12、取 m=1+4r(r 為正奇數(shù) ), 則有 m2 +7 0(mod2k).設(shè)對(duì) k( 3)有整數(shù) m 使得 m 2 +7 0(mod2k), 顯然 m 為奇數(shù) ,對(duì)于 k+1 ， (m+a?2 k-1 )2 +7m2+7+ma?2 km 272+7 0(mod2 k+1 ) ，對(duì)任意2k (am+b)(mod2 k+1 ),其中 b= Z+ ,取正整數(shù) a,b 同奇偶 ,則有 (m+a?2 k-1 )2 k正整數(shù) k 存在無(wú)限多個(gè)整數(shù) m 使得 m2 +7 0(mod2 k).例 11. 設(shè)對(duì)任意正整數(shù) n1,b的質(zhì)因數(shù)都大于 n.證明： n!|a(a+b)(a+2b)(a+3b)a+(n -

13、1)b證明： b 的質(zhì)因數(shù)都大于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競(jìng)賽試卷例 12. 設(shè) m>n1, 求最小的 m+n 使得 1000|1978 m -1978 n.解：令 k=m-n, 則 1978m-1978n 0(mod1000)2n?989n(1978k-1)3 3 0(mod2

14、?5 )2n0(mod 2 3 )n 342020， 19783(mod5)19781978k1 1(mod5)， 1978 3(mod25) 1978 3 0(mod 53 )1(mod25)， 1978-22(mod53),(-22)20 (25-3)2020442320 263 (243)7 (50-1) 26(mod5 ) 1978(mod5 3), 19784023603802 101(mod53),1978100 (25+1) 51(mod5 ),1978 (25+1)(50+1) 76(mod5),1978 (50+1)(25+1)(100+1) 1(mod53), 100|k

15、k 最小 =100, m+n=m-n+2n最小 =106.例 13.設(shè) a1 , a2 , a3 ,是整數(shù)序列 ,其中有無(wú)窮多項(xiàng)為正整數(shù),也有無(wú)窮多項(xiàng)為負(fù)整數(shù).假設(shè)對(duì)每個(gè)正整數(shù)n ,數(shù) a , a , a ,a 被 n 除的余數(shù)都各不相同. 證明 :在數(shù)列 a, a ,a ,中 ,每個(gè)整數(shù)都剛好出現(xiàn)一次 .123n123證明： 數(shù)列各項(xiàng)同時(shí)減去一個(gè)整數(shù)不改變本題的條件和結(jié)論,故不妨設(shè) a 1=0. 此時(shí)對(duì)每個(gè)正整數(shù)k 必有 ak <k: 若 ak k,取 n= a k ,則 a 1ak 0(mod n), 矛盾 .現(xiàn)在對(duì) k 歸納證明a1 ,a2, ,ak 適當(dāng)重排后是絕對(duì)值小于 k 的

16、 k 個(gè)相鄰整數(shù) .k=1 顯然 .設(shè) a 1,a 2, ,ak 適當(dāng)重排后為 (k 1 i),0, ,i(0 i k 1),由于a1 ,a2, ,ak ,ak+1 是(mod k+1) 的一個(gè)完全剩余系 ,故必 ak+1 i+1(mod k+1),但 a k+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ù)列中 .最后由正

17、負(fù)項(xiàng)均無(wú)窮多個(gè)（即數(shù)列含有任意大的正整數(shù)及任意小的負(fù)整數(shù)）就得到 :每個(gè)整數(shù)在數(shù)列中出現(xiàn)且只出現(xiàn)一次 .例 14. 偶數(shù)個(gè)人圍著一張圓桌討論，休息后，他們依不同次序重新圍著圓桌坐下，證明至少有兩個(gè)人，他們中間的人數(shù)在休息前與休息后是相等的。證明 ：將座號(hào)依順時(shí)針次序記為1,2, ,2n，每個(gè)人休息前后的座號(hào)記為(i,j) ，則 i 與 j 跑遍完全剩余系mod2n 。如果兩個(gè)人 (i 1,j1) ， (i2 ,j2 )休息前后在他們中間的人數(shù)不相等，則有j2 -j1i2-1mod2n ，即 j 2-i2j1-i 1(mod2n) ，因此， j i 也跑遍完全剩余系mod2n j i 的和 =

18、ji 0(mod2n) ，而任一完全剩余系mod2n的和 1+2+ +2n-1 n(2n-1) 0(mod2n),矛盾！故結(jié)論成立。例 15.證明：不論 n 和 k 是怎樣的正整數(shù) ,2n 3k +4n k+10不可能是連續(xù)正整數(shù)之積 .證明：令 p=n k ,則 2n 3k +4n k+10=2p 3+4p+10 是偶數(shù) ,取 mod3, 2p3 +4p+10=(3p 3+3p+9)-(p-1)p(p+1)+1 2p 3 +4p+10 1(mod3), 從而 2p 3+4p+10 不是 3個(gè)或3 個(gè)以上連續(xù)正整數(shù)之積 ,而兩個(gè)連續(xù)正整數(shù)之積按mod3分類 : 3m(3m +1) 0(mod3

19、),(3m+1)(3m+2) 2(mod3),(3m+3)(3m+2) 0(mod3)原式也不是兩個(gè)正整數(shù)之積 .綜上知 :2n 3k+4n k+10 不可能是連續(xù)正整數(shù)之積 .例 16.設(shè)正整數(shù)a,b 使得 15a+16b和 16a-15b都是正整數(shù)的平方，求這兩個(gè)平方數(shù)所可能取的最小值(IMO 37 4)。2 和 16a-15b=y 2 ,x,y Z+ ,則 15x 2+16y 2=(13 ·37)a,16x 2 -15y 2=(13 ·37)b, 若 (37,y)=1,解： 設(shè) 15a+16b=x設(shè) yy 1 1(mod37), 則由 15x 2+16y2 0(mod

20、37),16x 2 -15y 2 0(mod37), 得 15(xy 1 )2 -16(mod37),16(xy 1 )215(mod37)(xy 1)2 -6(mod37) ，這是不可能的， 因僅有 r2 0, ± 1, ± 3, ± 4, ± 7, ± 9, ± 10, ± 12, ±16(mod37)x=22222222(mod13),若(13,u)=1 ，設(shè) uu 1 1(mod13),37u,y=37v,0 15u+16v 2u+3v(mod13),0 16u -15v 3u -2v則 2(vu 1)2-

21、3(mod13),3(vu1)2 2(mod13)(vu1)2 5(mod13), 這是不可能的 ,因僅有 r 2 0, ± 1, ± 3, ± 4(mod13) u=13s,v=13t,x=37 ·13s,y=37 ·13t, 取 s=t=1得 x2，y2的最小值為 x2 =y 2=(13 ·37) 2=231361 ，此時(shí)， a=13·37·31 ，b=13·37 。練習(xí)題1. 設(shè) a,b,x 0 N* ,xn=ax n-1+b ,n=1,2, .證明 x1 ,x2 , 不可能都是質(zhì)數(shù) .證明： 設(shè)

22、x1=p 是質(zhì)數(shù) ,則 p>a,(p,a)=1,x2,x 3, ,xp+2 這 p+1個(gè)數(shù)中必有兩個(gè)屬于 modp 的同一剩余類 ,即有 m>n2, 使得 xm xn(modp), 由題意有xm-x n a(xm-1-xn-1 ) 0(modp),依次類推 ,有 xm-n+1 -x1 0(modp),即有競(jìng)賽試卷p| xm-n+1 , 因數(shù)列增 ,所以 xm-n+1 >p, x m-n+1 不是質(zhì)數(shù) .2. 確定所有正整數(shù)n,使方程 xn+(2+x) n +(2-x) n=0 有整數(shù)解 .解： 顯然 ,若 n 為偶數(shù) ,則方程無(wú)實(shí)數(shù)根,若 n=1, 則 x=-4. 當(dāng) n3且

23、為奇數(shù)時(shí)方程左端是首項(xiàng)為1,常數(shù)項(xiàng)為 2n+1 的多項(xiàng)式其整解只能是-2 t(t 為非負(fù)整數(shù) )形式 :若 t=0,1,2則 x=-1,-2,-4都不是方程的根;若 t 3,則 -2 nt +(2-2 t)n+(2+2 t)n=0-2 n(t-1) +(1-2 t-1 )n +(1+2 t-1 )n=0 ， -2 n(t-1) +(1-2 t-1 )n+(1+2 t-1 )n 2(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 滿足 |p n+1 -2p n |=1? 請(qǐng)說(shuō)明理由 .解： 若存

24、在 ,則由 pn+1 =2p n±1>p n 知 p n遞增 , p 3 >3, p3 1或 2(mod3). 若 p 3 1(mod3), 則 p 4=2p 3 -1 即p4 1(mod3) p5=2p 4-1, ,pn=2p n-1 -1 pn=2 n-3 p3 -2 n-3 +1, 取 n-3=p 3-1 則由 2 p3 1 1(modp3)知 p n 0(modp3), 矛盾 !若 p 3 2(mod3), 則 p 4=2p 3 +1, 即 p4 2(mod3) p5 =2p 4+1, ,pn=2p n-1 +1, pn =2 n-3 p 3+2 n-3 -1,取

25、 n-3=p 3-1 則由 2 p3 1 1(modp3)知 p n 0(modp3 ),矛盾 !Lmn4. 設(shè)三角形的三邊長(zhǎng)分別為整數(shù)L,m,n, 且 L>m>n. 已知 3 4 34 3 4 , 其中 x表示 x 的小數(shù)部101010分 .求三角形周長(zhǎng)的最小值 .Lmn解： 34 3 4 34 3 L,3m ,3n 的末四位數(shù)相同 ,從而 10 4|3 L -3 m=3 m(3L-m -1),10 4|3 L-m -1 L-m101010=4k, 其中 k N*. 3L-m =81 k=(1+80) k=1+ C k1 80C k2 802C k3 80380 k 10 4|3

26、 L-m -1104| C k1 80 C k2 802CC k1 80 C k2 802C k3 80 3125| C k1C k2 80C k3 802=k(40k-39)+C k3 802 5| C k2 80C k3 80 2 5|k,125| C k3 802 ， 125|k(40k-39)+Ck3 802 ， 125|k(40k-39) 5? 40k-39 125 ? 40k-39 125|k,k=125r,其中r N*.即 L-m=4k=500r, 同理 m-n=500s,sN *. n>L- m=500r 500 n 小 =501 ， m=n+500s 501+500=1

27、001 ， m 小=1001,L 500+1001=1501,所求三角形周長(zhǎng)的最小值為501+1001+1501=3003.解法 2：由已知得 3Lmn4)即Lmn4， 3Lmn4，由33 (mod103 33 (mod2 )33 (mod5 )得 3m-n 1(mod24) 44由得 3m-n4k1(mod54),現(xiàn)求滿足此式的k: 34k- 13 1(mod2 ) 4|m-n,m-n=4k,3(1+5?24k4)-1 5k?2+k(k 1) 2 8k (k1)( k 2) 3 12 0(mod54)k=53t,m-n=500t,同理 L-n=?5?2+?5 ?226500r, 其中 t,r

28、 為正整數(shù)，L>m>n r>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 不是 2 的倍數(shù) ,也不是5 的倍數(shù) . 證明 n 必能整除一個(gè)各位都是1 的數(shù)。n 1 個(gè)m 個(gè)r個(gè)證明：若數(shù) 1 11 111,1111中有被 n 整除者，則問(wèn)題得證； 否則必有 1111 與1111(m>r),m個(gè)r 個(gè)m個(gè)r 個(gè)m r個(gè)r個(gè)使得 111 1 1111(mod n) ，即 n |111 1111 1111 100

29、，因 n 不是 2和 5的倍mr個(gè)數(shù)，所以 n |1111，得證。6.設(shè) a 是 4568 7777 的各位數(shù)之和 , b 是 a 的各位數(shù)之和 ,c 是 b 的各位數(shù)之和 .求 c.競(jìng)賽試卷解： 4568 7777 <10000 7777=10 4×7777 共 4×7777+1=31109位數(shù)， a<9×31109=279981,b<2+5× 9=47,c<4+9=13 ， 4568777777773×2592+15(-1)2592 5(mod9)， a b c 5(mod9)c=5.5 57. 對(duì)于給定的正整數(shù)k,

30、用 f1 (k)表示 k 的各位數(shù)之和的平方,并設(shè) fn+1 (k)=f 1(f n(k)(n 1)試.求 f 2005 (2 2006 ) 的值 .解： 注意到 10m 1(mod9)正整數(shù) N=a n×10 n+ +a 1×10+a 0an+ +a 1 +a 0(mod9). 設(shè) f1 (2 2006 )=a 12 ,則20063×668?44(mod9), 設(shè) f 2(22006)=f2)=a 222 7(mod9),設(shè) f3(22006)= f 1(a2)=a22a1 2 21 (a 1,則 a2a123,則 a 3a24(mod9), ， lg2 200

31、6 =2006×lg2<700 f1(2 2006 )<(9 ×700) 2 <4×107 ,f2 (2 2006 )<(3+9 ×7) 2<4500,f 3(2 2006 )<(3+3×9) 2=30 2 a 3<30 a 3=4,13,22. ，f3 (2 2006 ) 16,169,242, f3(2 2006 )=16 時(shí), f 4(2 2006 )=7 2 =49, f 5(2 2006 )=13 2=169,f 6 (2 2006 )=16 2=256, f 7(2 2006 )=13 2

32、=169, ,f 2n(2 2006 )=16 2=256,f 2n+1 (2 2006 )=13 2 =169 f2005 (2 2006 )=169.8. 試求 777(100個(gè) 7) 的末四位數(shù) .解： 7-1(mod4) 777個(gè) 7),設(shè) 7777-1(mod4)(98=4k+3(98 個(gè) 7),k Z +,則 77=7 4k+3 (99 個(gè)777) 74 1(mod100) 74k 1(mod100), 774k+337=7100m+43(100個(gè) 7),m Z+.7 7 43(mod100). 又設(shè) 7 74 2401(mod10000) 78 4801(mod10000), 7

33、 16 9601(mod10000),7 32 9201(mod10000), 7 648401(mod10000),7100432642401?9201?8401 1(mod10000),7100m 1(mod10000),7100m+43437?7?777773832 2343 (mod10000) ， 77100m+437個(gè) 7) 的末四位數(shù)?7 ?7(100 個(gè) 7) 7 2343(mod10000), 7(100為 2343.三 . 重要定理及應(yīng)用1.Euler定理： 設(shè)整數(shù) m>1, 且 (a,m)=1. 則有 a (m) 1(modm).2.Fermat定理： 設(shè) p 是素

34、數(shù) ,則對(duì)任意正整數(shù) a 有 ap a(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, 矛盾 !). 所以 ,a?2a? ?(p-1)a 1?2?(p-1)(modp), 即 a p-1 ?(p-1)! (p-1)!(modp) ， (p,p-1)=1 ， ap a(modp).3. 設(shè)(a,m)=1,c 是使得 a c 1(modm) 的最小正整數(shù) , 則 c| (m).4. Wilson定理： 設(shè) p 是素?cái)?shù) ,則 (p -1)! -

35、1(mod p).5. 中國(guó)剩余定理：設(shè) K 2,而 m1,m 2, ,mk 是 K 個(gè)兩兩互質(zhì)的正整數(shù)，令M=m 1m 2mk =m 1 M1=m 2Mk=xa1 (mod m1 )xa2 (mod m2 )-1-1-1m kMk，則下列同余式組：的正整數(shù)解是 xa(modM).1M1M1+a 2 M2M2+ +a k MkMkx ak (mod mk )例 1. （）設(shè) n 為大于 1 的整數(shù)，證明 2 n-1 不能被 n 整除。（）試求所有能使 2 n+1 被 n 2 整除的素?cái)?shù) n 。證明：（）若 n 為偶數(shù)，則結(jié)論成立；若 n 為奇素?cái)?shù)，則 2n-1 1(modn), 結(jié)論成立；若

36、n 為奇合數(shù)，則 n 的質(zhì)因數(shù) (奇素?cái)?shù) )都不整除2n -1 ，即 n 不整除 2 n-1 ，故結(jié)論為真。（）易知使2 n+1 0(modn 2 )的素?cái)?shù) n 為奇數(shù)， (2,n)=1 ，2n 2(modn) 2n+1 0(modn) 3 0(modn)即 n|3 ， n=3 顯然滿足題意。例 2.證明對(duì)任意整數(shù)x5x37xx,3是整數(shù) .5153x55x37xx5 x(mod5), 3x 5+5x 3+7x 3x+7x 10x 0(mod5)，證明： 即,由 Fermat定理得15競(jìng)賽試卷 x3 x(mod3) 3x 5+5x 3 +7x 5x+7x 12x 0(mod3)， (3,5)=

37、1 3x 5 +5x 3+7x 0(mod15), 得證 .例 3. 設(shè) p 是大于 3 的素?cái)?shù) .求證 :42p|3 p-2 p -1.證明 ： 42=2×3×7,2|3 p-2 p-1,3|3 p -2 p-1, 由 Fermat 定理得3p 3(modp), 2p 2(modp)， 3p -2 p- 166pp6k+16k+1-13-0(modp) 3 1(mod7), 2 1(mod7),p>3 是素?cái)?shù)， p 1(mod6)或 p 5(mod6)， 3 -2-13 -22- 1 0(mod7)或 3p-2p6k+5-26k+5-15-4- 1 0(mod7)即

38、 7|3p-2p-1 42p|3p-2p-1.-13m例 4.已知 m,n為正整數(shù) ,且 m 為奇數(shù) ,(m,2 n-1)=1. 證明 :m|k n.k 1mm證明： 1,2, ,m 構(gòu)成 modm的完系 ,(m,2)=1 2,4, ,2m 也構(gòu)成 modm 的完系(2k )nk n (mod mk 1k 1mmmm( 2k ) nk n (mod m) 即 (2n1)k n0(mod m) (m,2 n -1)=1 ，m |k n 得證 .k 1k1k1k 1例 5.求與數(shù)列an2n3n6n 1,n 1 中所有項(xiàng)都互質(zhì)的所有正整數(shù) .解： 顯然 (1,a n)=1. 設(shè) m>1是與 a

39、 n 中所有項(xiàng)都互質(zhì)的正整數(shù),p 為 m 的一個(gè)質(zhì)因數(shù) ,若 p>3, 則由費(fèi)馬小定理得 : 2p 11 mod p , 3p 11 mod p , 6p 11 mod p ，記 2 p 1mp1, 3p 1np 1pnp 1, 6p 1tp 1( m, n,t Z ),則 ap 2 2p 23p 26p 21mp 1 np 1 tp 11=32363mp2nptpp 3m2nt ，由 a p-2為整數(shù) , ( p,6)1， 6|3m+2n+t,p a p2 這與 (m,a p-2 )=166矛盾 !若 p=2或 3,則 a2 =48=2 4?3,p|a 2 也矛盾 ! 故與 an中所有項(xiàng)都互質(zhì)的正整數(shù)只有1.例 6.求使得7d 1(mod2r)( 整數(shù) r 3)的最小正整數(shù) d0 .解： (2r)=2 r(1-12)=2r-1rk, 0 k-r1.先證 :對(duì)任意奇數(shù) a,必有 a2r 2r) :及 d 0| (2) d 0=21(mod2歸納法, 設(shè)23r=n時(shí) , a2n 21(mod2n) , 則當(dāng) r=n+1a=2t+1, 當(dāng) r=3 時(shí) ,a =4t(t+1)+1 1(mod2), 設(shè)當(dāng)時(shí) , a2n11 (a2n 21)(a2n 21) 可被 2n+1 整除 ,即有 a2n 11(mod2n 1 ) ,故