高中数学竞赛 数论
剩余类与剩余系
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),也矛盾!
(ⅲ)设m1,m2是两个互质的正整数,而x,y分别遍历模m1,m2的完系,则m2x+m1y历遍模m1m2的完系.
证明:因x,y分别历遍m1,m2个整数,所以,m2x+m1y历遍m1m2个整数.
假定m2x/+m1y/≡m2x//+m1y//(modm1m2),其中x/,x//是x经历的完系中的数,而y/,y//是y经历的完系中的数.因(m1,m2)=1,所以,m2x/≡m2x//(modm1),m1y/≡m1y// (modm2),从而x/≡x//(modm1),y/≡y//(modm2),矛盾!
3.既约剩余系的定义与性质
(1)定义3如果剩余类K r里的每一个数都与m互质，则K r叫与m互质的剩余类.在与模m互质的全部剩余类中，从每一类中任取一个数所做成的数组，叫做模m的一个既约(简化)剩余系.如:模5的简系1,2,3,4;模12的简系1,5,7,11.
(2)性质(ⅰ)K r与模m互质?K r中有一个数与m互质；
证明:设a∈K r,(m,a)=1,则对任意b∈K r,因a≡b≡r(modm),所以,(m,a)=(m,r)=
(m,b)=1,即K r与模m互质.
(ⅱ)与模m互质的剩余类的个数等于)m(?,即模m的一个既约剩余系由m
(?个整数组成()m(?为欧拉函数);
)
(ⅲ)若(a,m)=1,则x与ax同时遍历模m的既约剩余系.
证明:因(a,m)=1,(x,m)=1,所以,(ax,m)=1.若ax1≡ax2(modm),则有
x1≡x2(modm),矛盾!
(ⅳ)若a1,a2,…,aφ(m)是)m(?个与m互质的整数,并且两两对模m不同余,则a1,a2,…,aφ(m)是模m的一个既约剩余系.
证明:因a1,a2,…,aφ(m)是)m(?个与m互质的整数,并且两两对模m不同余,
所以,a 1,a 2,…,a φ(m)属于)m (?个剩余类,且每个剩余类都与m 互质,故a 1,a 2,…,a φ
(m)
是模m 的一个既约剩余系.
(ⅴ)设m 1,m 2是两个互质的正整数,而x,y 分别历遍模m 1,m 2的既约剩余
系,则m 2x+m 1y 历遍模m 1m 2的既约剩余系.
证明:显然,既约剩余系是完系中所有与模互质的整数做成的.因x,y 分
别历遍模m 1,m 2的完系时,m 2x+m 1y 历遍模m 1m 2的完系.由(m 1,x)=(m 2,y)=1, (m 1,m 2)=1得(m 2x,m 1)=(m 1y,m 2)=1,所以,(m 2x+m 1y,m 1)=1,(m 2x+m 1y,m 2)=1,故 (m 2x+m 1y, m 1m 2)=1.反之若(m 2x+m 1y, m 1m 2)=1,则(m 2x+m 1y,m 1)=(m 2x+m 1y,m 2) =1,所以,(m 2x,m 1)=(m 1y,m 2)=1,因(m 1,m 2)=1,所以,(m 1,x)=(m 2,y)=1.证毕.
推论1若m 1,m 2是两个互质的正整数,则)()()(2121m m m m ???=.
证明:因当x,y 分别历遍模m 1,m 2的既约剩余系时,m 2x+m 1y 也历遍模m 1m 2的既约剩余系,即m 2x+m 1y 取遍)(21m m ?个整数,又x 取遍)(1m ?个整数,y 取遍
)(2m ?个整数,所以, m 2x+m 1y 取遍)()(21m m ??个整数,故)()()(2121m m m m ???=.
推论2 设整数n 的标准分解式为k
k
p p p n αα
α
Λ2121=(k p p ,,1Λ为互异素
数,
*1,,N k ∈ααΛ),则有)11()11)(11()(21k
p p p n n ---
=Λ?. 证明:由推论1得)()()()(2121k k p p p n α
α
α
????Λ=,而1)(--=ααα?p p p , (即从1到αp 这αp 个数中,减去能被p 整除的数的个数),所以,
)())(()(11221112
2
1
1
------=k
k
k k p p p p p p n αααααα?Λ
)1
1()11)(11(21k
p p p n ---
=Λ.
4.欧拉(Euler)与费尔马(Fermat)定理
欧拉(Euler)定理 设m 是大于1的整数,(a ,m)=1,则)(m od 1)
(m a
m ≡?.
证明:设r 1,r 2,…,r )(m ?是模m 的既约剩余系,则由性质3知a r 1,a r 2,…,a r )
(m ?也是模m 的既约剩余系,所以, a r 1a r 2…a r )(m ?≡r 1r 2…r )(m ?(modm),即
≡)(21)(m m r r r a ??Λ
)(21m r r r ?Λ,因()(21m r r r ?Λ,m)=1,所以,)(m od 1)(m a m ≡?.
推论(Fermat 定理) 设p 为素数,则对任意整数a 都有)(m od p a a p
≡.
证明:若(a , p )=1,由1)(-=p p ?及Euler 定理得)(m od 11
p a
p ≡-即
)(m od p a a p ≡;若(a , p )≠1,则p |a ,显然有)(m od p a a p ≡.
例1设m>0,证明必有一个仅由0或1构成的自然数a 是m 的倍数. 证明:考虑数字全为1的数:因1,11,111,1111,…中必有两个在modm 的同一剩余类中,它们的差即为所求的a .
例2证明从任意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 的同一剩余类,这两个数的差即满足要求.
例3设f(x)=5x+2=f 1(x), f n+1(x)=f[f n (x)].求证:对任意正整数n,存在正整数m,使得2011|f n (m).
证明:因f 2(x)=f[f(x)]=5(5x+2)+2=52x+5×2+2,
f 3(x)=f[f 2(x)]=53x+52×2+5×2+2,…, f n (x)=5n x+5n-1×2+5n-2×2+…+2, 因(5n ,2011)=1,所以,x 与f n (x)同时历遍mod2011的完系,1≤x ≤2011,
所以,存在正整数m(1≤m ≤2011)使得f n (m)≡0(mod2011),即2011|f n (m).
例4设123,,,a a a L 是整数序列,其中有无穷多项为正整数,也有无穷多项为 负整数.假设对每个正整数n ,数123,,,,n a a a a L 被n 除的余数都各不相同.证明:在数列123,,,a a a L 中,每个整数都刚好出现一次.
证明:数列各项同时减去一个整数不改变本题的条件和结论,故不妨设a 1=0.此时对每个正整数k 必有∣a k ∣ 现在对k 归纳证明a 1,a 2,…,a k 适当重排后是绝对值小于k 的k 个相邻整数.k=1显然.设a 1,a 2,…,a k 适当重排后为-(k -1-i),…,0,…,i (0≤i ≤k -1),由于 a 1,a 2,…,a k ,a k+1是(mod k+1)的一个完全剩余系,故必a k+1≡i+1(mod k+1), 但 ∣a k+1∣ 由此得到:1).任一整数在数列中最多出现一次;2).若整数u 和v (u 最后由正负项均无穷多个（即数列含有任意大的正整数及任意小的负整数）就得到:每个整数在数列中出现且只出现一次. 例5偶数个人围着一张圆桌讨论，休息后，他们依不同次序重新围着圆桌坐下,证明至少有两个人，他们中间的人数在休息前与休息后是相等的。 证明：将座号依顺时针次序记为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),矛盾！故结论成立. 例6数列{a n }定义为: a 0=a (a ∈N *)，a n+1=a n +!40n (n ∈N).数列{a n }中存在无穷多项可被2011整除. 证明:因(40,2011)=1,所以,)2011(m od 140)2011(≡?. 因当)2011(?>n 时,!|)2011(n ?,所以,数列{a n (mod2011)}构成模2011的完系,且是周期数列,所以, 数列{a n }中存在无穷多项可被2011整除. 例7证明:存在无穷多个正整数n,使得n 2+1?n!. 证明:引理1对素数p >2,?≡)4(mod 1p 存在x(1≤x ≤p -1)使 )(m od 12p x -≡. 证:充 分性:因 对 1≤x ≤p -1,( p ,x)=1,所 以,)(mod 1)(2 1 21 p x x p p ≡=--,≡-2 12) (p x )(mod 1) 1(2 1p p ≡--,所以, 2 1 -p 为偶数,即).4(mod 1≡p 必要性:因1≤x ≤p -1时,x,2x,…,(p -1)x 构成modp 的既约剩余系,所以,存在 1≤a ≤p -1,使得a x ≡-1(mod p ),若不存在a (1≤a ≤p -1), a =x,使a x ≡-1(mod p ), 则这样的a ,x 共配成21-p 对,则有)(mod 1)!1()1(2 1 p p p -≡-≡--,即2 1-p 为奇数, 与 14+=k p 矛盾!所以,必存在x(1≤x ≤p -1)使)(m od 12p x -≡. 引理2形如4k+1(k ∈Z)的素数有无限多个. 证：假设形如4k+1的素数只有n 个:p 1,p 2,…,p n ，则p 1,p 2,…,p n 都不是 a =4(p 1p 2…p k )2+1的素因数. 设q 是a 的一个素因数,则有(2p 1 p 2…p k )2≡-1(mod q ),因存在1≤x ≤q -1使 2p 1 p 2…p k ≡x(mod q ),即x 2≡-1(mod q ),所以,由引理1知14+=k q ,矛盾！ 所以,形如4k+1的素数有无限多个. 回到原题:由引理1,2知,存在无穷多个素数p ,使得存在x(1≤x ≤p -1)使 )(m od 12p x -≡.即p |x 2+1,因p>x,所以, p ?x!, x 2+1?x!,因这样的素数p 无穷多, 所以,相应的x 也无穷多. 例8设f(x)是周期函数,T 和1是f(x)的周期且0 (1)若T 为有理数,则存在素数p,使得 p 1 是f(x)的周期; (2)若T 为无理数,则存在各项均为无理数的数列{a n }满足0 证明：(1)设T=n m (正整数m,n 互质,且n ≥2),因(m,n)=1,所以,m,2m,…,nm 构成 modn 的完系,故存在k ∈N *使得km ≡1(modn),即存在t ∈N *使得km=nt+1,因 f(x)=f(x+kT)=f(x+n km )=f(x+t+n 1)=f(x+n 1),所以n 1 是周期. 设n=kp ,其中k ∈N * , p 为素数,则n k p 11?=是周期.故存在素数p,使p 1 是周期. (2)当T 为无理数时,取a 1=T,则T 为无理数, 0 a k ,使得0 取a k+1=u a k -v,则a k+1是无理数且是f(x)的周期,且0 期. 例9设正整数n ≥2.求所有包含n 个整数的集合A,使得A 的任意非空子集中所有元素的和不能被n+1整除. 解:设A={a 1,a 2,…,a n }是满足条件的集合.),,2,1(1n k a S k i i k Λ==∑=,依题意知, 对 任意k=1,2,…,n 都有n+1?S k ,且任意S k , S j (k ≠j)都有S k ?S j (modn+1),所以,{S k }包含了modn+1的所有非零剩余,因对1≤i ≤n,整数a i ,S 2,S 3,…,S n 也包含了mod(n+1)的所有非零剩余,所以, a 1=S 1≡a i (modn+1),即A 中任意a i ≡a 1(modn+1).所以,对任意1≤k ≤n, a 1+a 2+…+a k ≡k a 1(modn+1).且k a 1?0(modn+1),从而(a 1,n+1)=1. 取a 1=a 得集合A={a +k i (n+1)|k i ∈Z, 1≤i ≤n,a ∈Z,且(a ,n+1)=1}为所求. 例10对任意正整数n,用S(n)表示集合{1,2,…,n}中所有与n 互质的元素之和. 证明: 2S(n)不是完全平方数; 例11求所有的奇质数p ,使得∑=-2011 11|k p k p . 例12求所有质数p ,使得2 122213)()()(|-+++p p p p C C C p Λ. 例13设n 为大于1的奇数,k 1,k 2,…,k n 是n 个给定的整数,对1,2,…,n 的每一个排列a=(a 1,a 2,…,a n ),记S(a)=∑=n i i i a k 1.证明:存在两个1,2,…,n 的排列b 和 c(b ≠c),使得n!|S(b)-S(c). 证明:如果对1,2,…,n 的任意两个不同排列b 和c(b ≠c),都有 n!?S(b)-S(c),那么当a 取遍所有排列时(共n!个),S(a)遍历模n!的一个完系, 因此,有∑a a S )(≡1+2+…+n!≡ 2 ! 2)1!(!n n n ≡+(modn!) ①, 另一方面,我们有 ∑a a S )(=)!(mod 02)1(!])!1[(1 11 11n k n n j n k a k a k n i i n i n j i n i a i i a n i i i ≡+=-==∑∑∑ ∑∑∑∑===== ②. 由①∑a a S )(≡2 ! n (modn!)与②∑a a S )(≡0(modn!)(因n 为奇数)矛盾!故原命题成 立. 例14已知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 1 m k k m k n m k n ∑∑==≡即)(mod 0)12(1 m k m k n n ≡-∑=. 因(m,2n -1)=1,所以∑=m k n k m 1 |.得证. 例15已知x ∈(0,1),设y ∈(0,1)且对任意正整数n ，y 的小数点后第n 位数字是x 的小数点后第2n 位数字.证明:若x 是有理数,则y 也是有理数. 例16设A={a 1,a 2,…,a φ(n)}是模n 的一个既约剩余系.如果方程x 2≡1(modn)在A 中解的个数为N,求证: a 1a 2…a φ(n)≡2 )1(N -(modn). 同余方程与同余方程组 1.同余方程(组)及其解的概念 定义1 给定正整数m 及n 次整系数多项式0111)(a x a x a x a x f n n n n ++++=--Λ ，则同余式f(x)≡0(modm)①叫做模m 的同余方程,若a n 0(modm),则n 叫做方程①的次数. 若x=a 是使f(a )≡0(modm)成立的一个整数,则x ≡a (modm)叫做方程①的一个解,即把剩余类a (modm)叫做①的一个解. 若a 1(modm),a 2(modm)均为方程①的解,且a 1,a 2对模m 不同余,就称它们是方程①的不同解.由此可见,只需在模m 的任一组完系中解方程①即可. 例1解方程2x 2+x-1≡0(mod 7). 解:取mod7的完系:-3, -2,-1,0,1,2,3,直接验算知x ≡-3(modm)是解. 例2求方程4x 2+27x-12≡0(mod 15). 解:取mod15的完系:-7, -6,…,-1,0,1,…,7,直接验算知x ≡-6,3(modm)是解. 2.一次同余方程 设m ?a ,则a x ≡b(modm),叫模m 的一次同余方程. 定理1当(a ,m)=1时,方程a x ≡b(modm)必有解,且解数为1. 证明:因当(a ,m)=1时,x 与a x 同时遍历模m 的完系,所以,有且仅有一个x 使得 a x ≡b(modm).即x ≡a -1b(modm). 定理2方程a x ≡b(modm)有解?(a ,m)|b,且有解时其解数为(a ,m),及若x 0 是一个特解,则它的(a ,m)个解是1),(,,1,0),(m od ) ,(0-=+ ≡m a t m t m a m x x Λ. 例3解方程6x ≡10(mod8). 解:因(6,8)=2,且-1是一个特解,所以,方程6x ≡10(mod8)的解为: 1,0),8(mod 41=+-≡t t x 即)8(mod 3,1-≡x . 例4解方程12x ≡6(mod9). 因(12,9)=3,且-1是一个特解,所以,方程12x ≡6(mod9)的解为: 2,1,0),8(mod 31=+-≡t t x 即)8(mod 5,2,1，-≡x . 3.同余方程组 定义3给定正整数m 1,m 2,…,m k 和整系数多项式f 1(x),f 2(x),…,f k (x),则同余式组 ?????? ?≡≡≡) (mod 0)()(mod 0)()(mod 0)(2 211k k m x f m x f m x f ΛΛΛ②,叫做同余方程组.若x=a 是使f j (a )≡0(modm j )(1≤j ≤k)成立的一个整数,则x ≡a (modm)叫做方程组②的一个解,即把剩余类a (modm)叫做②的一个解.其中m=[m 1,m 2,…,m k ]. 例5解方程组???≡≡) 8(mod 106)7(mod 3x x . 解:由例3知6x ≡10(mod8)的解是)8(mod 3,1-≡x .所以,原解方程组? ???-≡≡)8(mod 1)7(mod 3x x 或????≡≡)8(mod 3)7(mod 3x x ? ? ?≡≡)8(mod 31) 7(mod 31x x 或)56(mod 3,31)56(mod 3≡?≡x x . 中国剩余定理:设K ≥2,而m 1,m 2,…,m k 是K 个两两互质的正整数，令 M=m 1m 2…m k =m 1M 1=m 2M 2=…=m k M k ，则对任意整数a 1,a 2,…,a k 下列同余式组： ???????≡≡≡) (mod )(mod )(mod 2 211k 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). 其中M j -1满足M j M j -1≡1(modm j )(1≤j ≤k),即M j 对模m j 的逆. 证明:(1)对1≤j ≤k,因m j |M i (i ≠j) ,m j |M,所以x ≡a j M j M j -1≡a j (modm j ). (2)设x,y 都是同余式组的解,即x ≡a j (modm j ),y ≡a j (modm j )(1≤j ≤k), 则x ≡y(modm j ),即m j |x-y,因m 1,m 2,…,m k 两两互质,所以M| x-y 即x ≡y(modM). 注:(1)存在无穷多个整数x 满足同余方程组③,这些x 属于同一模m 的剩余类; (2)同余方程组③仅有一个解x ≡a 1M 1M 1-1+a 2M 2M 2-1+…+a k M k M k -1(modM). (3)当(a ,m i )=1(=1,2,…,n)时,同余方程组 ?? ? ????≡≡≡????????≡≡≡---)(mod )(mod )(mod )(mod )(mod ) (mod 1221 1112 211k k k k m a a x m a a x m a a x m a ax m a ax m a ax ΛΛΛΛΛΛ仍然具有定理结论. 这在数论解题中具有重要应用. 例6“今有物不知其数，三三数之余二，五五数之余三，七七数之余二，问物几何”. 解:设物数x,则有?? ? ??≡≡≡)7(mod 2)5(mod 3) 3(mod 2x x x ,这里m 1=3,m 2=5,m 3=7,M=3×5×7=105,所以, 35×35-1≡2×35-1≡1(mod3)?35-1≡2(mod3), 21×21-1≡21-1≡1(mod5)?21-1≡1(mod3), 15×15-1≡15-1≡1(mod7)?15-1≡1(mod3),所以,同余方程组的解为: )105(mod 23233115212132352≡=??+??+??≡x ,即x=105k+23(k ∈N). 例7有兵一队,若分别列5,6,7,11行纵队,则末行人数分别为1,5,4,10.求兵数. 解:设兵数x,则???? ???≡≡≡≡) 11(mod 10)7(mod 4)6(mod 5)5(mod 1x x x x ,其中m 1=5,m 2=6,m 3=7,m 4=11,M=2310, 462×462-1≡2×462-1≡1(mod5)?462-1≡3(mod5), 385×385-1≡385-1≡1(mod6)?385-1≡1(mod6), 330×330-1≡330-1≡1(mod7)?330-1≡1(mod7), 210×210-1≡210-1≡1(mod11)?210-1≡1(mod11),所以,同余方程组的解 为: )2310(mod 2111637121010330438553462≡=?+?+?+?≡x , 即x=2310k+2111(k ∈N). 例8证明:对任意n 个两两互质的正整数:m 1,m 2,…,m n ,总存在n 个连续的自然数k+1,k+2,…,k+n 使得m i |k+i(i=1,2,…,n). 证明:由剩余定理知,总存在整数k 使得?????? ?-≡-≡-≡) (mod ) (mod 2)(mod 12 1n m n k m k m k ΛΛ,即存在连续的自然数k+1,k+2,…,k+n 使得m i |k+i(i=1,2,…,n). 例9证明:对任意n ∈N *,存在n 个连续正整数它们中每一个数都不是素数的幂(当然也不是素数). 证明:因都不是素数的幂时,只能是素数之积.对任意n ∈N *,取两组不同的素 数p 1,p 2,…,p n 与q 1,q 2,…,q n ,则由剩余定理知存在m ∈N *,使得 ?????? ?-≡-≡-≡) (mod )(mod 2) (mod 12 211n n q p n m q p m q p m ΛΛ同时成立.于是,n 个连续正整数m+1, m+2,…,m+n 中,每一个数都有两个不同的素因子.故结论成立. 例10证明:存在一个含有N(≥2)个正整数的集合A,使得A 中任意两个数都互质,且A 中任意k(k ≥2)个数的和都是合数. 例11证明:存在一个由正整数组成的递增数列{a n },使得对任意k ∈N *,数列 {k +a n }中都至多有有限项为素数. 证明:用p 1,p 2,p 3,…表示所有素数从小到大的排列.令a 1=2,a 2为适合 ?? ?-≡≡)(mod 1)(mod 021p x p x 且大于a 1的最小正整数a 2=8,取a 3适合?? ? ??-≡-≡≡) (mod 2)(mod 1) (mod 0321p x p x p x 且大于a 2的 最小正整数a 2=38.假定a 1,a 2,…,a n 都已确定,则取a n+1适合???????-≡-≡≡+) (mod )(mod 1) (mod 012 1n p n x p x p x ΛΛ且大 于a n 的最小正整数,由剩余定理知满足条件的a n+1存在.则上述递推关系定义的数列{a n }满足题意:因对任意k ∈N *,当n ≥k+1时,都有k+a n ≡0(mod p k+1), 由{a n }递增可知{k +a n }从第k+2项起每一项都是p k+1的倍数,且都大于p k+1,所以, 数列{k +a n }中至多有k+1项为素数. 例12是否存在一个由正整数组成的数列，使得每个正整数都恰在该数列中出现一次，且对任意正整数k ，该数列的前k 项之和是k 的倍数？ 解:取a 1=1,假设a 1,a 2,…,a m 都已确定,令t 为不在a 1,a 2,…,a m 中出现的最小正整数, S=a 1+a 2+…+a m .由剩余定理知存在无穷多个r ∈N *,使得 ? ? ?+≡+++≡+)2(mod 0) 1(mod 0m t r S m r S 成立.(如a 1=1,取t=2,适合???≡++≡+)3(mod 0) 2(mod 01 1t r a r a 且r>1,2得 r=3). 取这样的r,使得r>t 且r>},,,m ax {21m a a a Λ,令a m+1=r, a m+2=t,则这样得到的数列{a n }满足要求. 例13证明:存在一个n ∈N *,使得对任意整数k,整数k 2+k+n 没有小于2011的质因数. 例14证明:存在k ∈N *, 使得对任意n ∈N *,数2n k+1都是合数. 例15设m ∈N *,n ∈Z,证明:数2n 可以表为两个与m 互素的整数之和. 历年全国高中数学联赛试题及答案 1．全卷满分120分，考试时间120分钟．试题卷共6页，有三大题，共24小题。 2．全卷答案必须做在答题纸卷Ⅰ、卷Ⅱ的相应位置上，做在试题卷上无效,考试时不 能使用计算器。 参考公式：二次函数图象的顶点坐标是。 温馨提示：请仔细审题，细心答题，答题前仔细阅读答题纸上的“注意事项”。 卷Ⅰ（选择题） 一、选择题（本大题有10小题，每小题3分，共30分．请选出各题中唯一的正确选项，不选、多选、错选，均不得分） 1．2的相反数是（▲） A．-2 B．2 C．- D． 2．下列计算正确的是（▲）A．Ｂ．9 =3 Ｃ．3-1= -3 Ｄ．2 +3= 5 3．据交通运输部统计，2013年春运期间，全国道路、水路、民航、铁路运送旅客总量超过了3400000000人次，该数用科学记数法可表示为（▲） A．B．C． D． 4．如图是由个相同的正方体搭成的几何体，则其俯视图是（▲） 5．使分式无意义的的值是（▲） A. B. C. D. 6．如图，已知,若, ，则等于（▲） A．B．C．D． 7．市委、市政府打算在2015年底前，完成国家森林城市创建．这是小明随机抽取我市10个小区所得到的绿化率情况，结果如下表： 小区绿化率（%） 20 25 30 32 小区个数 2 4 3 1 则关于这10个小区的绿化率情况，下列说法错误的是（▲） A．中位数是25% B．众数是25% C．极差是13% D．平均数是26．2% 8．将一个半径为R，圆心角为90°的扇形围成一个圆锥的侧面（无重叠），设圆锥底面半径为r，则R与r的关系正确的是（▲） A．R＝8r B．R＝6r C．R＝4r D．R＝2r 9．甲、乙两车分别从相距的两地同时出发，它们离A地的路程随时间变化的图象如图所示，则下列结论不正确的是( ▲) A．甲车的平均速度为； B．乙车行驶小时到达地,稍作停留后返回地； C．经小时后,两车在途中相遇； D．乙车返回地的平均速度比去地的平均速度小。 10．如图，为等边三角形，点的坐标为，过点作直线交于点，交于，点在反比例函数＜的图象上，若和（即图中两阴影部分）的面积相等，则值为（▲）A．B．C．D． 卷Ⅱ（非选择题） 二、填空题（本大题有6小题，每题4分，共24分） 11．分解因式：= ▲。 12．一个不透明的袋中装有除颜色外其他均相同的2个红球和3个黄球，从中随机摸出一个 高中数学竞赛中数论问题的常用方法 数论是研究数的性质的一门科学,它与中学数学教育有密切的联系.数论问题解法灵活,题型丰富,它是中学数学竞赛试题的源泉之一.下面介绍数论试题的常用方法. 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、（2009一试8）某车站每天8 00~900∶∶，900~1000∶∶都恰有一辆客车到站，但到站的时刻是随机的，且两者到站的时间是相互独立的，其规律为 一旅客820∶【答案】27 【解析】旅客候车的分布列为 候车时间的数学期望为10305070902723361218 ?+?+?+?+?= 2、（2010一试6）两人轮流投掷骰子，每人每次投掷两颗，第一个使两颗骰子点数和大于6者为胜，否则轮由另一人投掷.先投掷人的获胜概率是 . 【答案】 12 17 3、（2012一试8）某情报站有,,,A B C D 四种互不相同的密码，每周使用其中的一种密码，且每周都是从上周未使用的三种密码中等可能地随机选用一种．设第１周使用Ａ种密码，那么第７周也使用Ａ种密码的概率是．（用最简分数表示） 【答案】 61 243 【解析】用k P 表示第k 周用 A 种密码的概率,则第k 周末用A 种密码的概率为 1k P -.于是,有11(1),3k k P P k N *+=-∈,即1111()434k k P P +-=--由11P =知，14k P ? ?-???? 是首项为34，公 比为13-的等比数列.所以1131()443k k P --=-，即1311()434k k P -=-+，故761243 P = 4、（2014一试8）设D C B A ,,,是空间四个不共面的点，以 2 1 的概率在每对点之间连一条边，任意两点之间是否连边是相互独立的，则B A ,可用（一条边或者若干条边组成的）空间折线连接的概率是__________. 【答案】 3 4 2221219B C D -?-=点相连，且与，中至少一点相连，这样的情况数为（）（） 22(3)AB AD DB 无边，也无CD 边，此时AC,CB 相连有2种情况，，相连也有2种情况， ,,,,AC CB AD DB A B 但是其中均相连的情况被重复了一次，故可用折线连接的情况数为 222+2-1=7. 483++==.644以上三类情况数的总和为329748，故A,B 可用折线连接的概率为 5、（2015一试5）在正方体中随机取三条棱,它们两两异面的概率为. 【答案】 2 55 【解析】设正方体为ABCD-EFGH ，它共有12条棱，从中任意选出3条棱的方法共有3 12C =220种. 下面考虑使3条棱两两异面的取法数，由于正方体的棱共确定3个互不平行的方向（即AB 、AD 、AE 的方向），具有相同方向的4条棱两两共面，因此取出的3条棱必属于3个不同的方向.可先取定AB 方向的棱，这有4种取法.不妨设取的棱就是AB ，则AD 方向只能取棱EH 或棱FG ，共2种可能，当AD 方向取棱是EH 或FG 时，AE 方向取棱分别只能是CG 或DH. 由上可知，3条棱两两异面的取法数为4×2=8，故所求的概率为82 22055 =. 高中数学竞赛数论部分文档编制序号：[KKIDT-LLE0828-LLETD298-POI08] 初等数论简介 绪言：在各种数学竞赛中大量出现数论题，题目的内容几乎涉及到初等数论的所有专题。 1．请看下面的例子： （1） 证明：对于同样的整数x 和y ，表达式2x+3y 和9x+5y 能同时被整除。(1894年首 届匈牙利 数学竞赛第一题) （2） ①设n Z ∈，证明2131n -是168的倍数。 ②具有什么性质的自然数n ，能使123n ++++能整除123n ???（1956年上海首 届数学竞赛第一题） （3） 证明：3231 122 n n n ++-对于任何正整数n 都是整数，且用3除时余2。（1956年 北京、天津市首届数学竞赛第一题） （4） 证明：对任何自然数n ，分数 214 143 n n ++不可约简。（1956年首届国际数学奥林匹 克竞赛第一题） （5） 令(,, ,)a b g 和[,, ,]a b g 分别表示正整数,,,a b g 的最大公因数和最小公倍数， 试证：[][][][]()()()() 2 2 ,,,,,,,,,,a b c a b c a b b c c a a b b c c a =??（1972年美国首届奥林匹克数学竞赛第一题） 这些例子说明历来数论题在命题者心目中首当其冲。 2.再看以下统计数字： （1）世界上历史最悠久的匈牙利数学竞赛，从1894~1974年的222个试题中，数论题有41题，占18.5%。 （2）世界上规模最大、规格最高的IMO （国际数学奥林匹克竞赛）的前20届120道试题中有数论13题，占% 。 历年全国高中数学联赛二试几何题汇总 2007 联赛二试 类似九点圆 如图，在锐角?ABC 中，AB 不定方程 不定方程是指未知数的个数多于方程的个数，且未知数的取值范围是受某些限制（如整数、正整数或有理数）的方程.不定方程是数论的一个重要课题，也是一个非常困难和复杂的课题. 1．几类不定方程 （1）一次不定方程 在不定方程和不定方程组中，最简单的不定方程是整系数方程 )0,0(,0≠>=++b a c by ax 通常称之为二元一次不定方程.一次不定方程解的情况有如下 定理. 定理一：二元一次不定方程c b a c by ax ,,,=+为整数.有整数解的充分必要条件是c b a |),(. 定理二：若00,,1),(y x b a 且=为①之一解，则方程①全部解为at y y bt x x -=+=00,. （t 为整数）。 （2）沛尔)(pell 方程 形如12 2 =-dy x （*d N ∈，d 不是完全平方数）的方程称为沛尔方程. 能够证明它一定有无穷多组正整数解；又设),(11y x 为该方程的正整数解),(y x 中使d y x +最小的 解，则其的全部正整数解由111111111[()()]2)()] n n n n n n x x x y x x ?=+-?? ??=-?? （1,2,3, n =）给 出. ①只要有解),(11y x ，就可以由通解公式给出方程的无穷多组解. ②n n y x , 满足的关系：1(n n x y x y +=+；112 11222n n n n n n x x x x y x y y ----=-?? =-? ， （3）勾股方程2 2 2 z y x =+ 这里只讨论勾股方程的正整数解，只需讨论满足1),(=y x 的解，此时易知z y x ,,实际上两两互素. 这种z y x ,,两两互素的正整数解),,(z y x 称为方程的本原解，也称为本原的勾股数。容易看出y x ,一奇一偶，无妨设y 为偶数，下面的结果勾股方程的全部本原解通解公式。 定理三：方程2 2 2 z y x =+满足1),(=y x ，2|y 的全部正整数解),,(z y x 可表为 2222,2,b a z ab y b a x +==-=，其中，b a ,是满足b a b a ,,0>>一奇一偶，且 第1届I M O 1.求证(21n+4)/(14n+3)对每个自然数n都是最简分数。 2.设√(x+√(2x-1))+√(x-√(2x-1))=A，试在以下3种情况下分别求出x的实数解： (a)A=√2；(b)A=1；(c)A=2。 3.a、b、c都是实数，已知cosx的二次方程 acos2x+bcosx+c=0, 试用a,b,c作出一个关于cos2x的二次方程，使它的根与原来的方程一样。当a=4,b=2,c=-1时比较cosx和cos2x的方程式。 4.试作一直角三角形使其斜边为已知的c，斜边上的中线是两直角边的几何平均值。 5.在线段AB上任意选取一点M，在AB的同一侧分别以AM、MB为底作正方形AMCD、MBEF，这两个正方形的外接圆的圆心分别是P、Q，设这两个外接圆又交于M、N， (a.)求证AF、BC相交于N点； （b.)求证不论点M如何选取直线MN都通过一定点S； (c.)当M在A与B之间变动时，求线断PQ的中点的轨迹。 6.两个平面P、Q交于一线p，A为p上给定一点，C为Q上给定一点，并且这两点都不在直线p上。试作一等腰梯形ABCD（AB平行于CD），使得它有一个内切圆，并且顶点B、D分别落在平面P和Q 上。 第2届IMO 1.找出所有具有下列性质的三位数N：N能被11整除且N/11等于N的各位数字的平方和。 2.寻找使下式成立的实数x： 4x2/(1-√(1+2x))2<2x+9 3.直角三角形ABC的斜边BC的长为a，将它分成n等份（n为奇数），令为从A点向中间的那一小段线段所张的锐角，从A到BC边的高长为h，求证： tan=4nh/(an2-a). 初等数论简介 绪言：在各种数学竞赛中大量出现数论题，题目的内容几乎涉及到初等数论的所有专题。 1． 请看下面的例子： （1） 证明：对于同样的整数x 和y ，表达式2x+3y 和9x+5y 能同时被整除。(1894年首届匈牙利 数学竞 赛第一题) （2） ①设n Z ∈，证明213 1n -是168的倍数。 ②具有什么性质的自然数n ，能使123n ++++ 能整除123n ??? ？（1956年上海首届数学竞赛第一题） （3） 证明：3 231 122 n n n + +-对于任何正整数n 都是整数，且用3除时余2。（1956年北京、天津市首届数学竞赛第一题） （4） 证明：对任何自然数n ，分数 214 143 n n ++不可约简。（1956年首届国际数学奥林匹克竞赛第一题） （5） 令(,,,)a b g 和[,,,]a b g 分别表示正整数,,,a b g 的最大公因数和最小公倍数，试证： [][][][]()()()() 2 2 ,,,,,,,,,,a b c a b c a b b c c a a b b c c a =??（1972年美国首届奥林匹克数学竞赛第一题） 这些例子说明历来数论题在命题者心目中首当其冲。 2.再看以下统计数字： （1）世界上历史最悠久的匈牙利数学竞赛，从1894~1974年的222个试题中，数论题有41题，占18.5%。 （2）世界上规模最大、规格最高的IMO （国际数学奥林匹克竞赛）的前20届120道试题中有数论13题，占10.8% 。 这说明：数论题在命题者心目中总是占有一定的分量。如果将有一定“数论味”的计数型题目统计在内，那么比例还会高很多。 3.请看近年来国内外重大竞赛中出现的数论题： (1)方程323652x x x y y ++=-+的整数解(,)x y 的个数是（ ） A 、 0 B 、1 C 、3 D 、无穷多 （2007全国初中联赛5） （2）已知,a b 都是正整数，试问关于x 的方程()2 1 02 x abx a b -++=是否有两个整数解？ 如果有，请把它们求出来；如果没有，请给出证明。 （2007全国初中联赛12） 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 数论部分 2018A 四、（本题满分50分）数列{}n a 定义如下：1a 是任意正整数，对整数1≥n ，1+n a 与∑=n i i a 1 互 素，且不等于n a a a ,.,,21 的最小正整数，证明：每个正整数均在数列{}n a 中出现。 ★证明：显然11=a 或者12=a .下面考虑整数1>m ，设m 有k 个不同的素因子，我们对k 归纳证明 m 在{}n a 中出现.记n n a a a S +++= 21，1≥n . 1=k 时，m 是素数方幂，记αp m =，其中0>α，p 是素数.假设m 不在{}n a 中出现.由于{}n a 各 项互不相同，因此存在正整数N ，当N n ≥时，都有αp a n >.若对某个N n ≥，n S p |/，那么αp 与 n S 互素，又n a a a ,.,,21 中无一项是αp ，故有数列定义知αp a n ≤+1，但是αp a n >+1，矛盾！ 因此对每个N n ≥，都有n S p |.又1|+n S p ，可得1|+n a p ，从而1+n a 与n S 不互素，这与1+n a 的定义矛盾！ 假设2≥k ，且结论对1-k 成立.设m 的标准分解为k k p p p m αα α 2121=.假设m 不在{}n a 中出现，于 是存在正整数/N ，当/ N n ≥时，都有m a n >.取充分大的正整数 121,,-k βββ ，使得 n N n k a p p p M k /1211121max ≤≤->=-βββ . 我们证明，对/ N n ≥，有M a n ≠+1. 对于任意/ N n ≥，若n S 与k p p p 21互素，则m 与n S 互素，又m 在n a a a ,.,,21 中均未出现，而 m a n >+1，这与数列的定义矛盾，因此我们得到：对于任意/N n ≥，n S 与k p p p 21不互素*， ⑴若存在i （11-≤≤k i ），使得n i S p |，则()1,1=+n n S a ，故1|+/n i a p ，从而M a n ≠+1（因为M p i |）。 ⑵若对每个i （11-≤≤k i ），均有n i S p |/，则由*知，必有n k S p |.于是1|+/n k a p ，进而1|++/n n k a S p ，即1|+/n k S p .故由*知：存在0i （110-≤≤k i ），使得1|0+n i S p ，再由n n n a S S +=+1及前面的假设n i S p |/，可知1|0+/n i a p ，故M a n ≠+1。 第1届I M O 1.? 求证(21n+4)/(14n+3) 对每个自然数 n都是最简分数。 2.??设√(x+√(2x-1))+√(x-√(2x-1))=A，试在以下3种情况下分别求出x的实数解：? (a) A=√2；(b)A=1；(c)A=2。 3.?a、b、c都是实数，已知 cos x的二次方程 a cos2x + b cos x + c = 0, 试用a,b,c作出一个关于 cos 2x的二次方程，使它的根与原来的方程一样。当 a=4,b=2,c=-1时比较 cos x和cos 2x的方程式。 4.? 试作一直角三角形使其斜边为已知的 c，斜边上的中线是两直角边的几何平均值。 5.? 在线段AB上任意选取一点M，在AB的同一侧分别以AM、MB为底作正方形AMCD、MBEF，这两个正方形的外接圆的圆心分别是P、Q，设这两个外接圆又交于M、N， ??? (a.) 求证 AF、BC相交于N点； ?? （b.) 求证不论点M如何选取直线MN 都通过一定点 S； ??? (c.) 当M在A与B之间变动时，求线断 PQ的中点的轨迹。 6.? 两个平面P、Q交于一线p，A为p上给定一点，C为Q上给定一点，并且这两点都不在直线p上。试作一等腰梯形ABCD（AB平行于CD），使得它有一个内切圆，并且顶点B、D分别落在平面P和Q上。 第2届IMO 1.? 找出所有具有下列性质的三位数 N：N能被11整除且 N/11等于N的各位数字的平方和。 2.? 寻找使下式成立的实数x： 4x2/(1 - √(1 + 2x))2 ?< ?2x + 9 3.? 直角三角形ABC的斜边BC的长为a，将它分成 n 等份（n为奇数），令?为从A点向中间的那一小段线段所张的锐角，从A到BC边的高长为h，求证： tan ? = 4nh/(an2 - a). 4.? 已知从A、B引出的高线长度以及从A引出的中线长，求作三角形ABC。 5.? 正方体ABCDA'B'C'D'（上底面ABCD，下底面A'B'C'D'）。X是对角线AC上任意一点，Y是B'D'上任意一点。 a.求XY中点的轨迹； b.求(a)中轨迹上的、并且还满足 ZY=2XZ的点Z的轨迹。 6.? 一个圆锥内有一内接球，又有一圆柱体外切于此圆球，其底面落在圆锥的底面上。令V1为圆锥的体积，V2为圆柱的体积。 ??? (a).? 求证：V1不等于 V2； ??? (b).? 求V1/V2的最小值；并在此情况下作出圆锥顶角的一般。 7.? 等腰梯形ABCD，AB平行于DC，BC=AD。令AB=a,CD=c，梯形的高为 h。X点在对称轴上并使得角BXC、AXD都是直角。试作出所有这样的X点并计算X到两底的距离；再讨论在什么样的条件下这样的X点确实存在。 第3届IMO 1.? 设a、b是常数，解方程组 x + y + z = a; ? ? x2 + y2 + z2 = b2; ? ? xy=z2 并求出若使x、y、z是互不相同的正数，a、b应满足什么条件？ 2.? 设a、b、c是某三角形的边，A 是其面积，求证： a2 + b2 + c2>= 4√3 A. 并求出等号何时成立。 3.? 解方程 cos n x - sin n x = 1, 其中n是一个自然数。 4.? P是三角形ABC内部一点，PA交BC于D，PB交AC于E，PC交AB于F，求证AP/PD, 高中数学竞赛 数论 剩余类与剩余系 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),也矛盾! （1981年~2019年） 2019A 5、在1,2,3, ,10中随机选出一个数a ，在1,2,3,,10----中随机选出一 个数b ，则2a b +被3整除的概率为 ． 答案： 37100 解析：首先数组(),a b 有1010100 ?=种等概率的选法． 考虑其中使2a b +被3整除 的选法数N ．①若a 被 3 整除，则b 也被 3 整除．此时,a b 各有3种选法，这样的(),a b 有 339?=组． 若a 不被 3 整除，则()21mod3a ≡，从而()1mod3b ≡-．此时a 有7 种选法，b 有4种选法，这样的(),a b 有7428?=组． 因此92837N =+=．于是所求概率为 37 100 。 2019A 三、（本题满分 50 分）设m 为整数，2m ≥．整数数列12,,a a 满足：12,a a 不 全为零，且对任意正整数n ，均有21n n n a a ma ++=-．证明：若存在整数,r s , (2r s >≥ )使得1r s a a a ==，则r s m -≥． 解析：证明：不妨设12,a a 互素（否则，若()12,1a a d =>，则12,1a a d d ?? = ?? ?互素，并且用 12 ,,a a d d 代替12,, a a ，条件与结论均不改变）． 由数列递推关系知()234mod a a a m ≡≡≡ ． ① 以下证明：对任意整数3n ≥，有()()2123mod n a a a n a m m ≡-+-????． ② ………10 分 事实上，当3n =时②显然成立．假设n k =时②成立（其中k 为某个大于2的整数），注意到①，有()212mod k ma ma m -≡，结合归纳假设知 ()()()2 1122221232mod k k k a a ma a k a m ma a a k a m +-≡-≡+--=-+-???????? ，即1n k =+时②也成立．因此②对任意整数3n ≥均成立． ………………20 分 2016年~2018年全国高中数学联赛一试试题分类汇编 10、计数问题、概率与统计部分 2018A 3、将6,5,4,3,2,1随机排成一行，记为f e d c b a ,,,,,，则def abc +是偶数的概率为 ◆答案：10 9 ★解析：先考虑def abc +为奇数时，abc ，def 一奇一偶，①若abc 为奇数，则c b a ,,为5,3,1的排列，进而f e d ,,为6,4,2的排列，这样共有3666=?种；②若abc 为偶数，由对称性得，也有3666=?种，从而def abc +为奇数的概率为 101!672=，故所求为10 91011=- 2018B 3、将6,5,4,3,2,1随机排成一行，记为f e d c b a ,,,,,，则def abc +是奇数的概率为 ◆答案：10 1 ★解析：由def abc +为奇数时，abc ，def 一奇一偶，①若abc 为奇数，则c b a ,,为5,3,1的排列，进而f e d ,,为6,4,2的排列，这样共有3666=?种；②若abc 为偶数，由对称性得，也有3666=?种，从而def abc +为奇数的概率为 101!672=。 2017A 6、在平面直角坐标系xOy 中，点集{}1,0,1,|),(-==y x y x K ，在K 中随机取出三个点，则这三个点中存在两点距离为5的概率为 ◆答案： 7 4 ★解析：由题意得K 有9个点，故从中取出三个点共有8439=C 种。 将K 中的点按右图标记为O A A A ,,,,821 ，其中有8对点之间的距 离为5，由对称性，考虑取41,A A 两点的情况，则余下的一个点有 7种取法， 这样有5687=?个三点组（不考虑顺序）。对每个i A （8,,2,1 =i ），K 中恰有53,++i i A A 竞赛中的数论问题的思考方法 一. 条件的增设 对于一道数论命题，我们往往要首先排除字母取零值或字母取相等值等“平凡”的情况，这样，利用字母的对称性等条件，往往可以就字母间的大小顺序、整除性、互素性等增置新的条件，从而便于运用各种数论特有手段。 1. 大小顺序条件 与实数范围不同，若整数x ，y 有大小顺序x 2010年全国高中数学联赛 一 试 一、填空题（每小题8分，共64分，） 1. 函数x x x f 3245)(---= 的值域是 . 2. 已知函数x x a y sin )3cos (2 -=的最小值为3-，则实数a 的取值范围是 . 3. 双曲线12 2 =-y x 的右半支与直线100=x 围成的区域内部（不含边界）整点（纵横坐标均为整数的点）的个数是 . 4. 已知}{n a 是公差不为0的等差数列，}{n b 是等比数列，其中 3522113,,1,3b a b a b a ====，且存在常数βα,使得对每一个正整数n 都有βα+=n n b a log ， 则=+βα . 5. 函数)1,0(23)(2≠>-+=a a a a x f x x 在区间]1,1[-∈x 上的最大值为8，则它在这个区 间上的最小值是 . 6. 两人轮流投掷骰子，每人每次投掷两颗，第一个使两颗骰子点数和大于6者为胜，否则轮由另一人投掷.先投掷人的获胜概率是 . 7. 正三棱柱111C B A ABC -的9条棱长都相等，P 是1CC 的中点，二面角α=--11B P A B ,则=αsin . 8. 方程2010=++z y x 满足z y x ≤≤的正整数解（x ,y ,z ）的个数是 . 二、解答题（本题满分56分） 9. （16分）已知函数)0()(2 3 ≠+++=a d cx bx ax x f ，当10≤≤x 时，1)(≤'x f ，试求a 的最大值. 10.（20分）已知抛物线x y 62=上的两个动点1122(,)(,)A x y B x y 和，其中21x x ≠且 421=+x x .线段AB 的垂直平分线与x 轴交于点C ，求ABC ?面积的最大值. 11.（20分）证明：方程02523 =-+x x 恰有一个实数根r ，且存在唯一的严格递增正整数数列}{n a ，使得 +++=3215 2 a a a r r r . 初等数论中的几个重要定理 基础知识 定义（欧拉(Euler)函数）一组数称为是模的既约剩余系，如果对任意的，且对于任意的，若＝1，则有且仅有一个是对模 的剩余，即。并定义中和互质的数的个数， 称为欧拉（Euler）函数。 这是数论中的非常重要的一个函数，显然，而对于，就是1,2，…，中与互素的数的个数，比如说是素数，则有。 引理：；可用容斥定理来证（证明略）。 定理1：（欧拉（Euler）定理）设＝1，则。 分析与解答：要证，我们得设法找出个相乘，由个数我们想到中与互质的的个数：，由于＝1，从而 也是与互质的个数，且两两余数不一样，故 （），而（）＝1，故。 证明：取模的一个既约剩余系，考虑，由于与互质，故仍与互质，且有，于是对每个都能找到唯一的一个，使得，这种对应关系 是一一的，从而，。 ，，故。证毕。 这是数论证明题中常用的一种方法，使用一组剩余系，然后乘一个数组组成另外一组剩余系来解决问题。 定理2：（费尔马（Fermat）小定理）对于质数及任意整数有。 设为质数，若是的倍数，则。若不是的倍数，则 由引理及欧拉定理得，，由此即得。 定理推论：设为质数，是与互质的任一整数，则。 定理3：（威尔逊（Wilson）定理）设为质数，则。 分析与解答：受欧拉定理的影响，我们也找个数，然后来对应乘法。 证明：对于，在中，必然有一个数除以余1，这是因为则好是的一个剩余系去0。 从而对，使得； 若，，则，，故对于，有。即对于不同的对应于不同的，即中数可两两配对，其积除以余1，然后有，使，即与它自己配对，这时，，或，或。 除外，别的数可两两配对，积除以余1。故。 定义：设为整系数多项式（），我们把含有的一组同余式 （）称为同余方组程。特别地，，当均为的一次整系数多项式时，该同余方程组称为一次同余方程组.若整数同时满足： ，则剩余类（其中）称为同余方程组的一个解，写作 定理4：（中国剩余定理）设是两两互素的正整数，那么对于任意整数，一次同余方程组，必有解，且解可以写为： 这里，，以及满足，（即为对模的逆）。 中国定理的作用在于它能断言所说的同余式组当模两两互素时一定有解，而对于解的形式并不重要。 定理5：（拉格郎日定理）设是质数，是非负整数，多项式 是一个模为次的整系数多项式（即），则同余方程至多有个解（在模有意义的情况下）。 定理6：若为对模的阶，为某一正整数，满足，则必为的倍数。 以上介绍的只是一些系统的知识、方法，经常在解决数论问题中起着突破难点的作用。另外还有一些小的技巧则是在解决、思考问题中起着排除情况、辅助分析等作用，有时也会起到 全国高中数学历届(2009-2019)联赛与各省市预赛试题汇编 专题20函数真题汇编与预赛典型例题 1．【2019年全国联赛】已知正实数a满足，则的值为. 【答案】 【解析】 由. . 2．【2018年全国联赛】设f（x）是定义在R上的以2为周期的偶函数，在区间[0，1]上严格递减，且满足，则不等式组的解集为. 【答案】 【解析】由f（x）为偶函数及在[0，1]上严格递减知，f（x）在[-1，0]上严格递增，再结合f（x）以2为周期可知，[1，2]是f（x）的严格递增区间. 注意到. 所以. 而，故原不等式组成立当且仅当. 3．【2017年全国联赛】设为定义在R上的函数，对任意实数x有.当0≤x＜7时，.则的值为____________。 【答案】 【解析】 由题得，所以函数的周期为7， . 故答案为： 4．【2016年全国联赛】设正实数u、v、w均不等于1.若，则 的值为________. 【答案】 【解析】 令 .则: . 故. 从而， . 5．【2015年全国联赛】设为不相等的实数.若二次函数 满足 ，则 的 值为______. 【答案】4 【解析】 由已知条件及二次函数图像的轴对称性得 . 故答案为：4 6．【2014年全国联赛】若正数a ，b 满足2362log 3log log ()a b a b +=+=+，则11 a b += ． 【答案】108 【解析】 试题分析：设2 32362log 3log log ()2 ,3,6t t t a b a b t a b a b --+=+=+=?==+=? 11a b a b ab ++= 23610823 t t t --==?． 考点：指数与对数运算． 7．【2014年全国联赛】设集合中的最大、最小元素分别为M 、m ，则 的值为 ___________. 【答案】 【解析】 由 ，知 .历年全国高中数学联赛试题及答案
高中数学竞赛中数论问题的常用方法
概率统计-历届全国高中数学联赛真题专题分类汇编
高中数学竞赛数论部分
历年全国高中数学联赛二试几何题汇总汇总
高中数学竞赛辅导初等数论不定方程
高中数学竞赛历届IMO竞赛试题届完整中文版
高中数学竞赛资料-数论部分 (1)
历年全国高中数学联赛试题及答案
数论历届高中数学联赛真题分类汇编含详细答案
高中数学竞赛历届IMO竞赛试题届完整中文版
高中数学竞赛数论
全国高中数学联赛试题分类汇编-数论(1981年-2019年)
10二项式定理计数概率与统计2016-2018年历年数学联赛真题WORD版分类汇编含详细答案
高中数学竞赛专题讲座---竞赛中的数论问题
2020年整理往年全国高中数学联赛一试真题及答案详解
初等数论中的几个重要定理高中数学竞赛
全国高中数学联赛与各省市预赛历届(2009-2019)试题汇编 函数(解析版)
相关主题
文本预览