數(shù)學(xué)競(jìng)賽數(shù)論問(wèn)題復(fù)習(xí)課程

1、數(shù)學(xué)競(jìng)賽數(shù)論問(wèn)題學(xué)習(xí)好資料高中數(shù)學(xué)競(jìng)賽中數(shù)論問(wèn)題的常用方法數(shù)論是研究數(shù)的性質(zhì)的一門科學(xué)，它與中學(xué)數(shù)學(xué)教育有密切的聯(lián)系.數(shù)論問(wèn)題解法靈活，題型豐富，它是中學(xué)數(shù)學(xué)競(jìng)賽試題的源泉之一.下面介紹數(shù)論試題的常用方法.1.基本原理為了使用方便，我們將數(shù)論中的一些概念和結(jié)論摘錄如下：我們用(ai,a2,.,an)表示整數(shù)a1,a2,an的最大公約數(shù).用a1,a2,，an表示ai,a2,，an的最小公倍數(shù).對(duì)于實(shí)數(shù)x,用x表示不超過(guò)x的最大整數(shù)，用x=x-x表示x的小數(shù)部分.對(duì)于整數(shù)a,b,若m|(ab),m1,則稱a,b關(guān)于模m同余，記為ab(modm).對(duì)于正整數(shù)m,用(m)表示1,2,，m中與m互質(zhì)的整

2、數(shù)的個(gè)數(shù)，并稱(m)為歐拉函數(shù).對(duì)于正整數(shù)m,若整數(shù)r1,r2,.,rm中任何兩個(gè)數(shù)對(duì)模m均不同余,則稱r,r2,.,rm為模m的一個(gè)完全剩余系；若整數(shù)1,2,.,)中每一個(gè)數(shù)都與m互質(zhì)，且其中任何兩個(gè)數(shù)關(guān)于模m不同余，則稱1,2,./(m)為模m的簡(jiǎn)化剩余系.定理1設(shè)a,b的最大公約數(shù)為d,則存在整數(shù)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)設(shè)p為素?cái)?shù)，則在n!質(zhì)因數(shù)分解中，p的指數(shù)為4.k1p定理4(1)若口,),.,7是模m的完全剩余系，(a,m)1,則ar1b,ar2b,.,armb也是模m的完全剩余系;(2)若r1,r2，,r(m)是模m的簡(jiǎn)化剩余系，(a,m)1,則ar1,ar2,ar(m)是模m的簡(jiǎn)化剩余系.定理5(1)若(m,n)1,則(mn)(m)(n).(2)若n的標(biāo)準(zhǔn)分解式為npi1P22.pj,其中i,2，k為正整數(shù)，Pi,P2,.Pk為111互不相同的素?cái)?shù)，則(n)n(1一)(1一).(1一).P

