同余的概念与应用
概念与性质
1. 定义：若整数a,b 被整数m(m≥1)除的余数相同,则称a 同余于b 模m,或a,b 对模m 同余.记为a≡b(modm).余数r:0≤r<1.
2. 性质：(ⅰ)a≡b(modm)?m|a-b,即a=b+mk,k ∈Z.
(ⅱ)若a≡b(modm),b≡c(modm),则a≡c(modm).
(ⅲ)若a 1≡b 1(modm),a 2≡b 2(modm)，则a 1±a 2≡b 1±b 2(modm),a 1a 2≡b 1b 2(modm);
(ⅳ)设f(x)=a n x n +a n-1x n-1+…+a 1x+a 0,g(x)=b n x n +b n-1x n-1+…+b 1x+b 0是两个整系数多项式,满足a i ≡ b i (modm)(0≤i≤n).若a≡b(modm),则f(a)≡f(b)(modm).(ⅴ)ac≡bc(modm)?a≡b(mod )
,(m c m ), (ⅵ)若m≥1,(a,m)=1,则存在整数c 使得ac≡1(modm).称c 为a 对模m 的逆或倒数,记为c=a -1(modm); (ⅶ)???≡≡)
(mod )(mod 21m b a m b a 同时成立?≡a b (mod[m 1,m 2]);(ⅷ)若a≡b(modm 1),a≡b(modm 2),且(m 1,m 2)= 1,则a≡b(modm 1m 2).
3. 剩余类：设m 为正整数，把全体整数按对模m 的余数分成m 类，相应m 个集合记为：K 0,K 1,…,K m-1,其中K r ={qm+r|q ∈Z,0≤余数r≤m -1}称为模m 的一个剩余类。
性质：(ⅰ)i m i K Z 10-≤≤= 且K i ∩K j =φ(i≠j).
(ⅱ)每一整数仅在K 0,K 1,…,K m-1一个里.
(ⅲ)对任意a 、b ∈Z ，则a 、b ∈K r ?a≡b(modm).
4. 完全剩余系：设K 0,K 1,…,K m-1为模m 的全部剩余类，从每个K r 里任取一个a r ，得m 个数a 0,a 1,…,a m-1组成的数组，叫做模m 的一个完全剩余系。0,1,2,…,m -1叫做模m 的最小非负完全剩余系。 性质：(ⅰ)m 个整数构成模m 的一完全剩余系?两两对模m 不同余。
(ⅱ)若(a,m)=1，则x 与ax+b 同时跑遍模m 的完全剩余系。
5. 既约剩余系：如果K r 里的每一个数都与m 互质，则K r 叫与m 互质的剩余类，在与模m 互质的全部剩余类中，从每一类任取一个数所做成的数组，叫做模m 的一个既约剩余系。
性质：(ⅰ)K r 与模m 互质?K r 中有一个数与m 互质；
(ⅱ)与模m 互质的剩余类的个数等于)m (?;
(ⅲ)若(a,m)=1,则x 与ax+b 同时跑遍模m 的既约剩余系。
(ⅳ)设(a,p)=1,则d 0是a 对于模p 的阶?a d o≡1(modp),且1,a,…,a do-1对模p 两两不同余.特别地,d o = Φ(p)?1,a,…,a Φ(p)-1构成模p 的一个既约剩余系.
例1. 设x i ∈{-1,1},i=1,2,…,101,证明:x 1+2x 2+…+100x 101≠0.
证明:∵x 1+2x 2+…+100x 101≡1+2+…+101≡51≡1(mod2)∴成立.
例2. 设p 为质数.求证:)(mod p p n C p n ??
????≡. 证明:∵n≡0,1,2,…,p -1(modp)∴必有某一个i(0≤i≤p -1)使得n≡i(modp),从而p i n p n -=??
????.∴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
n C =(p-1)!n(n-1)…(n -i+1)(n-i-
1)…(n-p+1)!
p i n -≡(p -1)!p i n -(modp),即(p-1)!p n C ≡(p -1)!p i n -(modp),因((p-1)!,p)=1∴(mod p p n p i n C p n ??????≡-≡ )(mod p p n p i n p n
??????≡-≡. 例3. 设m>0,证明必有一个仅由0或1构成的自然数a 是m 的倍数.
证明：考虑数字全为1的数:1,11,111,1111,…中必有两个在modm 的同一剩余类中,它们的差即为所求的a.
例4. 证明从任意m 个整数a 1,a 2,…,a m 中,必可选出若干个数,它们的和(包括只一个加数)能被m 整除. 证明：考虑m 个数a 1,a 1+a 2,a 1+a 2+a 3,…,a 1+a 2+…+a m ,如果其中有一个数能被m 整除,则结论成立,否则,必有两个数属于modm 的同一剩余类,这两个数的差即满足要求.
例5. 证明数11,111,1111,…中无平方数.
证明：因任意整数n 2≡0或1(mod4),而11≡111≡1111≡…≡3(mod4),所以,数11,111,1111,…中无平方数. 例6. 确定n 5=1335+1105+845+275.
解：因n 5≡35+05+45+75≡3+4+7≡4(mod10),所以n 个位数字为4,显然n 的首位数字为1,进一步估
计:n 5<2×1335+(84+27)5<3×1335<55
13345???
? ??,所以,n<13345?<167,所以n 可取134,144,154,164,又n 5≡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).注意到:4 X25=100且(4,25)=1,34≡81≡1(mod5),∵34≡81≡6(mod25),38≡36≡11(mod25),∴312≡66≡-9(mod25),316≡-54≡-4(mod2
5)∴320≡-24≡1(mod25) ①;∵32≡1(mod4)∴320≡1(mod4) ②,由①,②得320≡1(mod100),∴32006≡ 320 X100?36≡29(mod100),故32006的末两位数字是29.
例8. 求1 X3 X5 X 7 X…X2005的末3位数字.
解：注意到:8X125=1000且(8,125)=1，∵(2n-3)(2n-1)(2n+1)(2n+3)≡(4n 2-9)(4n 2-1)≡1(mod8)，及M= 1 X3 X5 X 7 X…X2005=125m 是1003个奇数之积，∴M≡1 X3 X5≡7(mod8), 125m≡5m≡7(mod8)，∴m≡ 3(mod8)，∴M≡125m≡125X3≡375(mod8)，∴M≡125m≡375(mod8).即1 X3 X5 X 7 X…X2005的末3位数字为375.
例9. 求大于5的素数平方被30除的余数.
解：设p 是大于5的素数,且p≡r(mod30)(r<30)，∵(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)，∴p 2≡1或19(mod30)
例10. 设n,k 为正整数,求证:存在无限多个形如n?2k -7的平方数.
解：即求使得m 2+7≡0(mod2k )成立的整数m.当k=1,2,3时,取m=1+4r(r 为正奇数),则有m 2+7≡0(mod2k ).设对k(≥3)有整数m 使得m 2+7≡0(mod2k ),显然m 为奇数,对于k+1，∵(m+a?2k-1)2+7≡m 2+7+ma?2k ≡
2k (am+b)(mod2k+1),其中b=k m 272+∈Z +,取正整数a,b 同奇偶,则有(m+a?2k-1)2+7≡0(mod2k+1)，∴对任意正整数k 存在无限多个整数m 使得m 2+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)n a(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. 设m>n≥1,求最小的m+n 使得1000|1978m -1978n .
解：令k=m-n,则1978m -1978n ≡0(mod1000)?2n ?989n (1978k -1) ≡0(mod23?53)?
?????≡-≥?≡)
5(mod 0119783)2(mod 0233k n n ，∵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,,,
a a a 是整数序列,其中有无穷多项为正整数,也有无穷多项为负整数.假设对每个正整数n ,数123,,,,n a a a a 被n 除的余数都各不相同.证明:在数列123,,,
a a a 中,每个整数都刚好出现一次. 证明：数列各项同时减去一个整数不改变本题的条件和结论,故不妨设a 1=0.此时对每个正整数k 必有∣a k ∣ 例14. 偶数个人围着一张圆桌讨论，休息后，他们依不同次序重新围着圆桌坐下，证明至少有两个人，他们中间的人数在休息前与休息后是相等的。 证明：将座号依顺时针次序记为1,2,…,2n ，每个人休息前后的座号记为(i,j)，则i 与j 跑遍完全剩余系mod2n 。如果两个人(i 1,j 1)，(i 2,j 2)休息前后在他们中间的人数不相等，则有j 2-j 1≡i 2-i 1mod2n ，即j 2-i 2≡ j 1-i 1(mod2n)，因此，j －i 也跑遍完全剩余系mod2n ∴j －i 的和=∑∑-i j ≡0(mod2n)，而任一完全剩余系mod2n 的和≡1+2+…+2n -1≡n(2n -1)≡0(mod2n),矛盾！故结论成立。 例15. 证明：不论n 和k 是怎样的正整数,2n 3k +4n k +10不可能是连续正整数之积. 证明：令p=n k ,则2n 3k +4n k +10=2p 3+4p+10是偶数,取mod3,∵2p 3+4p+10=(3p 3+3p+9)-(p-1)p(p+1)+1 ∴2p 3+4p+10≡1(mod3),从而2p 3+4p+10不是3个或3个以上连续正整数之积,而两个连续正整数之积按mod3分类: 3m(3m+1)≡0(mod3),(3m+1)(3m+2)≡2(mod3),(3m+3)(3m+2)≡0(mod3)∴原式也不是两个正整数之积.综上知:2n 3k +4n k +10不可能是连续正整数之积. 例16. 设正整数a,b 使得15a+16b 和16a-15b 都是正整数的平方，求这两个平方数所可能取的最小值(IMO 37－4)。 解：设15a+16b=x 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,设yy 1≡1(mod37),则由15x 2+16y 2≡0(mod37),16x 2-15y 2≡0(mod37),得15(xy 1)2≡-16(mod37),16(xy 1)2≡ 15(mod37)? (xy 1)2≡-6(mod37)，这是不可能的，因仅有r 2≡0,±1,±3,±4,±7,±9,±10,±12,±16(mod37)∴x= 37u,y=37v,0≡15u 2+16v 2≡2u 2+3v 2(mod13),0≡16u 2-15v 2≡3u 2-2v 2(mod13),若(13,u)=1，设uu 1≡1(mod13),则2(vu 1)2≡-3(mod13),3(vu 1)2≡2(mod13)?(vu 1)2≡5(mod13),这是不可能的,因仅有r 2≡0,±1,±3,±4(mod13) ∴u=13s,v=13t,x=37·13s,y=37·13t,取s=t=1得x 2，y 2的最小值为x 2=y 2=(13·37)2=231361，此时，a= 13·37·31，b=13·37。 练习题 1. 设a,b,x 0∈N *,x n =ax n-1+b ,n=1,2, ….证明x 1,x 2,…不可能都是质数. 证明：设x 1=p 是质数,则p>a,(p,a)=1, x 2,x 3,…,x p+2这p+1个数中必有两个属于modp 的同一剩余类,即有m>n≥2,使得x m ≡x n (modp),由题意有x m -x n ≡a(x m-1-x n-1)≡0(modp),依次类推,有x m-n+1-x 1≡0(modp),即有 p |x m-n+1,因数列增,所以x m-n+1>p, x m-n+1不是质数. 2. 确定所有正整数n,使方程x n +(2+x)n +(2-x)n =0有整数解. 解：显然,若n 为偶数,则方程无实数根,若n=1,则x=-4.当n≥3且为奇数时∵方程左端是首项为1,常数项为2n+1的多项式∴其整解只能是-2t (t 为非负整数)形式:若t=0,1,2则x=-1,-2,-4都不是方程的根;若t≥3,则-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)n ≡2(mod4)∴左端≠0.综上知,仅当n=1时,原方程有唯一整解x=-4. 3. 问是否存在一个无限项素数数列p 1,p 2,…,p n ,…对任意n 满足|p n+1-2p n |=1?请说明理由. 解：若存在,则由p n+1=2p n ±1>p n 知{p n }递增, p 3>3, p 3≡1或2(mod3).若p 3≡1(mod3),则p 4=2p 3-1即p 4≡1(mod3)∴p 5=2p 4-1,…,p n =2p n-1-1∴p n =2n-3p 3-2n-3+1,取n-3=p 3-1则由132-p ≡1(modp 3) 知p n ≡0(modp 3),矛盾!若p 3≡2(mod3), 则p 4=2p 3+1,即p 4≡2(mod3)∴p 5=2p 4+1,…,p n =2p n-1+1, ∴p n =2n-3p 3+2n-3-1,取n-3=p 3-1则由132-p ≡1(mo dp 3)知p n ≡0(modp 3),矛盾! 4. 设三角形的三边长分别为整数L,m,n,且L>m>n.已知==}10 3{}103{44m L }103{4n ,其中{x}表示x 的小数部分.求三角形周长的最小值. 解：∵}10 3{}103{}103{444n m L ==∴3L ,3m ,3n 的末四位数相同,从而104|3L -3m =3m (3L-m -1),104|3L-m -1∴L-m =4k,其中k ∈N *.∵3L-m =81k =(1+80)k =1+k k k k C C C 8080808033221++++ ∴104|3L-m -1?104|2218080k k C C C ++ 33221808080k k k C C C ++?125|23218080k k k C C C ++=k(40k-39)+2380k C ∵5|2328080k k C C +∴5|k, 125|2380k C ，∵125|k(40k-39)+2380k C ，∴125|k(40k-39)∵5?40k-39∴125?40k-39∴125|k,k=125r,其中r ∈N *.即L-m=4k=500r,同理m-n=500s,s ∈N *.∵n>L-m=500r≥500∴n 小=501，∵m=n+500s≥501+500= 1001，∴m 小=1001,L≥500+1001=1501,所求三角形周长的最小值为501+1001+1501=3003. 解法2：由已知得3L ≡3m ≡3n ≡(mod104)即3L ≡3m ≡3n ≡(mod24) ①，3L ≡3m ≡3n ≡(mod54) ②，由①得3m-n ≡1(mod24) ∵34≡1(mod24) ∴4|m-n,m-n=4k,由②得3m-n ≡34k ≡1(mod54),现求满足此式的k:∵34k -1≡ (1+5?24)k -1≡5k?24+2)1(-k k ?52?28+6)2)(1(--k k k ?53?212≡0(mod54)?k=53t,m-n=500t,同理L-n= 500r,其中t,r 为正整数，∵L>m>n ∴r>t,即三角形三条边为500r+n, 500t+n 和n,且有n>500(r-t)≥500∴仅当t=1,r=2,n=501时,1000+501+500+501+501=3003. 5. 如果整数n 不是2的倍数,也不是5的倍数.证明n 必能整除一个各位都是1的数。 证明：若数 个11111111111+n ,,,,中有被n 整除者，则问题得证；否则必有 个m 1111与 个 r 1111(m>r)使得 个m 1111≡)n (mod r 个1111，即 个个个个r r m r m ][|n 00111111111111-=-，因n 不是2和5的倍 数，所以 个r m |n -1111，得证。 6. 设a 是45687777的各位数之和, b 是a 的各位数之和,c 是b 的各位数之和.求c. 解：∵45687777<100007777=104×7777共4×7777+1=31109位数，∴a<9×31109=279981,b<2+5×9=47, c<4+9=13，∵45687777≡57777≡53×2592+1≡5(-1)2592≡5(mod9)，∴a≡b≡c≡5(mod9) ∴c=5. 7. 对于给定的正整数k,用f 1(k)表示k 的各位数之和的平方,并设f n+1(k)=f 1(f n (k))(n≥1).试求f 2005(22006)的值. 解：注意到10m ≡1(mod9)∴正整数N=a n ×10n +…+a 1×10+a 0≡a n +…+a 1+a 0(mod9).设f 1(22006)=a 12,则a 1≡22006≡23×668?4≡4(mod9), 设f 2(22006)=f 1(a 12)=a 22,则a 2≡a 12≡7(mod9),设f 3(22006)= f 1(a 22)=a 32,则a 3≡a 22≡ 4(mod9),，∵lg22006=2006×lg2<700∴f 1(22006)<(9×700)2<4×107,f 2(22006)<(3+9×7)2<4500,f 3(22006)<(3+ 3×9)2=302∵a 3<30∴a 3=4,13,22.，f 3(22006)∈{16,169,242}, f 3(22006)=16时, f 4(22006)=72=49, f 5(22006)=132= 169,f 6(22006)=162=256, f 7(22006)=132=169,…,f 2n (22006)=162=256,f 2n+1(22006)=132=169∴f 2005(22006)=169. 8. 试求7 77 (100个7)的末四位数. 解：∵7≡-1(mod4)∴7 77 ≡-1(mod4)(98个7),设777 =4k+3(98个7),k ∈Z +,则777 =74k+3(99个 7)∵74≡1(mod100)∴74k ≡1(mod100),777 ≡74k+3≡73≡43(mod100).又设777 =7100m+43(100个7),m ∈Z +. ∵74≡2401(mod10000)∴78≡4801(mod10000), 716≡9601(mod10000),732≡9201(mod10000), 764≡ 8401(mod10000),7100≡74?732?764≡2401?9201?8401≡1(mod10000),7100m ≡1(mod10000),7100m+43≡743≡ 73?78?732≡2343 (mod10000)，∴7 77 (100个7)≡7100m+43≡2343(mod10000),7 77 (100个7)的末四位数 为2343. 三. 重要定理及应用 1. Euler 定理：设整数m>1,且(a,m)=1.则有a φ(m)≡1(modm). 2. Fermat 定理：设p 是素数,则对任意正整数a 有a p ≡a(modp). 证明：若p|a,则显然成立.若(p,a)=1,则a,2a,…,(p -1)a 对modp 余数各不相同(若p|(m-n)a(n 3. 设(a,m)=1,c 是使得a c ≡1(modm)的最小正整数,则c|φ(m). 4. Wilson 定理：设p 是素数,则(p -1)!≡-1(mod p). 5.中国剩余定理：设K≥2,而m 1,m 2,…,m k 是K 个两两互质的正整数，令M=m 1m 2…m k =m 1M 1=m 2M k =…= m k M k ，则下列同余式组：???????≡≡≡) (mod )(mod )(mod 2211k k m a x m a x m a x 的正整数解是x≡a 1M 1M 1-1+a 2M 2M 2-1+…+a k M k M k -1(modM). 例1. （Ⅰ）设n 为大于1的整数，证明2n -1不能被n 整除。 （Ⅱ）试求所有能使2n +1被n 2整除的素数n 。 证明：（Ⅰ）若n 为偶数，则结论成立；若n 为奇素数，则2n -1≡1(modn),结论成立；若n 为奇合数，则n 的质因数(奇素数)都不整除2n -1，即n 不整除2n -1，故结论为真。 （Ⅱ）易知使2n +1≡0(modn 2)的素数n 为奇数，∴(2,n)=1，2n ≡2(modn)∵2n +1≡0(modn)∴3≡0(modn)即n|3，n=3显然满足题意。 例2. 证明对任意整数x,15 73535x x x ++是整数. 证明：即1575335x x x ++,由Fermat 定理得x 5≡x(mod5),∴3x 5+5x 3+7x≡3x+7x≡10x≡0(mod5)， ∵x 3≡x(mod3)∴3x 5+5x 3+7x≡5x+7x≡12x≡0(mod3)，∵(3,5)=1∴3x 5+5x 3+7x≡0(mod15),得证. 例3. 设p 是大于3的素数.求证:42p|3p -2p -1. 证明：∵42=2×3×7,2|3p -2p -1,3|3p -2p -1,由Fermat 定理得3p ≡3(modp), 2p ≡2(modp)，∴3p -2p -1≡ 0(modp)∵36≡1(mod7), 26≡1(mod7),p>3是素数，∴p≡1(mod6)或p≡5(mod6)，∴3p -2p -1≡36k+1-26k+1-1≡3- 2-1≡0(mod7)或3p -2p -1≡36k+5-26k+5-1≡5-4-1≡0(mod7)即7|3p -2p -1∴42p|3p -2p -1. 例4. 已知m,n 为正整数,且m 为奇数,(m,2n -1)=1.证明:m|∑=m k n k 1. 证明：∵1,2,…,m 构成modm 的完系,(m,2)=1∴2,4,…,2m 也构成modm 的完系∴(mod ) 2(1 1m k k m k n m k n ∑∑==≡ )(mod ) 2(11m k k m k n m k n ∑∑==≡即)(mod 0)12(1m k m k n n ≡-∑=∵(m,2n -1)=1，∴∑=m k n k m 1 |得证. 例5. 求与数列{}2361,1n n n n a n =++-≥中所有项都互质的所有正整数. 解：显然(1,a n )=1.设m>1是与{a n }中所有项都互质的正整数,p 为m 的一个质因数,若p>3,则由费马小定理得:()121mod p p -≡,()131mod p p -≡,()161mod p p -≡，记121p mp -=+,131 p np -=+ 31p np -=+,161p tp -=+(,,m n t Z ∈),则222211123611236p p p p mp np tp a ----+++=++-= ++-= 323266mp np tp m n t p ++++==?，∵由a p-2为整数,(,6)1p =，∴6|3m+2n+t,2p p a -这与(m,a p-2)=1矛盾!若p=2或3,则a 2=48=24?3,p|a 2也矛盾!故与{}n a 中所有项都互质的正整数只有1. 例6. 求使得7d ≡1(mod2r )(整数r≥3)的最小正整数d 0. 解：∵Φ(2r )=2r (1-21)=2r-1及d 0|Φ(2r )∴d 0=2k , 0≤k≤r -1.先证:对任意奇数a,必有)2(mod 122r r a ≡-:归纳法,设a=2t+1,当r=3时,a 2=4t(t+1)+1≡1(mod23),设当r=n 时,)2(mod 122n n a ≡-,则当r=n+1时,)1)(1(1221222+-=----n n n a a a 可被2n+1整除,即有)2(mod 1121+≡-n n a ,故结论成立. 由此可知d 0=2k 中的k 满足0≤k≤r -2.我们证明:对任意整数r≥3,必有327-r ?1(mod2r ):归纳法,当r=3时,显然成立,设当r=n 时,327-n ?1(mod2n )∵3 27-n ≡1(mod2n-1) ∴3 27-n =1+s?2n-1,其中整数2?s,∴s n n 1(1)7 (722232+==-- n n s s n n 2)21(1)7(722 2232-?++==--,2?1+s?2n-2,即227-n ?1(mod2n+1)∴327-r ?1(mod2r ),由此推 得:j 27?1(mod2r ),0≤j≤r -3,故d 0=2r-2为所求. 例7求所有的正整数对(p,n)满足:(ⅰ)p 是素数; (ⅱ)n≤2p; (ⅲ)n p-1|(p-1)n +1. 解：显然(p,1)和(2,2)是满足题意的正整数对，下设n≥2,p≥3.∵(p-1)n +1为奇数∴n 为奇数且n<2p ，记q 为n 的最小素因子，则q|(p-1)n +1即(p-1)n ≡-1(modq),且(q,p-1)=1,(n,q-1)=1,存在u,v ∈Z 使得 un+v(q-1)=1,由Fermat 小定理得：p-1≡(p -1)nu (p-1)v(q-1) ≡(-1)u (modq)∵q 为奇数∴u 必为奇数,p-1≡ -1(modq)，从而p=q ，∵n<2p=2q 及q 是n 的最小素因子∴n=p=q.∵(p-1)p +1=p C p C p p p p p p 111--++- ∴p p-1|(p-1)p +1?p≤3∴p=3,满足题意的所有的正整数对为(p,1)、(2,2)、(3,3)其中p 为任意质数(IMO 40). 方法2：对任意素数p ，数对(p,1)是解；当p=2时，仅有数对(2,1)、(2,2)是解；下设p≥3，n≥2，若(p,n)是解，则n 是奇数，设n 的最小素因子是q ，n=q d m(q?m)，则(p-1)q ≡(p -1)(modq)∴≡-d q p )1((p-1)(modq) ∵q|(p-1)n +1，∴)(mod 1)1()1()1(q p p p m n m q d -≡-≡-≡-，∵(p-1)2m ≡1(modq)，∴q|(p-1)2m -1， ∵(p-1)q-1≡1(modq)，∴q|(p-1)q-1-1∵q 是n 的最小素因子∴(2m,q-1)=2，设p-1对模q 的阶为r,则r|2m,r|q-1， ∴r=2∴q|(p-1)2-1=p(p-2)，∵(m,q-1)=1,若q|p-2,则q|(p-1)m +1=[(p-2)+1]m +1= (p-2)m +…+m(p -2)+2?q|2 与n 是奇数矛盾∴q|p,必有q=p ，∵n=q d m=p d m<2p=2q ∴n=q=p,又由(ⅲ)得p p-1|(p-1)p +1=21-p p p-1-…+p 2展开式仅有4项∴n=p=3。故满足条件的所有的正整数对为(p,n)=(p,1)、(2,2)、(3,3)。 例8. 已知p 为奇素数.证明：)(mod 2 )1(21112p p p k p k p +≡∑-=-. 证明：∵p-1为偶数∴∑∑-=---=--+=211 12121112])([p k p p p k p k p k k ，∵k 2p-1+(p-k)2p-1=22122211212-----++?-p p p p p C k p C p 22221222112-----?++?p p p p p k p C k p C ，∴k 2p-1+(p-k)2p-1≡22112--?p p k p C ≡p(2p -1)k 2p-2(modp 2),由Fermat 定理知k p-1≡ 1(modp)，∴(2p-1)k 2p-2≡2p -1≡-1(modp)即(2p-1)k 2p-2=pm-1，∴p(2p-1)k 2p-2≡p 2m-p≡-p(modp 2)，∴ )(2111112p k p k p k p ≡-≡∑∑-=-=- )(mod 2 )1(2)1(2)1()(222111112p p p p p p p p p k p k p k p +≡--≡-- ≡-≡∑∑-=-=- 练习题 1. 求所有的素数对(x,y)满足x y -y x =xy 2-19. 解：∵x y =y x +xy 2-19及Fermat 定理x y ≡x(mody)，∴x y ≡x≡-19(mody)∴y|x+19,同理x|y-19,xy|(x+19)(y- 19),即xy|19(y-x-19)∴xy|y-x-19.(ⅰ)当x=2时,2y =3y 2-19,由y|x+19=21得y=3,7,检验知(2,3)和(2,7)都是解.(ⅱ)当y=2时,x 2=2x +4x-19,且x|(-17)∴x=17检验知(17,2)非解.(ⅲ)当x≥3时,当y≥3时,由xy|y-x-19及y≤x+19得:3x≤xy≤x+19-y≤x+16即3x≤x+16∴x≤8,x=3,5,7.此时,由y|x+19=22,24,26得y=11,3,13不满足x|y-19,非解.∴满足x y -y x =xy 2-19的所有素数对(x,y)=(2,3)和(2,7). 2. 证明：不存在非负整数k 和m,使得k!+48=48(k+1)m . 证明：k=0,m=0显然不是解.下设k,m 为正整数.10.若k+1为合数,则k+1|k!, k+1|48∵48|k!∴k≥6, k=7,11,23,47检验知都不是解.20.若k+1为素数,由Wilson 定理知k!≡-1(modk+1),即k+1|k!+1，∵k!+48= 48(k+1)m ∴k+1|47,k=46.方程为46!+48=48?47m 即148 !46+=47m ,取mod4得1≡(-1)m (mod4)∴m 为偶数,令m=2m 1.则有)147)(147(11-+m m = 48!46∵232|48!46,)23(m od 21471≡+m ，∴232|1471-m ，∵11)146(47m m +=≡46m 1+1(mod232)， ∴232|1471-m ?232|46m 1?23|m 1∴m=2m 1≥46,故有46!+48<48?47m .综上所述,不存在非负整数k 和m,使得k!+48=48(k+1)m . 3. 已知p 是一个大于5的素数.求证:至少存在两个不同的正整数q 1,q 2满足:(ⅰ)1≤q 1,q 2≤p -1; (ⅱ)q i p-1≡ 1(modp 2)(i=1,2). 证明：引理:若a b ?1(modc),则必存在素数q|a 且q b ≡1(modc).证明原题:由二项式定理可知(p-1)p-1, (p+1)p-1, (2p-1)p-1, (2p+1)p-1这四个数在modp 2下的余数均不为1∴存在q 1|p-1且q 1p-1≡1(modp 2).(ⅰ)若q 1≠2,则令q 2=2,易知q 2|p+1,且q 2p-1≡1(modp 2), q 1,q 2即为所求.(ⅱ)若q 1=2,则由2p-1, 2p+1中必有一数被3整除,可令q 2=3,则必有q 2|2p-1或2p+1,且q 2p-1≡1(modp 2)得证. 4. 证明,对于每一个素数p,总存在无穷多个正整数n 使得p|2n -n. 证明：若p=2,则n 取任意偶数,结论成立;若p>2,则由Fermat 定理得2p-1≡1(modp),令n=(mp-1)(p-1),m 为任意正整数,则n≡1(modp),2n ≡1(modp)∴2n -n≡0(modp),即有p|2n -n.故结论成立. 5. 已知k 为正整数,k≥2, p 1,p 2,…,p k 为奇素数,且(a,p 1p 2…p k )=1.证明a )1()1)(1(21---k p p p -1有不同于p 1,p 2,…,p k 的奇素数因数. 证明：∵(a,p 1p 2…p k )=1∴(a,p 1)=1, 由Fermat 定理得:)(mod 1111p a p ≡-,又 2 )1()1)(1(32---k p p p 为正整数，∴)(mod 112)1()1)(1(21p a k p p p ≡--- 即1|2) 1()1)(1(121----k p p p a p ,同理得1|,,,2) 1()1)(1(3221----k p p p k a p p p ,∵2)1()1)(1(21---k p p p 为偶数∴(mod 102 )1()1)(1(21或≡---k p p p a )4(mod 102) 1()1)(12或≡---k p p ，且4?12)1()1)(1(21+---k p p p a ,即12)1()1)(1(21+---k p p p a 有异于p 1,p 2,…,p k 的奇素数因数∴]1][1[12 ) 1()1)(1(2) 1()1)(1()1()1)(1(212121+-=----------k k k p p p p p p p p p a a a 有异于p 1,p 2,…,p k 的奇素数因数. 6. 已知p 为素数.证明,存在一个素数q,使得对任意正整数n,q ?n p -p. 证明：∵)(mod 1111221p p p p p p p p p +≡++++=--- ，∴1 1--p p p 中至少有一个素因子q 满足q ?1(modp 2).若存在正整数n 使得n p ≡p(modq),则有)(mod 12q p n p p ≡≡(∵p|p p -1),由Fermat 定理得: n q-1≡1(modq)及p 2?q-1,(p 2,q-1)|p(∵(p 2,q-1)=1或p)，∴n p ≡1(modq)∵n p ≡p(modq)∴p≡1(modq) ∴1+p+p 2+…+p p-1≡p(modq)，∵q 是1+p+p 2+…+p p-1的一个质因子∴p≡0(modq)与p≡1(modq)矛盾! 7. 设正整数a,b,c,d,m,n 满足:a+b+c+d=m 2, a 2+b 2+c 2+d 2=1989,且其中a,b,c,d 的最大者为n 2.试求m,n 的值. 解:显然,a,b,c,d 不全为偶数(1奇或3奇),从而m 为奇数.∵m 2=a+b+c+d 1989 2)(42222=+++≤d c b a 19892)22=+d c <90,∴m 2只能取{12,32,52,72,92},∵(a+b+c+d)2>a 2+b 2+c 2+d 2=1989∴m 2>1989 即m 2≥45∴m 2 =49或81.若m 2=49即a+b+c+d=49.∵a,b,c,d 的最大者为d=n 2∴4n 4≥a 2+b 2+c 2+d 2=1989∴n≥5,∵a+b+c= 49-n 2∴5≤n≤6即n=5或6,d=25或36.a+b+c=24或13, a 2+b 2+c 2 =1364或693,∵(a+b+c)2=242=576>a 2+ b 2+ c 2或(a+b+c)2=132=169>a 2+b 2+c 2 ,∴此时方程无解.∴m 2=a+b+c+n 2=81, a 2+b 2+c 2+n 4=1989,∵4n 2≥81 ∴n≥5∵1989-n 4≥3即n 4≤1992∴5≤n≤6即n=5或6. 当n=5时,a+b+c=56,a 2+b 2+c 2 =1364,∵4|1364=a 2+ b 2+c 2∴a,b,c 均为偶数:a=2a 1,b=2b 1,c=2c 1且a 12+b 12+c 12 =341, a 1+b 1+c 1=28∵a 12+b 12+c 12 =341≡1(mod4) ∴a 1,b 1,c 1必定两个偶数一个奇数: a 1=2a 2,b 1=2b 2,c 1=2k-1且2(a 2+b 2+k)=29矛盾!当n=6时,a+b+c=45,a 2+ b 2+c 2 =693,∵693≡1(mod4)∴a=2a 1,b=2b 1,c=2k-1且a 1+b 1+k=23,a 12+b 12+k(k-1) =173,∵k(k-1)为偶数∴a 1,b 1一奇一偶: a 1=2a 2,b 1=2r-1且2a 2+2r+k=24,4a 22+4r(r-1)+k(k-1) =172∴2|k,4|k(k-1)∴4|k,又 ∵173-k(k-1) =2)23(2)(2 2112 121k b a b a -=+≥+,即有k 2-16k+61≤0∴7≤k≤9,∵4|k ∴k=8,a 2+r=8,a 22+ r(r-1)=29,消去a 2得2r 2-17r+35=0,解得r=5,(a,b,c,d)=(12,18,15,36)∴m 2=81,n 2=36,(m,n)=(9,6). 8. 求方程2x ?3y -5z ?7w =1的所有非负整数解(x,y,z,w). 解:(1)若y=0,则2x -5z ?7w =1,当z≠0时, 2x ≡1(mod5)∵24≡1(mod5)∴4|x,从而3|2x -1=5z ?7w ,这不可能∴z=0, 2x -7w =1,当x=1,2,3时,(x,w)=(1,0),(3,1);当x≥4时, 7w =2x -1≡-1(mod16),但当w 为偶数时7w ≡ 1(mod16),当w 为奇数时7w ≡7(mod16),矛盾.∴这时解为(1,0,0,0),(3,0,0,1);(2)若y>0.①当x=1时,2?3y - 5z ?7w =1,则5z ?7w ≡-1(mod3),即(-1)z ≡-1(mod3)∴z 为奇数∴2?3y ≡1(mod5)∵34≡1(mod5),∴y≡1(mod4)即y=4m+1.当w≠0时, 2?3y ≡1(mod7)∵36≡1(mod7)∴y≡4(mod6),y=6n+4=4m+1,即6n=4m-3矛盾∴必有w=0, 2?3y -5z =1,当y=1时,z=1;当y≥2时,5z ≡-1(mod9)∵56≡1(mod9)∴z≡3(mod6),53+1|5z +1,7|5z +1=2?3y 矛盾! ∴这时解为(1,1,1,0),②当x≥2时,∵5z ?7w ≡-1(mod4),5z ?7w ≡-1(mod3)即(-1)w ≡-1(mod4),(-1)z ≡-1(mod3)∴w,z 都是奇数,2x ?3y =5z ?7w +1≡35+1≡4(mod8),∴x=2,y=2k,方程为4?3y -5z ?7w =1∴4?3y ≡1(mod5),y≡2(mod4), 4?3y ≡1(mod7),y≡2(mod6)∴y≡2(mod12),设y=12m+2(m≥0),则5z ?7w =4?312m+2-1=(2?36m+1-1)(2?36m+1+1) ∵2?36m+1+1≡0(mod7),(2?36m+1-1,2?36m+1+1)=1∴5|2?36m+1-1,∴?????=+?=-?++w m z m 713251321616,若m≥1,则5z ≡ -1(mod9),由①的证明知不可能.若m=0,则y=2,?? ???=+?=-?w z 71325132得z=w=1,得解(2,2,1,1).故原方程的所有解为:(x,y,z,w)=(1,0,0,0),(3,0,0,1),(1,1,1,0),(2,2,1,1). 9. 求方程5x +1=2y +2z ?5t 的所有正整数解(x,y,z,t). 解:设(x,y,z,t)是方程的正整数解,则2y ≡1(mod5)∵24≡1(mod5)∴4|y,对方程两边mod4得2z ≡2(mod4)∴z=1.设y=4r,得5x +1=24r +2?5t 即5x -2?5t =16r -1,两边mod3得:(-1)x +(-1)t ≡0(mod3)∴x,t 一奇一偶∵5t ≡1或5(mod8)∴对5x =2?5t +16r -1,两边mod8得: 5x ≡2?5t -1≡1(mod8)∴x 为偶数,t 为奇数.(1)若t=1,则5x =16r +9,设x=2m,则(5m -3)(5m +3)=16r .∵(5m -3,5m +3)=(5m -3,6)=2∴5m -3=2,5m +3=24r-1,∴m=1,24r-1=23 ∴r=1,y=4,x=2,得解(x,y,z,t)=(2,4,1,1);(2)若t>1,则t≥3,x≥4,53|5x -2?5t =16r -1∵16r -1=(15+1)r =15r +…+ 2215?r C +151?r C ∴5|r,令r=5k,则165k -1≡55k -1≡(5?32)k -1≡0(mod11),∴11|5x -2?5t =5t (5x-t -2),即11|5x-t -2,但5n ≡1,3,4,5,9(mod11),即11?5x-t -2,矛盾!故原方程有唯一解(x,y,z,t)=(2,4,1,1). 27同余 1．设m 是一个给定的正整数，如果两个整数a 与b 用m 除所得的余数相同，则称a 与b 对模同余，记作，否则，就说a 与b 对模m 不同余，记作，显然，； 每一个整数a 恰与1，2，……，m ，这m 个数中的某一个同余； 2.同余的性质： 1).反身性：； 2).对称性：； 3).若，则; 4).若，，则 特别是； 5).若，，则； 特别是 ； 6).； 7).若 ； 8).若， ……………… ，且 例题讲解 1．证明：完全平方数模4同余于0或1； 2．证明对于任何整数,能被7整除； )(mod m b a ≡)(mod m b a ≡)(|)(,)(mod b a m Z k b km a m b a -?∈+=?≡)(mod m a a ≡)(mod )(mod m a b m b a ≡?≡)(mod m b a ≡)(mod m c b ≡)(mod m c a ≡)(m od 11m b a ≡)(m od 22m b a ≡)(m od 2121m b b a a ±≡±)(mod )(mod m k b k a m b a ±≡±?≡)(m od 11m b a ≡)(m od 22m b a ≡)(m od 2121m b b a a ≡)(m od ),(m od m bk ak Z k m b a ≡?∈≡则)(m od ),(m od m b a N n m b a n n ≡?∈≡则)(mod )(m ac ab c b a +≡+)(m od 1),(),(m od m b a m c m bc ac ≡=≡时，则当)(mod )(mod ).(mod ),(m b a mc bc ac d m b a d m c ≡?≡≡=特别地，时，当)(m od 1m b a ≡)(m od 2m b a ≡)(mod 3m b a ≡)(mod n m b a ≡)(m od ],,[21M b a m m m M n ≡??=，则0≥k 153261616+++++k k k 全国高中数学联合竞赛试题（A 卷） 一试 一、填空题（本大题共8小题，每小题8分，共64分） 1. 若正数,a b 满足()2362log 3log log a b a b +=+=+，则11 a b +的值为________． 答案：设连等式值为k ，则2 3 2 ,3 ,6k k k a b a b --==+=，可得答案108 分析：对数式恒等变形问题，集训队讲义专门训练并重点强调过 2. 设集合3|12b a b a ?? +≤≤≤????中的最大元素与最小你别为,M m ，则M m -的值为______． 答案：33251b a +≤+= ，33 b a a a +≥+≥ ，均能取到，故答案为5-分析：简单最值问题，与均值、对勾函数、放缩有关，集训队讲义上有类似题 3. 若函数()21f x x a x =+-在[0,)+∞上单调递增，则实数a 的取值范围是______． 答案：零点分类讨论去绝对值，答案[]2,0- 分析：含绝对值的函数单调性问题，集训队讲义专门训练并重点强调过 4. 数列{}n a 满足12a =，()()*1221n n n a a n N n ++=∈+，则 2014 122013a a a a =+++______． 答案：()1221 n n n a a n ++=+，迭乘得()121n n a n -=+，()212232421n n S n -=+?+?+++， 乘以公比错位相减，得2n n S n =，故答案为2015 2013 ． 分析：迭乘法求通项，等差等比乘积求前n 项和，集训队讲义专门训练并重点强调过 5. 正四棱锥P ABCD -中，侧面是边长为1的正三角形，,M N 分别是边,AB BC 的中点，则异面直线MN 与PC 之间的距离是 ________． 答案：OB 为公垂线方向向量，故距离为12OB =分析：异面直线距离，也可以用向量法做，集训队讲义专门练并重点强调过 6. 设椭圆Γ的两个焦点是12,F F ，过点1F 的直线与Γ交于点,P Q ．若212PF F F =，且1134PF QF =，则 椭圆Γ的短轴与长轴的比值为________． 答案：不妨设焦点在x 轴（画图方便），设114,3PF QF ==，焦距为2c ，224a c =+， 可得△2PQF 三边长为7,21,2c c + ，过2F 作高，利用勾股可得5c =． 分析：椭圆中常规计算，与勾股定理、解三角形、斯特瓦尔特等有关，集训队讲义训练过相关 7. 设等边三角形ABC 的内切圆半径为2，圆心为I ．若点P 满足1PI =，则△APB 与△APC 的面积之 比的最大值为________． 答案：sin sin APB APC S PAB S PAC ∠=∠，又两角和为60 最大，即AP 与 (),1I 切于对称轴右侧 2 分析：平面几何最值、面积、三角函数、轨迹 2018年全国高中数学联合竞赛一试试题（A 卷） 一、填空题：本大题共 8小题，每小题 8分，共64分． 1.设集合{1,2,3,,99}A = ，{2}B x x A =∈，{2}B x x A =∈，则B C 的元素个数 . 解析：因为{1,2,3,,99}A = ，所以{2,4,6,,198}B = ,{1,2,3,,49}C = ,于是 {2,4,6,,48}B C = ，共24个元素. 2.设点P 到平面α Q 在平面α上，使得直线PQ 与α所成角不小于30 且不大于60 ，则这样的点Q 所构成的区域的面积为 . 解析：过点P 作平面α的垂线，这垂足为O ，则点Q 的轨迹是以O 为圆心，分别以1ON =和3OM =为半径的扇环,于是点Q 所构成的区域的面积为21S S S =-= 9 8πππ-=. 3. 将1,2,3,4,5,6随机排成一行，记为,,,,,a b c d e f ，则abc def +是偶数的概率为 . 解析：（直接法）将1,2,3,4,5,6随机排成一行，共有6 6720A =种不同的排法，要使 abc def +为偶数，abc 为与def 同为偶数或abc 与且def 同为奇数. （1）若,,a b c 中一个偶数两个奇数且,,d e f 中一个奇数两个偶数. 共324种情形； （2）若,,a b c 中一个奇数两个偶数且,,d e f 中一个偶数两个奇数. 共324种情形； 共有648种情形.综上所述，abc def +是偶数的概率为 6489 72010 =. （间接法）“abc def +是偶数”的对立事件为“abc def +是偶数”， abc def +是偶数分成两种情况：“abc 是偶数且def 是奇数”或“abc 是奇数且def 是偶数”，每 P O M N α 高中数学竞赛专题讲座：三角函数与向量 一、三角函数部分 1．(集训试题)在△ABC 中，角A 、B 、C 的对边分别记为a 、b 、c(b ≠1)，且 A C ， A B sin sin 都是方程log b x=log b (4x-4)的根，则△ABC （B ） A ．是等腰三角形，但不是直角三角形 B ．是直角三角形，但不是等腰三角形 C ．是等腰直角三角形 D ．不是等腰三角形，也不是直角三角形 解：由log b x=log b (4x-4)得：x 2-4x+4=0，所以x 1=x 2=2，故C=2A ，sinB=2sinA ， 因A+B+C=180°，所以3A+B=180°，因此sinB=sin3A ，∴3sinA-4sin 3A=2sinA ， ∵sinA(1-4sin 2A)=0，又sinA ≠0，所以sin 2A= 41，而sinA>0，∴sinA=2 1. 因此A=30°,B=90°,C=60°。故选B 。 2．（2006吉林预赛）已知函数y=sinx+acosx 的图象关于x=5π/3对称，则函数y=asinx+cosx 的图象的一条对称轴是（C ） A ．x=π/3 B ．x=2π/3 C ．x=11π/6 D ．x=π 3．2006年南昌市）若三角形的三条高线长分别为12,15,20,则此三角形的形状为( B ) A ．锐角三角形 B ．直角三角形 C ．钝角三角形 D ．形状不确定 4．（2006年南昌市）若sin tan a θθ=+,cos cot b θθ=+,则以下诸式中错误的是( B ) A ．sin θ= 11+-b ab B ．cos θ=1 1+-a ab C ．tan cot θθ+=) 1)(1(21)1(2++-+++b a ab b a D ．tan cot θθ-=)1)(1()2)((++++-b a b a b a 5．（2006安徽初赛）已知△ABC 为等腰直角三角形，∠C = 90°，D 、E 为AB 边上的两个点，且点D 在AE 之间， ∠DCE = 45°，则以AD 、DE 、EB 为边长构成的三角形的最大角是 （ ） A ．锐角 B ．钝角 C ．直角 D ．不能确定 6．（2006陕西赛区预赛）若3 3sin cos cos sin ,02θθθθθπ-≥-≤<，则角θ的取值范围是(C) A ．[0, ]4 π B ．[,]4 ππ C ．5[, ]4 4ππ D ．3[,)42 ππ 7．（2006年江苏）在△ABC 中，1tan 2A =，310 cos 10 B =．若△AB C 的最长边为1，则最短边的长为 （ D ） A ．455 B ．355 C ．255 D ．5 5 8．(2005年浙江)设2)(1=x f ，x x x f 2cos sin )(2+=，x x x f 2cos 2 sin )(3+=，24sin )(x x f =，上述函数中，周期函数的个数是（ B ） A ．1 B ．2 C ．3 D ．4 【解】： 2)(1= x f 是以任何正实数为周期的周期函数；)(2x f 不是周期函数。 因为x sin 是以π21=T 为周期 的周期函数, x 2cos 是以222π =T 为周期的周期函数, 而1T 与2T 之比不是有理数，故)(2x f 不是周期函数。 )(3x f 不是周期函数。 因为2sin x 是以π221=T 为周期的周期函数, x 2cos 是以2 22π =T 为周期的周期函数, 高中数学竞赛中数论问题的常用方法 数论是研究数的性质的一门科学,它与中学数学教育有密切的联系.数论问题解法灵活,题型丰富,它是中学数学竞赛试题的源泉之一.下面介绍数论试题的常用方法. 1.基本原理 为了使用方便,我们将数论中的一些概念和结论摘录如下: 我们用),...,,(21n a a a 表示整数1a ,2a ,…,n a 的最大公约数.用[1a ,2a ,…,n a ]表示1a ,2a ,…,n a 的 最小公倍数.对于实数x ,用[x ]表示不超过x 的最大整数,用{x }=x -[x ]表示x 的小数部分.对于整数 b a ,,若)(|b a m -,,1≥m 则称b a ,关于模m 同余,记为)(mod m b a ≡.对于正整数m ,用)(m ?表示 {1,2,…,m }中与m 互质的整数的个数,并称)(m ?为欧拉函数.对于正整数m ,若整数m r r r ,...,,21中任何两个数对模m 均不同余,则称{m r r r ,...,,21}为模m 的一个完全剩余系；若整数)(21,...,,m r r r ?中每一个数都与m 互质,且其中任何两个数关于模m 不同余,则称{)(21,...,,m r r r ?}为模m 的简化剩余系. 定理1 设b a ,的最大公约数为d ,则存在整数y x ,,使得yb xa d +=. 定理2(1)若)(mod m b a i i ≡,1=i ,2,…,n ,)(m od 21m x x =,则 1 1n i i i a x =∑≡2 1 n i i i b x =∑； (2)若)(mod m b a ≡,),(b a d =,m d |,则 )(mod d m d b d a ≡； (3)若b a ≡,),(b a d =,且1),(=m d ,则)(mod m d b d a ≡； (4)若b a ≡(i m mod ),n i ,...,2,1=,M=[n m m m ,...,,21],则b a ≡(M mod ). 定理3(1)1][][1+<≤<-x x x x ； (2)][][][y x y x +≥+； (3)设p 为素数,则在!n 质因数分解中,p 的指数为 ∑≥1 k k p n . 定理4 (1)若{m r r r ,...,,21}是模m 的完全剩余系,1),(=m a ,则{b ar b ar b ar m +++,...,,21}也是模 m 的完全剩余系； (2)若{)(21,...,,m r r r ?}是模m 的简化剩余系,1),(=m a ,则{)(21...,,m ar ar ar ?}是模m 的简化剩余系. 定理5(1)若1),(=n m ,则)()()(n m mn ???=. (2)若n 的标准分解式为k k p p p n ααα (2) 121=,其中k ααα,...,21为正整数,k p p p ,...,21为互不相 高中数学竞赛介绍，尖子生请收好！ 首先，强调一点：不是所有学生都可以学数学竞赛，要想学习数学竞赛必须同时具备以下条件： ?高考数学可以轻松应对； ?对数学竞赛有兴趣，自发选择学习数学竞赛； ?具备自主学习能力； ?高考涉及的其他学科不存在太大问题，或个人的竞赛前景远优于高考前景。 数学竞赛需要的时间和精力都是很大的，并且如果因为学习竞赛受挫而导致对数学产生负情绪是得不偿失的，因此，我从不提倡“全民竞赛”。当然，如果你恰好符合以上的四个条件，那么你一定要学习竞赛。为什么？因为学习数学竞赛的好处很多。 与其他学科竞赛一样，学习数学竞赛除了能在升入高校方面获得保送或降分的优惠外，还能培养学生的自主学习能力，这对学生的整个大学学习乃至今后的学术研究或是社会工作是尤为重要的。 因此，若你有足够的实力，精力和时间，那么竞赛将是你们的不二之选。 此外，数学竞赛学到一定深度后就会发现，数学竞赛不再是由知识结构和解题方法组成，而是对思维能力的培养和运用，而思维能力的价值是远超过数学本身的，这将会对学生以后对问题的思考与对事物的判断等产生不可估量的影响。当然，这是后话。 说归说，高中数学竞赛指的究竟是什么？我想说的是，绝不仅仅是高联（全国高中数学联赛）这么简单。下面，我就带着大家理一理高中阶段可能会遇到的竞赛。 1. 全国高中数学联赛 全国高中数学联赛旨在选拔在数学方面有突出特长的同学，让他们进入全国知名高等学府，而且选拔成绩比较优异的同学进入更高级别的竞赛，直至国际数学奥林匹克（IMO）。并且通过竞赛的方式，培养中学生对于数学的 兴趣，让学生们爱好数学，学习数学，激发学生们的钻研精神，独立思考精神以及合作精神。 2.中国数学奥林匹克（CMO） CMO考试完全模拟IMO进行，每天3道题，限四个半小时完成。每题21分（为IMO试题的3倍，为符合中国人的认知习惯），6个题满分为126分。颁奖与IMO类似，设立一、二、三等奖，分数最高的约前60名选手将组成参加当年国际数学奥林匹克（International Mathematical Olympiad,简称IMO）的中国国家集训队。 3.国际数学奥林匹克（IMO） 国际数学奥林匹克(International Mathematical Olympiad，简称IMO)是世界上规模和影响最大的中学生数学学科竞赛活动。 正如专家们指出：IMO的重大意义之一是促进创造性的思维训练，对于科学技术迅速发展的今天，这种训练尤为重要。数学不仅要教会学生运算技巧，更重要的是培养学生有严密的思维逻辑，有灵活的分析和解决问题的方法。 根据我的感觉，如果高考的数学难度有两星，那么高联的一试难度大概有三颗星，二试难度大概有四颗星；而CMO和IMO的难度大概在五颗星左右。因此，参加高中竞赛的确 2009年全国高中数学联赛试题及答案 全国高中数学联赛 全国高中数学联赛一试命题范围不超出教育部《全日制普通高级中学数学教学大纲》中所规定的教学要求和内容，但在方法的要求上有所提高。主要考查学生对基础知识和基本技能的掌握情况，以及综合和灵活运用的能力。 全国高中数学联赛加试命题范围与国际数学奥林匹克接轨，在知识方面有所扩展，适当增加一些竞赛教学大纲的内容。全卷包括4道大题，其中一道平面几何题. 一 试 一、填空（每小题7分，共56分） 1． 若函数( )f x = ()()()n n f x f f f f x ??=??????，则() ()991f = ． 2． 已知直线:90L x y +-=和圆22:228810M x y x y +---=，点A 在直线L 上，B ，C 为圆M 上两点，在ABC ?中，45BAC ∠=?，AB 过圆心M ，则点A 横 坐标范围为 ． 3． 在坐标平面上有两个区域M 和N ，M 为02y y x y x ?? ??-? ≥≤≤，N 是随t 变化的区 域，它由不等式1t x t +≤≤所确定，t 的取值范围是01t ≤≤，则M 和N 的公共面积是函数()f t = ． 4． 使不等式 1111 200712 213 a n n n +++ <-+++对一切正整数n 都成立的最小正整数a 的值为 ． 5． 椭圆22 221x y a b +=()0a b >>上任意两点P ，Q ，若OP OQ ⊥，则乘积 OP OQ ?的最小值为 ． 6． 若方程()lg 2lg 1kx x =+仅有一个实根，那么k 的取值范围是 ． 7． 一个由若干行数字组成的数表，从第二行起每一行中的数字均等于其肩 上的两个数之和，最后一行仅有一个数，第一行是前100个正整数按从小到大排成的行，则最后一行的数是 （可以用指数表示） 8． 某车站每天800~900∶∶，900~1000∶∶都恰有一辆客车到站，但到站的时 金牌学生推荐（可参照选择） 一、第零阶段：知识拓展 《数学选修4-1：几何证明选讲》 《数学选修4-5：不等式选讲》 《数学选修4-6：初等数论初步》 二、全国高中数学联赛各省赛区预赛（即省选初赛） 1、《五年高考三年模拟》B版或《3年高考2年模拟》第二轮复习专用 2、《高中数学联赛备考手册》华东师范大学出版社（推荐指数五颗星） 3、《奥赛经典：超级训练系列》高中数学沈文选主编湖南师范大学出版社（推荐指数五颗星） 4、单樽《解题研究》（推荐指数五颗星） 5、单樽《平面几何中的小花》（个别地区竞赛会考到平几） 6、《平面几何》浙江大学出版社 7、奥林匹克小丛书第二版《不等式的解题方法与技巧》苏勇熊斌著 三、第二阶段：全国高中数学联赛 一试 0、《奥林匹克数学中的真题分析》沈文选湖南师范大学出版社（推荐指数五颗星） 1、《高中数学联赛考前辅导》熊斌冯志刚华东师范大学出版社 2、《数学竞赛培优教程（一试）》浙江大学出版社 3、命题人讲座《数列与数学归纳法》单樽 4、《数列与数学归纳法》（小丛书第二版，冯志刚） 5、《数列与归纳法》浙江大学出版社韦吉珠 6、《解析几何的技巧》单樽（建议买华东师大出版的版本） 7、《概率与期望》单樽 8、《同中学生谈排列组合》苏淳 9、《函数与函数方程》奥林匹克小丛书第二版 10、《三角函数》奥林匹克小丛书第二版 11、《奥林匹克数学中的几何问题》沈文选（推荐指数五颗星） 12、《圆锥曲线的几何性质》 13、《解析几何》浙江大学出版社 二试 平几 1、高中数学竞赛解题策略(几何分册)沈文选（推荐指数五颗星） 2、《奥林匹克数学中的几何问题》沈文选（推荐指数五颗星） 3、奥林匹克小丛书第二版《平面几何》 4、浙大小红皮《平面几何》 5、沈文选《三角形的五心》 6、田廷彦《三角与几何》 7、田廷彦《面积与面积方法》 不等式 8、《初等不等式的证明方法》韩神 9、命题人讲座《代数不等式》计神 10、《重要不等式》中科大出版社 11、奥林匹克小丛书《柯西不等式与平均值不等式》 数论 （9,10，11选一本即可，某位大神说二试改为四道题以来没出过难题） 12、奥林匹克小丛书初中版《整除，同余与不定方程》 13、奥林匹克小丛书《数论》 14、命题人讲座《初等数论》冯志刚 组合 15、奥林匹克小丛书第二版《组合数学》 16、奥林匹克小丛书第二版《组合几何》 17、命题人讲座刘培杰《组合问题》 18、《构造法解题》余红兵 19、《从特殊性看问题》中科大出版社 20、《抽屉原则》常庚哲 四、中国数学奥林匹克（Chinese Mathematical Olympiad）及以上 命题人讲座《圆》田廷彦 《近代欧式几何学》 《近代的三角形的几何学》 《不等式的秘密》范建熊、隋振林 《奥赛经典：奥林匹克数学中的数论问题》沈文选 《奥赛经典：数学奥林匹克高级教程》叶军 《初等数论难题集》 命题人讲座《图论》 奥林匹克小丛书第二版《图论》 《走向IMO》 数学竞赛训练题 1、函数()x x x x x f 44cos cos sin sin ++=的最大值是_______。 2、已知S n 、T n 分别是等差数列{}n a 与{}n b 的前n 项的和，且2412-+=n n T S n n ，则=+++15 61118310b b a b b a _______。 3、若函数()?? ? ?? +=x a x x f a 4log 在区间上为增函数，则a 的取值范围是为_______。 4、在四面体ABCD 中，已知DA ⊥平面ABC ，△ABC 是边长为2的正三角形，则当二面角A-BD-C 的正切值为2时，四面体ABCD 的体积为_______。 5、已知定义在R 上的函数()x f 满足： （1）()11=f ； （2）当10< 高中数学竞赛训练题—填空题 1. 若不等式1-log a )10(x a -＜0有解，则实数a 的范围是 . 2．设()f x 是定义在Ｒ上的奇函数，且满足(2)()f x f x +=-；又当01x ≤≤时， 1()2 f x x = ，则方程21 )(-=x f 的解集为 。 3.设200221,,,a a a Λ均为正实数，且 2 1 212121200221=++++++a a a Λ，则200221a a a ???Λ的最小值为____________________. 4. ,x R ∈ 函数()2sin 3cos 23 x x f x =+的最小正周期为 . 5. 设P 是圆2 2 36x y +=上一动点，A 点坐标为()20,0。当P 在圆上运动时，线段PA 的中点M 的轨迹方程为 . 6.. 设z 是虚数，1 w z z =+ ，且12w -<<，则z 的实部取值范围为 . 7. 设4 4 2 )1()1()(x x x x k x f --+-=。如果对任何]1,0[∈x ，都有0)(≥x f ，则k 的最小值为 . 8．＝ 。 9．设lg lg lg 111()121418x x x f x = +++++，则 1 ()()_________f x f x +=。 10．设集合{}1215S =L ，，，，{}123A a a a =，，是S 的子集，且()123a a a ，，满足： 123115a a a ≤≤<<，326a a -≤，那么满足条件的集合A 的个数为 ． 11．已知数列}{n a 满足,01=a ),2,1(1211Λ=+++=+n a a a n n n ，则n a =___ . 12．已知坐标平面上三点()()) 0,3,,A B C ，P 是坐标平面上的点，且 PA PB PC =+，则P 点的轨迹方程为 ． 13.已知0 2sin 2sin 5=α，则) 1tan() 1tan(00-+αα的值是______________. 14.乒乓球比赛采用7局4胜制，若甲、乙两人实力相当，获胜的概率各占一半，则打完5局后仍不能结束比赛的概率等于_____________. 15.不等式 92) 211(42 2 +<+-x x x 的解集为_______________________. 1988年全国高中数学联赛试题 第一试(10月16日上午8∶00——9∶30) 一．选择题(本大题共5小题，每小题有一个正确答案，选对得7分，选错、不选或多选均得0分)： 1．设有三个函数，第一个是y=φ(x )，它的反函数是第二个函数，而第三个函数的图象及第二个函数的图象关于x +y=0对称，那么，第三个函数是( ) A ．y=－φ(x ) B ．y=－φ(－x ) C ．y=－φ－1(x ) D ．y=－φ－ 1(－x ) 2．已知原点在椭圆k 2x 2+y 2－4kx +2ky +k 2－1=0的内部，那么参数k 的取值范围是( ) A ．|k |>1 B ．|k |≠1 C ．－1 高中数学竞赛 数论 剩余类与剩余系 1.剩余类的定义与性质 (1)定义1 设m 为正整数，把全体整数按对模m 的余数分成m 类，相应m 个集合记为：K 0,K 1,…,K m-1,其中K r ={qm+r|q ∈Z,0≤余数r ≤m-1}称为模m 的一个剩余类(也叫同余类)。K 0,K 1,…,K m-1为模m 的全部剩余类. (2)性质(ⅰ)i m i K Z 1 0-≤≤=Y 且K i ∩K j =φ(i ≠j). (ⅱ)每一整数仅在K 0,K 1,…,K m-1一个里. (ⅲ)对任意a 、b ∈Z ，则a 、b ∈K r ?a ≡b(modm). 2.剩余系的定义与性质 (1)定义2 设K 0,K 1,…,K m-1为模m 的全部剩余类，从每个K r 里任取一个a r ，得m 个数a 0,a 1,…,a m-1组成的数组，叫做模m 的一个完全剩余系,简称完系. 特别地,0,1,2,…,m -1叫做模m 的最小非负完全剩余系.下述数组叫做模m 的绝对最小完全剩余系:当m 为奇数时,2 1 ,,1,0,1,,121,21--+----m m m ΛΛ;当m 为偶数时,12 ,,1,0,1,,12,2--+-- m m m ΛΛ或2,,1,0,1,,12m m ΛΛ-+-. (2)性质(ⅰ)m 个整数构成模m 的一完全剩余系?两两对模m 不同余. (ⅱ)若(a,m)=1，则x 与ax+b 同时遍历模m 的完全剩余系. 证明:即证a 0,a 1,…,a m-1与aa 0+b, aa 1+b,…,aa m-1+b 同为模m 的完全剩余系, 因a 0,a 1,…,a m-1为模m 的完系时,若aa i +b ≡aa j +b(modm),则a i ≡a j (modm), 矛盾!反之,当aa 0+b, aa 1+b,…,aa m-1+b 为模m 的完系时,若a i ≡a j (modm),则有 aa i +b ≡aa j +b(modm),也矛盾! §27同余 1．设m 是一个给定的正整数，如果两个整数a 与b 用m 除所得的余数相同，则称a 与b 对模同余，记作)(mod m b a ≡，否则，就说a 与b 对模m 不同余，记作)(mod m b a ≡，显然，)(|)(,)(mod b a m Z k b km a m b a -?∈+=?≡； 每一个整数a 恰与1，2，……，m ，这m 个数中的某一个同余； 2.同余的性质： 1).反身性：)(mod m a a ≡； 2).对称性：)(mod )(mod m a b m b a ≡?≡； 3).若)(mod m b a ≡，)(mod m c b ≡则)(mod m c a ≡; 4).若)(m od 11m b a ≡，)(m od 22m b a ≡，则)(m od 2121m b b a a ±≡± 特别是)(mod )(mod m k b k a m b a ±≡±?≡； 5).若)(m od 11m b a ≡，)(m od 22m b a ≡，则)(m od 2121m b b a a ≡； 特别是)(m od ),(m od m bk ak Z k m b a ≡?∈≡则 )(m od ),(m od m b a N n m b a n n ≡?∈≡则； 6).)(mod )(m ac ab c b a +≡+； 7).若)(m od 1),(),(m od m b a m c m bc ac ≡=≡时，则当 )(mod )(mod ).(mod ),(m b a mc bc ac d m b a d m c ≡?≡≡=特别地，时，当； 8).若)(m o d 1m b a ≡， )(m od 2m b a ≡ )(mod 3m b a ≡ ……………… )(mod n m b a ≡，且)(m od ],,[21M b a m m m M n ≡??=，则 例题讲解 1．证明：完全平方数模4同余于0或1； 2．证明对于任何整数0≥k ,1532 6161 6+++++k k k 能被7整除； 高中数学竞赛集训训练题 1．b a ,是两个不相等的正数，且满足2 2 3 3 b a b a -=-，求所有可能的整数 c ,使得ab c 9=. 2．已知不等式 24 131...312111a n n n n > ++++++++对一切正整数a 均成立，求正整数a 的最大值，并证明你的结论。 3．设{}n a 为14a =的单调递增数列，且满足22 111168()2n n n n n n a a a a a a +++++=++，求{n a } 的通项公式。 4．（1）设,0,0>>y x 求证： ;4 32y x y x x -≥+ （2）设,0,0,0>>>z y x 求证： .2 333zx yz xy x z z z y y y x x ++≥+++++ 5. 设数列ΛΛΛ,1 ,,12, 1,,13,22,31,12,21,11k k k -， 问：（1）这个数列第2010项的值是多少； （2）在这个数列中，第2010个值为1的项的序号是多少. 6. 设有红、黑、白三种颜色的球各10个。现将它们全部放入甲、乙两个袋子中，要求每 个袋子里三种颜色球都有，且甲乙两个袋子中三种颜色球数之积相等。问共有多少种放法。 7．已知数列{}n a 满足1a a =（0,1a a ≠≠且），前n 项和为n S ，且(1)1n n a S a a = --， 记lg ||n n n b a a =（n *∈N ），当a =时，问是否存在正整数m ，使得对于任意正整数n ，都有m n b b ≥？如果存在，求出m 的值；如果不存在，说明理由． 8. 在ABC ?中，已9,sin cos sin AB AC B A C ==u u u r u u u r g ，又ABC ?的面积等于6. （Ⅰ）求ABC ?的三边之长； （Ⅱ）设P 是ABC ?（含边界）内一点，P 到三边AB 、BC 、AB 的距离为1d 、2d 和3d ，求 123d d d ++的取值范围. 9．在数列{}n a 中，1a ，2a 是给定的非零整数，21n n n a a a ++=-． （1）若152a =，161a =-，求2008a ； （2）证明：从{}n a 中一定可以选取无穷多项组成两个不同的常数数列． 10. 已知椭圆)1(12 22>=+a y a x ，Rt ABC ?以A （0，1）为直角顶点，边AB 、BC 与椭圆 交于两点B 、C 。若△ABC 面积的最大值为27 8 ，求a 的值。 竞赛中的数论问题的思考方法 一. 条件的增设 对于一道数论命题，我们往往要首先排除字母取零值或字母取相等值等“平凡”的情况，这样，利用字母的对称性等条件，往往可以就字母间的大小顺序、整除性、互素性等增置新的条件，从而便于运用各种数论特有手段。 1. 大小顺序条件 与实数范围不同，若整数x ，y 有大小顺序x 高中数学竞赛试题 一选择题(每题5分,满分60分) 1. 如果a,b,c 都是实数，那么P ∶ac<0,是q ∶关于x 的方程ax 2 +bx+c=0有一个正根和一个 负根的（ ） （A ）必要而不充分条件 （B ）充要条件 （C ）充分而不必要条件 （D ）既不充分也不必要条件 2. 某种放射性元素，100年后只剩原来质量的一半，现有这种元素1克，3年后剩下（ ）。 （A ） 100 5 .03?克 （B ）(1－0.5%)3克 （C ）0.925克 （D ）100125.0克 3. 由甲城市到乙城市t 分钟的电话费由函数g (t )=1.06×(0.75[t ]+1)给出，其中t >0，[t ]表示 大于或等于t 的最小整数，则从甲城市到乙城市5.5分钟的电话费为（ ）。 （A ）5.83元 （B ）5.25元 （C ）5.56元 （D ）5.04元 4. 已知函数 >0， 则 的值 A 、一定大于零 B 、一定小于零 C 、等于零 D 、正负都有可能 5. 已知数列3，7，11，15，…则113是它的（ ） （A ）第23项 （B ）第24项 （C ）第19项 （D ）第25项 6. 已知等差数列}{n a 的公差不为零，}{n a 中的部分项 ,,,,,321n k k k k a a a a 构成等比数 列，其中,17,5,1321===k k k 则n k k k k ++++ 321等于（ ） (A) 13--n n (B) 13-+n n (C) 13+-n n (D)都不对 7. 已知函数x b x a x f cos sin )(-=（a 、b 为常数，0≠a ，R x ∈）在4 π = x 处取得最小 值，则函数)4 3( x f y -=π 是（ ） A ．偶函数且它的图象关于点)0,(π对称 B ．偶函数且它的图象关于点)0,2 3(π 对称 C ．奇函数且它的图象关于点)0,2 3(π 对称 D ．奇函数且它的图象关于点)0,(π对称 8. 如果 A A tan 1tan 1+-= 4+5，那么cot （A +4 π ）的值等于 ( ) A -4-5 B 4+5 C - 5 41+ D 5 41+ 9. 已知︱︱=1，︱︱=3,?=0,点C 在∠AOB 内，且∠AOC =30°，设 =m +n (m 、n ∈R )，则 n m 等于 高中数学竞赛训练题 一、选择题（仅有一个选择支正确） 1．已知全集}{}{N n n x x B N n n x x A N U ∈==∈===,4,,2,,则（ ） （A ） B A U = (B) )(B A C U U = (C) B C A U U = (D) B C A C U U U = 2．已知b a ,是正实数,则不等式组???>+>+ab xy b a y x 是不等式组? ??>>b y a x 成立的（ ） （A ）充分不必要条件 (B) 必要不充分条件 (C) 充分且必要条件 (D)既不充分又不必要条件 3．等差数列{}n a 中,,336),9(30,1849=>==-n n S n a S 则n 的值是（ ） （A ）8 (B) 9 (C) 16 (D) 21 4．已知复数2 121 -+ =z z w 为纯虚数,则z 的值为（ ） （A ） 1 (B) 21 (C) 31 (D) 不能确定 5．边长为5的菱形,若它的一条对角线的长不大于6,则这个菱形对角线长度之和的最大值是（ ） （A ） 16 (B) 210 (C) 14 (D) 65 6．平面上的整点（横、纵坐标都是整数）到直线5 435+=x y 的距离中的最小值是（ ）（A ） 17034 (B) 8534 (C) 170343 (D) 30 1 7．若232,2,2++x y x x 成等比数列,则点),(y x 在平面直角坐标系内的轨迹是（ ） （A ） 一段圆弧 (B) 一段椭圆弧 (C) 双曲线的一部分 (D) 抛物线的一部分 8．若ABC ?的三边c b a ,,满足：,0322,0222 =+-+=---c b a c b a a 则它的最大内角的度数是（ ） （A ） 0150 (B) 0120 (C) 090 (D) 060高中数学竞赛专题精讲27同余(含答案)
2019年全国高中数学联赛试题及解答
2018全国高中数学联赛试题
高中数学竞赛专题讲座：三角函数与向量
高中数学竞赛中数论问题的常用方法
高中数学竞赛介绍,尖子生请收好
全国高中数学联赛试题及答案教程文件
【数学竞赛各阶段书籍推荐】
高中数学竞赛训练题(0530)
高中数学竞赛训练题—填空题
历年全国高中数学联赛试题及答案
高中数学竞赛数论
高中数学竞赛讲义-同余
高中数学竞赛集训训练题
高中数学竞赛专题讲座---竞赛中的数论问题
高中数学竞赛试题附详细答案
高中数学竞赛训练题 (3)
相关主题
文本预览