数学竞赛数论问题复习课程

1、数学竞赛数论问题学习好资料高中数学竞赛中数论问题的常用方法数论是研究数的性质的一门科学，它与中学数学教育有密切的联系.数论问题解法灵活，题型丰富，它是中学数学竞赛试题的源泉之一.下面介绍数论试题的常用方法.1.基本原理为了使用方便，我们将数论中的一些概念和结论摘录如下：我们用(ai,a2,.,an)表示整数a1,a2,an的最大公约数.用a1,a2,，an表示ai,a2,，an的最小公倍数.对于实数x,用x表示不超过x的最大整数，用x=x-x表示x的小数部分.对于整数a,b,若m|(ab),m1,则称a,b关于模m同余，记为ab(modm).对于正整数m,用(m)表示1,2,，m中与m互质的整

2、数的个数，并称(m)为欧拉函数.对于正整数m,若整数r1,r2,.,rm中任何两个数对模m均不同余,则称r,r2,.,rm为模m的一个完全剩余系；若整数1,2,.,)中每一个数都与m互质，且其中任何两个数关于模m不同余，则称1,2,./(m)为模m的简化剩余系.定理1设a,b的最大公约数为d,则存在整数x,y,使得dxayb.n.niije理2(1)右aib(modm),i1,2,，n,x1x2(modm),贝Uai%bix2;i1i1(2)若ab(modm),d(a,b),d|m,则与b(modm)；ddd(3)若ab,d(a,b),且(d,m)1,则亘(modm)；dd(4)若ab(mod

3、m)i1,2,.,n,M=mm?,.,mn,则ab(modM).定理3(1)x1xxx1;(2)xyxy;(3)设p为素数，则在n!质因数分解中，p的指数为4.k1p定理4(1)若口,),.,7是模m的完全剩余系，(a,m)1,则ar1b,ar2b,.,armb也是模m的完全剩余系;(2)若r1,r2，,r(m)是模m的简化剩余系，(a,m)1,则ar1,ar2,ar(m)是模m的简化剩余系.定理5(1)若(m,n)1,则(mn)(m)(n).(2)若n的标准分解式为npi1P22.pj,其中i,2，k为正整数，Pi,P2,.Pk为111互不相同的素数，则(n)n(1一)(1一).(1一).P

4、1P2Pk对于以上结论的证明，有兴趣的读者可查阅初等数论教材.2方法解读对于数论试题，除直接运用数论的基本原理外，常用的基本方法还有因式(因数)分解法，配对法,分组法，估值法，同余方法，构造法，调整法，数学归纳法与反证法.下面分别予以说明2.1基本原理的应用ab例1设正整数a,b,c的最大公约数为1,并且士。(1),证明：(ab)是一个完全平ab方数.证：设(a,b)d,aad,bb1d，其中，)1.由于(a,b,c)1,故有(d,c)1.由(1)覆行a1b1da1cb1c(2)由(2)知，a11ble，又(a1,b1)1,a11c.同理可证b1|c,从而有a1blic，设ca1b1k,k为正

5、整数，代入(2)得dk(a14)(3)2由(3)知k|d,又k|c,k|(d,c)1,k1.da1b1.abd(a1b1)d.故成立.例2设n为大于1的奇数，k1,k2,，kn为给定的整数.对于1,2,.,n的排列P(a1，a2,.,an),n记s(P)kiai,试证存在1,2,.,n的两个不同的排列BC,使得n!|s(B)s(C).证:假设对于任意两个不同的排列B、C,均有n!不整除s(B)S(C).令X为1,2,.,n的所有排列构成的集合，则s(P)|PX为模n!的一个完全剩余系，从而有s(P)i(1-ngodn!)(1)PXi12又s(P)(nki2)=，nkiPXPXi12i1而n为大

6、于1的奇数，所以由(1),(2)得(1n!)n!地上工nki0(modn!).22i1n!又(1n!,n!)1,所以一0(modn!),矛盾.故，存在RCX,BC,使得n!|s(B)s(C).22.2 因式(数)分解数论中许多问题直接与因式(数)分解相关联，如合数问题，整除问题等常常是要证明某种分解式的存在.数的标准分解式本身就是一种特定形式的因数分解.在不定方程的求解与一些代数式的求值中，因式(数)分解能帮助我们确定某些变量的取值范围，寻找到解题的方法.例3求三个素数，使得它们的积为和的5倍.解：易知a,b,c中必有一个为5,不妨设c5,则有abab5,从而有(a1)(b1)6.a11a12