4、1P2Pk對(duì)于以上結(jié)論的證明，有興趣的讀者可查閱初等數(shù)論教材.2方法解讀對(duì)于數(shù)論試題，除直接運(yùn)用數(shù)論的基本原理外，常用的基本方法還有因式(因數(shù))分解法，配對(duì)法,分組法，估值法，同余方法，構(gòu)造法，調(diào)整法，數(shù)學(xué)歸納法與反證法.下面分別予以說(shuō)明2.1基本原理的應(yīng)用ab例1設(shè)正整數(shù)a,b,c的最大公約數(shù)為1,并且士。(1),證明：(ab)是一個(gè)完全平ab方數(shù).證：設(shè)(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，設(shè)ca1b1k,k為正

5、整數(shù)，代入(2)得dk(a14)(3)2由(3)知k|d,又k|c,k|(d,c)1,k1.da1b1.abd(a1b1)d.故成立.例2設(shè)n為大于1的奇數(shù)，k1,k2,，kn為給定的整數(shù).對(duì)于1,2,.,n的排列P(a1，a2,.,an),n記s(P)kiai,試證存在1,2,.,n的兩個(gè)不同的排列BC,使得n!|s(B)s(C).證:假設(shè)對(duì)于任意兩個(gè)不同的排列B、C,均有n!不整除s(B)S(C).令X為1,2,.,n的所有排列構(gòu)成的集合，則s(P)|PX為模n!的一個(gè)完全剩余系，從而有s(P)i(1-ngodn!)(1)PXi12又s(P)(nki2)=，nkiPXPXi12i1而n為大

6、于1的奇數(shù)，所以由(1),(2)得(1n!)n!地上工nki0(modn!).22i1n!又(1n!,n!)1,所以一0(modn!),矛盾.故，存在RCX,BC,使得n!|s(B)s(C).22.2 因式(數(shù))分解數(shù)論中許多問(wèn)題直接與因式(數(shù))分解相關(guān)聯(lián)，如合數(shù)問(wèn)題，整除問(wèn)題等常常是要證明某種分解式的存在.數(shù)的標(biāo)準(zhǔn)分解式本身就是一種特定形式的因數(shù)分解.在不定方程的求解與一些代數(shù)式的求值中，因式(數(shù))分解能幫助我們確定某些變量的取值范圍，尋找到解題的方法.例3求三個(gè)素?cái)?shù)，使得它們的積為和的5倍.解：易知a,b,c中必有一個(gè)為5,不妨設(shè)c5,則有abab5,從而有(a1)(b1)6.a11a12

7、因?yàn)閍1與b1均為正整數(shù)，不妨設(shè)ab,則有或，從而知b16b13a2,b7.故所求的三個(gè)素?cái)?shù)為2,5,7.2.3 配對(duì)例4設(shè)k為正奇數(shù)，證明：123.n整除1k2k.nk.分析因?yàn)?23.nn(n1).故需證n(n1)|2(1k2k.nk),注意到當(dāng)k為奇2證 2(1k 2k數(shù)時(shí)，xkyk可因式分解，因此可將2(1k2k.nk)中的2n個(gè)數(shù)兩兩配對(duì).n)=1(n1)2(n2).(n1)12n,而當(dāng)k為奇數(shù)時(shí)，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),故結(jié)

8、論成立.質(zhì):2.4分組例5 (1990年高中聯(lián)賽試題)設(shè)E 1,2,.,200 , Ga1，a2,., a100E,且 G 具有下列性對(duì)任何1ij100,aiaj201；100ai 10080.i 1證：對(duì)于 1 i 100，令 i 2i 1, i 201i. Ei i, J ,則G中恰含Ei中的一個(gè)元素.設(shè)G中有k個(gè)奇數(shù)h , i2ik ,有s個(gè)偶數(shù)j1 , j2 ,.,js，這里試證：G中的奇數(shù)的個(gè)數(shù)是4的倍數(shù)，且G中所有數(shù)的平方和是一定數(shù).精品資料i1,i2,.,ik,j2,.,js=1,2,.,100.由題設(shè)k知,10080=t 1sit r 1jrk(201t 1it)jrk201t

9、 1it +'tsjrr 1201k“+(2200)=201kit10100 . . 201k,t20k由于it為偶數(shù)，所以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個(gè)質(zhì)數(shù)之和，即a12,a2235,

10、a323510,，證明：對(duì)任意的正整數(shù)n,區(qū)間an,an1中包含有一個(gè)完全平方數(shù).分析：設(shè)質(zhì)數(shù)從小到大依次為Pi,P2,.,Pk，要結(jié)論成立，只要存在正整數(shù)m,使得anm2an1,只要Janm1,只要JOn二y'an1,只要aman12,an,只要Pn112$,只要(Pn11)24an4(P1P2Pk)(1)證：直接驗(yàn)證易知a1,a2,a2,a3,a3,a41,a4,as中都含有1個(gè)完全平方數(shù).當(dāng)n5時(shí)，我們證明：(1)式成立.為此，令f(n1)(Pn11)240P2.Pk),22則f(n1)f(n)(Pn11)(Pn1)4Pn=(Pn1Pn)(Pn1Pn2)4pn.當(dāng)n2時(shí)，pn為奇

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

12、方面，由二項(xiàng)式定理知nk1(n1)1)k1=A(n1)2+k(n1).其中A為整數(shù)，所以(n1)2|k(n1),故(n1)|k,因此kn1,故有nk1nn11(n1)!.這說(shuō)明當(dāng)n5時(shí)，方程無(wú)解，故方程(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、組成的無(wú)重復(fù)數(shù)字的7位數(shù)，證明：這些7位數(shù)中沒(méi)有一個(gè)是另一個(gè)的倍數(shù).證：若有兩個(gè)7位數(shù)a,b,使得akb(1)由于a,b均是由1,2，,7所排成，故2k7由(1)得akb(mod9),1k1(mod9),即k1(mod9),這與2k9矛盾，故結(jié)論成立.2.7 構(gòu)造例10若一個(gè)正整數(shù)的標(biāo)準(zhǔn)分解中，每個(gè)素約數(shù)的幕次都大于1,則稱它為幕數(shù)，證明：存在無(wú)窮多個(gè)互不相同的正整數(shù)，它們及它們中任意多個(gè)不同數(shù)的和都不是幕數(shù).證：將全體素?cái)?shù)從小到大依次記為Pi,P2,Pn,.入2222一、十八令aPi,a2P1P2,當(dāng)n2時(shí)，ananPnPnPiP2Pn1Pn,下證：a1，a2,，an,合題意.事實(shí)上，Pn|

14、an,但P2|an,所以Hn不是幕數(shù).又對(duì)于11i2ik,ai2aik222ahai2aikah(1一一)二(1APi1)=RP2ph1ph(1ApJ,ahah其中A為正整數(shù).因?yàn)?Pi1,1APi1)1,所以Pi1在(q1ai2aik)的標(biāo)準(zhǔn)分解中的幕次為1,因而不是幕數(shù).例11設(shè)1,2,3,2011中質(zhì)數(shù)的個(gè)數(shù)為a,n為正整數(shù)且1na,求證必有2011個(gè)連續(xù)正整數(shù)，其中恰有n個(gè)質(zhì)數(shù).證:令A(yù)kk,k1,k2,k2010,并令f(k)為Ak中質(zhì)數(shù)的個(gè)數(shù)，則易知fa,f(2012!2)0.對(duì)于k1,2,(2012!1),顯然有|f(k1)f(k)|1,所以又t于0na,必存在一個(gè)k0,使得f(

15、k0)n,從而Ak0中的2011個(gè)連續(xù)整數(shù)滿足要求.2.8 數(shù)學(xué)歸納法例12設(shè)n是正整數(shù)，求證：512132n32n224n1.證：令f(n)32n32n224n1.因?yàn)閒(1)0,所以5121f(1)，假設(shè)5121f(n),那么對(duì)于n1,因?yàn)閒(n1)f(n)8(32n8n1),所以要證5121f(n1),只需證512|8(32n8n1),即只需證明64|(32n8n1).為此，令g(n)32n8n1.顯然有641g(1)0,假設(shè)641g(n),由于g(n1)g(n)8(9n1)64(9n19n21),因此641g(n1),由歸納法原理知對(duì)一切n,有64132n8n1,從而有5121f(n1),再由歸納法原理知，對(duì)于正整數(shù)n,有512|f(n).2.9 反證法例13試證方程X32y34z30(1)無(wú)正整數(shù)解.分析：若(x,y,z)為(1)的一組解，則X為偶數(shù)，令X2X1，則4x；y32z30,從而知y為偶數(shù)，再令y2y1，代入得2x34y3z30,故z為偶數(shù)，再令z2乙，代入得xi32y；4z30,因此(、，1,乙)也是方程(1)的解.這樣由方程(1)的一組正整數(shù)解(x,y,z)必可得到另一組正整數(shù)解(刈，丫1,乙)，且xix.因此，若開始取得的正整數(shù)解使得x達(dá)到最小