7、因为a1与b1均为正整数，不妨设ab,则有或，从而知b16b13a2,b7.故所求的三个素数为2,5,7.2.3 配对例4设k为正奇数，证明：123.n整除1k2k.nk.分析因为123.nn(n1).故需证n(n1)|2(1k2k.nk),注意到当k为奇2证 2(1k 2k数时，xkyk可因式分解，因此可将2(1k2k.nk)中的2n个数两两配对.n)=1(n1)2(n2).(n1)12n,而当k为奇数时，ab|ak bk,从而知 n| 2 1k 2k又 2T 2kk=1nk 2k (n 1)k . nk 1k,(n 1)|2(1k2k由(1)(2)知，n(n 1)|2(1k2knk),故结

8、论成立.质:2.4分组例5 (1990年高中联赛试题)设E 1,2,.,200 , Ga1，a2,., a100E,且 G 具有下列性对任何1ij100,aiaj201；100ai 10080.i 1证：对于 1 i 100，令 i 2i 1, i 201i. Ei i, J ,则G中恰含Ei中的一个元素.设G中有k个奇数h , i2ik ,有s个偶数j1 , j2 ,.,js，这里试证：G中的奇数的个数是4的倍数，且G中所有数的平方和是一定数.精品资料i1,i2,.,ik,j2,.,js=1,2,.,100.由题设k知,10080=t 1sit r 1jrk(201t 1it)jrk201t

9、 1it +'tsjrr 1201k“+(2200)=201kit10100 . . 201k,t20k由于it为偶数，所以4|2t 1it，又 4|20,所以 4|201k,1002aii 1s2itr 1k2 _jr =t 1(201it)2sk22jr =201r 1t 1k2 201 t 1it2itsj2)r 1= 2012kk201it+(2242622002)=201(201k2ki)+4100(1001)(2001(2)tit6将(1)代入(2)得a；201(20)4100101201=1349380.ii62.5估值例6令an表示前n个质数之和，即a12,a2235,

10、a323510,，证明：对任意的正整数n,区间an,an1中包含有一个完全平方数.分析：设质数从小到大依次为Pi,P2,.,Pk，要结论成立，只要存在正整数m,使得anm2an1,只要Janm1,只要JOn二y'an1,只要aman12,an,只要Pn112$,只要(Pn11)24an4(P1P2Pk)(1)证：直接验证易知a1,a2,a2,a3,a3,a41,a4,as中都含有1个完全平方数.当n5时，我们证明：(1)式成立.为此，令f(n1)(Pn11)240P2.Pk),22则f(n1)f(n)(Pn11)(Pn1)4Pn=(Pn1Pn)(Pn1Pn2)4pn.当n2时，pn为奇

11、数，故Pn1Pn2,f(n1)f(n)2(Pn1Pn22=201Pn2)0,故当n2时，数列f(n)为递增数列.由于22f(5)(P51)4(P1P2P3P4)=(111)4(2357)=32>0所以当n5时，f(n)f(5)0.故当n5时(1)式成立.例7求出不定方程(n1)!nk1(1)的全部正整数解.解当n2时，易得k1;当n2时,(1)式左边为偶数，故右边也是偶数，所以n为奇数.当n3时，由2!3k1,得k1.当n5时，由4!5k1,得k2.当n5且为奇数时，工n3,2,故24|(n2)!,即(n1)|(n2)!,因此222(n1)2|(n1)!,所以(n1)2|(nk1).另一

12、方面，由二项式定理知nk1(n1)1)k1=A(n1)2+k(n1).其中A为整数，所以(n1)2|k(n1),故(n1)|k,因此kn1,故有nk1nn11(n1)!.这说明当n5时，方程无解，故方程(1)的解为(n,k)(2,1),(3,1),(5,2).2.6 同余例8证明993993991991能被1984整除.证9939932991991991993(991)=(991)(991)=(49519841)(991)(991)(mod1984),二993993991991(991)9919919910(mod1984).1984|993993991991.例9用1,2,3,4,5,6,7

13、组成的无重复数字的7位数，证明：这些7位数中没有一个是另一个的倍数.证：若有两个7位数a,b,使得akb(1)由于a,b均是由1,2，,7所排成，故2k7由(1)得akb(mod9),1k1(mod9),即k1(mod9),这与2k9矛盾，故结论成立.2.7 构造例10若一个正整数的标准分解中，每个素约数的幕次都大于1,则称它为幕数，证明：存在无穷多个互不相同的正整数，它们及它们中任意多个不同数的和都不是幕数.证：将全体素数从小到大依次记为Pi,P2,Pn,.入2222一、十八令aPi,a2P1P2,当n2时，ananPnPnPiP2Pn1Pn,下证：a1，a2,，an,合题意.事实上，Pn|

14、an,但P2|an,所以Hn不是幕数.又对于11i2ik,ai2aik222ahai2aikah(1一一)二(1APi1)=RP2ph1ph(1ApJ,ahah其中A为正整数.因为(Pi1,1APi1)1,所以Pi1在(q1ai2aik)的标准分解中的幕次为1,因而不是幕数.例11设1,2,3,2011中质数的个数为a,n为正整数且1na,求证必有2011个连续正整数，其中恰有n个质数.证:令Akk,k1,k2,k2010,并令f(k)为Ak中质数的个数，则易知fa,f(2012!2)0.对于k1,2,(2012!1),显然有|f(k1)f(k)|1,所以又t于0na,必存在一个k0,使得f(

15、k0)n,从而Ak0中的2011个连续整数满足要求.2.8 数学归纳法例12设n是正整数，求证：512132n32n224n1.证：令f(n)32n32n224n1.因为f(1)0,所以5121f(1)，假设5121f(n),那么对于n1,因为f(n1)f(n)8(32n8n1),所以要证5121f(n1),只需证512|8(32n8n1),即只需证明64|(32n8n1).为此，令g(n)32n8n1.显然有641g(1)0,假设641g(n),由于g(n1)g(n)8(9n1)64(9n19n21),因此641g(n1),由归纳法原理知对一切n,有64132n8n1,从而有5121f(n1),再由归纳法原理知，对于正整数n,有512|f(n).2.9 反证法例13试证方程X32y34z30(1)无正整数解.分析：若(x,y,z)为(1)的一组解，则X为偶数，令X2X1，则4x；y32z30,从而知y为偶数，再令y2y1，代入得2x34y3z30,故z为偶数，再令z2乙，代入得xi32y；4z30,因此(、，1,乙)也是方程(1)的解.这样由方程(1)的一组正整数解(x,y,z)必可得到另一组正整数解(刈，丫1,乙)，且xix.因此，若开始取得的正整数解使得x达到最小