數(shù)學(xué)競賽中的數(shù)論問題

羅增儒引言研究正整數(shù)的一個數(shù)學(xué)分支.什么是正整數(shù)呢?人們借助于“集合”和“后繼”關(guān)系給正整數(shù)(當時也即自然數(shù))作過本質(zhì)的描述，正整數(shù)1,2,3,…是這樣一個集合N:(1)有一個最小的數(shù)1.(2)每一個數(shù)a的后面都有且只有一個后繼數(shù)a';除1之外，每一個數(shù)的都是且只是一個數(shù)的后繼數(shù).(3)對N_的子集M,假設(shè)1∈M,且當a∈M時，有后繼數(shù)a1∈M,那么M=N.沒有成熟到解決它的程度.比方，哥德巴赫猜測：1742年6月7日，普魯士派往俄國的一位公使哥德巴赫寫信給歐拉，提出“任何偶數(shù)，由4開始，都可以表示為兩個素數(shù)和的形式，任何奇數(shù)，由7開始，都可以表示為三個素數(shù)的和.后者是前者的推論，也可獨立證明(已解決).“表示為兩個素數(shù)和的形式”就是著名的哥德巴赫猜測，簡稱1+1.1900年希爾伯特將其歸入23個問題中的第8個問題.1966年陳景潤證得：一個素數(shù)+素數(shù)×素數(shù)(1+2),至今仍無人超越.的話：“自然科學(xué)的皇后是數(shù)學(xué)，數(shù)學(xué)的皇冠是數(shù)論，哥德巴赫猜測那么是皇冠上的明珠.……”陳景的明珠”僅一步之遙.●數(shù)論題涉及的知識不是很多，但用不多的知識來解決問題往往就需要較強的能力和精明多的技巧，有人說：用以發(fā)現(xiàn)數(shù)學(xué)人才，在初等數(shù)學(xué)中再也沒有比數(shù)論教材更好的課程了.任何學(xué)生如能把當今一本數(shù)論教材中的練習(xí)做出，就應(yīng)當受到鼓勵，勸他(她)將來去從事數(shù)學(xué)方面的工作(U.Dudley《數(shù)論根底》前言).下面，是一個有趣的故事.題加以考察(1959):如果你手頭上有n+1個正整數(shù)，這些正整數(shù)小于或等于2n,那么你一定有一對不到12歲的波薩只用了1分半鐘，就給出了問題的解答.他將1～2n分成(1,2),(3,4),…,(2n-1,2n)共n個抽屜，手頭的n+1必定互素.數(shù)，幾何，初等數(shù)論，組合初步(俗稱代數(shù)題、幾何題、算術(shù)題和智力題).高中競賽加試四道題正好3、4、5、8、9、11等數(shù)整除的判定；素數(shù)和合數(shù)，最大公約數(shù)與最小公倍數(shù)；奇數(shù)和偶數(shù)，奇偶性分方程.根據(jù)已出現(xiàn)的試題統(tǒng)計，中學(xué)數(shù)學(xué)競賽中的數(shù)論問題的主要有8個重點類型：(1)奇數(shù)與偶數(shù)(奇偶分析法、01法);(3)平方數(shù)；(4)整除；(5)同余；(6)不定方程；(7)數(shù)論函數(shù)、[x]高斯函數(shù)、φ(n)歐拉函數(shù)；(8)進位制(十進制、二進制).下面，我們首先介紹數(shù)論題的根本內(nèi)容(10個定義、18條定理),然后，對數(shù)學(xué)競賽中的數(shù)論問題中學(xué)數(shù)學(xué)競賽中的數(shù)論問題涉及的數(shù)論內(nèi)容主要有10個定義、18條定理.定義1(帶余除法)給定整數(shù)a,b,b≠0,如果有整數(shù)q,r(O≤r<|b1)滿足定義5大于1且除1及其自身外沒有別的正整數(shù)因子的正整數(shù)，稱為素數(shù)(也稱質(zhì)數(shù)).其余大于1的正整數(shù)稱為合數(shù)；數(shù)1既不是素數(shù)也不是合數(shù).證明1先證存在性.作序列相減(q-q?)b=r?-r,注：如果取消O≤r<b,當r<0或r>b,不保證唯一.經(jīng)典方法：緊扣定義，構(gòu)造法證存在性，反證法證唯一性.證明2.只證存在性，用高斯記號，由有,故存在a=qb+r=qb+(b+r)=b(q即M有r比r更小，這與r為最小值矛盾.證明設(shè)A={a,b的公約數(shù)},B={b,c的公約數(shù)}.任J得A=B.有A中元素的最大值=B中元素的最大值，即注：這是輾轉(zhuǎn)相除法求最大公約數(shù)的理論根底.經(jīng)典方法：要證明A=B,只需證AB且BA定理3對任意的正整數(shù)a,b,有的公倍數(shù)，那么存在正整數(shù)m使k=m[a,b],有(2)ax?+by?=(a,b).得得r=a(x-qx?)x+b(y-qY?)<ax〔2〕由(1)有p=P·P?…較P,+1>1.2是素數(shù)，而大于2的偶數(shù)都是合數(shù)，所以2是唯一的偶素數(shù).注：這個證明中，包含著數(shù)學(xué)歸納法的早期因素：假設(shè)假設(shè)有n個素數(shù)，便有n+1個素數(shù).(構(gòu)造法、反證法〕秒定理8(整除的性質(zhì))整數(shù)a,b,c通常指非零整數(shù)定理9(同余的性質(zhì))設(shè)a,b,c,d,m為整數(shù)，m>0,(1)假設(shè)a=b(modm)且b=c(modm),那么a=c(modm);證明由a=b(modm)且b=c(modm),a-b=mq,b-c=mq?'(2)假設(shè)a=b(modm)且c=d(modm),那么a+c=b+d(modm)且ac=bd(modm).a-b=mg?,c-d=mq?,對①直接相加,有對①分別乘以c,b后相加，有ac-bd=(ac-bc)-(bc-bd)=m(c(3)假設(shè)a=b(modm),那么對任意的正整數(shù)n有a*=b°(modm)且an=bn(modmn).得a2*1+b31=(a+b)(a2~2-a2~>b+a2**b2-…-ab2~3+b2*2)·a2”-b2”=(a+b)(a2~1-a2~-b+a2~*b2-…+ab2~2-b^*')設(shè) 定理11給定整數(shù)k≥2,對任意的正整數(shù)n,都有唯一的k進制表示.如定理12(算術(shù)根本定理)每個大于1的正整數(shù)都可分解為素數(shù)的乘積，而且不計因數(shù)的順序時，證明1先證明，正整數(shù)n可分解為素數(shù)的乘積①下面證明分解式是唯一的.假設(shè)n還有另一個分解式n=q?9?*9’P?=9?·P?P?…Pm=q?Q?…q?·證明2用第二數(shù)學(xué)歸納法證明P?=9;,q?=P;’又P?=q?≥q?=P;≥所以P?=9P?P?…P=9?Q?…q?·n=P“P?“2…P.注省略號其實是有限項之和.畫線示意50!中2的指數(shù).假設(shè)不然，存在t,s,l≤t<s≤p-1,使sa=pq?+r?,再把上述p-1個等式相乘，有其中M是一個整數(shù).亦即〔1〕a=1,命題顯然成立.故有這說明，命題對a=k+1是成立.由容斥原理得注示意n=3的容斥原理.(1)必要性(方程有解必須滿足的條件).假設(shè)方程存在整數(shù)解，記為那么(2)充分性(條件能使方程有解).假設(shè)d|c,可設(shè)c=de由于形如ax+by的數(shù)中有最小正數(shù)ax?+by?=(a,b).兩邊乘以e,得這說明方程有解方程的一切整數(shù)解可以表示為①證明直接代入知①是方程的整數(shù)解，下面證明任意一個整數(shù)解都有①的形式.由(x?,yo)是方程的一個解，有ax+by=c,相減a(x-x?)+b(y-y?)=0.3有得方程的任意一個整數(shù)解可以表示為定義10(平面整點)在平面直角坐標系上，縱橫坐標都是整數(shù)的點稱為整點(也稱格點).類似地可以定義空間整點.第二講數(shù)論題的范例講解主要講幾個重要類型：奇數(shù)與偶數(shù)，約數(shù)與倍數(shù)(素數(shù)與合數(shù)),平方數(shù)，整除，同余，不定方程，數(shù)論函數(shù)等.重點是通過典型范例來分析解題思路、提煉解題方法和穩(wěn)固根本內(nèi)容.整數(shù)按照能否被2整除可以分為兩類，一類余數(shù)為0,稱為偶數(shù)，一類余數(shù)為1,稱為奇數(shù).偶數(shù)可以表示為2n,奇數(shù)可以表示為2n-1或2n+1.一般地，整數(shù)被正整數(shù)m去除，按照余數(shù)可以分為m類，稱為模m的剩余類C;={x|x=i(modm)},從每類中各取出一個元素a,∈C,可得模m的完全剩余系(剩余類派出的一個代表團),0,1,2,…,m-1稱為模m的非負最小完全剩余系.數(shù)字化都有聯(lián)系，在數(shù)學(xué)競賽中有廣泛的應(yīng)用.關(guān)于奇數(shù)和偶數(shù)，有下面的簡單性質(zhì)：(1)奇數(shù)≠偶數(shù).(2)偶數(shù)的個位上是0、2、4、6、8;奇數(shù)的個位上是1、3、5、7、9.〔3〕奇數(shù)與偶數(shù)是相間排列的；兩個連續(xù)整數(shù)中必是一個奇數(shù)一個偶數(shù)；(4)奇數(shù)個奇數(shù)的和是奇數(shù)；偶數(shù)個奇數(shù)的和是偶數(shù)；偶數(shù)跟奇數(shù)的和是奇數(shù)；任意多個偶數(shù)的和是偶數(shù).〔5〕除2外所有的正偶數(shù)均為合數(shù)；〔6〕相鄰偶數(shù)的最大公約數(shù)為2,最小公倍數(shù)為它們乘積的一半.(7)偶數(shù)乘以任何整數(shù)的積為偶數(shù).(9)乘積為奇數(shù)的充分必要條件是各個因數(shù)為奇數(shù).〔10〕n個偶數(shù)的積是2”的倍數(shù).是偶數(shù).例1-1(1986,英國)設(shè)q?,a?,…,a?是整數(shù)，b,b?,…,b,是它們的一個排列，證明數(shù)減小數(shù)),所得的14個差恰好為1,2,…,14?解考慮14個差的和S,一方面解(1)4堆是不能保證的.如4堆的奇偶性為：(反例)(奇奇),(偶偶),(奇偶),(偶奇).例4有n個數(shù)xj,x?,…,X?-,x?,它們中的每一個要么是1,要么是-1.假設(shè)xX?+X?X?+…+…+Xr-X+x,X?=0,求證4|n.x?X?+X?X?+…+…+X?-Xn(-1)(+1)?=xX?*X?5;…*-×,*X所以，n為4的倍數(shù)，4|n.(q?,a?,…,a,-,a中至少有2個偶數(shù))第二步證至少有2個偶數(shù).連一線段，可得n+1條互不重疊的線段，證明在此n+1條線段中，以一個有理點和一個無理點為端點(q?a?)(a?a?)(a?a?)…(q??Q??)=(-1=a?(a?a?…a?-)2an+?=q(1)短除法.(2)分解質(zhì)因數(shù)法.設(shè)b=pp?·…P?2,β≥0,i=1,2,…,k.那么(a,b)=p*p?…P,解(1)方法1分解質(zhì)因數(shù)法.由得得方法2輾轉(zhuǎn)相除法.或(2)方法1短除法.由得得方法2.分解質(zhì)因數(shù)法.由得正整數(shù)n分別除以2,3,4,5,6,7,8,9,10得到的余數(shù)依次為1,2,3,4,5,6,7,8,9,那么n的最小解依題意，對最小的n,那么n+1是2,3,4,5,6,7,8,9,10的公倍數(shù)得n=2519.解相當于求不定方程15x+27y=6的整數(shù)解.即往小容器里倒2次油，每次倒?jié)M之后就向大容器里倒，大容器倒?jié)M時，小容器里剩有3升油；再重復(fù)一次，可得6升.成立.即命題對n=k+1時成立.由數(shù)學(xué)歸納法知命題對n≥2成立.證明1(反證法)假假設(shè)可約，那么存在①②③④⑤解題分析：(1)去掉反證法的假設(shè)與矛盾就是一個正面證法.(2)式④是實質(zhì)性的進展，說明由此獲得2個解法.消去n,②×3-①×2,得①②③④⑤=1.解題分析：第④相當于①-②;第⑤相當于②-2〔①-②〕=②×3-①×2;所以③式與⑤式的效果是一樣的.例12不存在這樣的多項式f(n)=a?n"+am|n"*+…+n+a?p使f(b)=a,b"+aw-b"~1+…+a;進而對任意的整數(shù)k,有f(b+kp)=a(b+kp)"+a(b+(1)平方數(shù)的個位數(shù)只有6個：0,1,4,5.6.9(2)平方數(shù)的末兩位數(shù)只有22個：00,01,21,41,61,81,04,24,44,64,84,25,16,36,56,76,96,09,29,49,69,89.(4)(2n-1}2=1(mod8).〔6〕但凡不能被3整除的數(shù)，平方后被3除余1.(7)在兩個相鄰整數(shù)的平方數(shù)之間，不能再有平方數(shù).2.平方數(shù)的證明方法(1)反證法.(2)恒等變形法.(4)約數(shù)法.證明該數(shù)有奇數(shù)個約數(shù).3.非平方數(shù)的判別方法(2)約數(shù)有偶數(shù)個的數(shù)不是平方數(shù).〔3〕個位數(shù)為2,3,7,8的數(shù)不是平方數(shù).(4)同余法：滿足下式的數(shù)n都不是平方數(shù).(5)末兩位數(shù)不是：00,01,21,41,61,81,04,24,44,64,84,25,16,36,56,76,96,09,29,49,69,89.如個位數(shù)與十位數(shù)都是都是奇數(shù)的數(shù)，個位數(shù)是6、而十位數(shù)是偶數(shù)的數(shù).例13有100盞電燈，排成一橫行，從左到右，我們給電燈編上號碼1,2,…,99,100.每盞燈由一個拉線開關(guān)控制著.最初，電燈全是關(guān)著的.另外有100個學(xué)生，第一個學(xué)生走過來，把但凡號碼為1的倍數(shù)的電燈的開關(guān)拉了一下；接著第2個學(xué)生走過來，把但凡號碼為2的倍數(shù)的電燈的開關(guān)拉了一下；第3個學(xué)生走過來，把但凡號碼為3的倍數(shù)的電燈的開關(guān)拉了一下，如此等等，最后那個學(xué)生走過來，把編號能被100整除的電燈的開關(guān)拉了一下，這樣過去之后，問哪些燈是亮的?講解(1)直接統(tǒng)計100次拉線記錄，會眼花繚亂.(2)拉電燈的開關(guān)有什么規(guī)律：電燈編號包含的正約數(shù)〔學(xué)生〕才能拉、不是正約數(shù)(學(xué)生〕不能拉，有幾個正約數(shù)就被拉幾次.(3)燈被拉的次數(shù)與亮不亮(開、關(guān))有什么關(guān)系：0123456789關(guān)開關(guān)開關(guān)開關(guān)開關(guān)開燈被拉奇數(shù)次的亮!(4)哪些數(shù)有奇數(shù)個約數(shù)：平方數(shù).(5)1～100中有哪些平方數(shù)：共10個：答案：編號為1,4,9,16,25,36,49,64,81,100共10個燈還亮.例14直角三角形的兩條直角邊分別為正整數(shù)a,b,斜邊為正整數(shù)c,假設(shè)a為素數(shù)，求證證明由勾股定理c2=a2+b2,有為平方數(shù).例152(a+b+1)=2a+(a2-1)+2求證，任意3個連續(xù)正整數(shù)的積不是平方數(shù).證明設(shè)存在3個連續(xù)正整數(shù)n-1,n,n+1(n>1)的積為平方數(shù)，即存在整數(shù)m,使這一矛盾說明，3個連續(xù)正整數(shù)的積不是平方數(shù).個不同元素a,b,使得ab-1不是完全平方數(shù).證明因為2×5-1=32,2×13-1=52,5×13-1=82,所以不是完全平方數(shù)只能是2d-1,5d-1,13d-1.假設(shè)結(jié)論不成立，那么存在正整數(shù)x,y,z,使同時成立，由①知x是奇數(shù)，設(shè)x=2n-1①②③代入①得2d=q2-p2=(q+p)(q-p).證明k是正整數(shù).式中a,b是對稱的，不妨設(shè)a≥b.(1)假設(shè)a=b,那么(2)假設(shè)a>b,由帶余除法定理，可設(shè)a=bs-t(s≥2,0≤t<b,s,t是整數(shù)),那么由且得化簡b2+t2=sbt+s這種證明的方法叫“無窮遞降法”,是17世紀法國數(shù)學(xué)家費馬(Fermat.1601一1665)首創(chuàng)和應(yīng)用的一種方法.整除的判別方法主要有7大類.(2)具體找出q,滿足a=bq.例18任意一個正整數(shù)m與它的十進制表示中的所有數(shù)碼之差能被9整除.2.數(shù)的整除判別法.〔1〕任何整數(shù)都能被1整除.(2)如果一個整數(shù)的末位能被2或5整除，那么這個數(shù)就能被2或5整除.(3)如果一個整數(shù)的末兩位能被4或25整除，那么這個數(shù)就能被4或25整除.(4)如果一個整數(shù)的末三位能被8或125整除，那么這個數(shù)就能被8或125整除.(5)如果一個整數(shù)各數(shù)位上的數(shù)字之和能被3或9整除，那么這個數(shù)就能被3或9整除.a?×10?+a?×101+…+q?×10+q?=a?a×10?+a?-×10~1+…+q?×10+q?=〔6〕如果一個整數(shù)的末三位數(shù)與末三位數(shù)以前的數(shù)字所組成的數(shù)的差能被7或11或13整除，那么這個數(shù)就能被7或11或13整除.又由1001=7×11×13,而7,11,13均為素數(shù)知，m能被7或11或13整除.(7)如果一個整數(shù)的奇位數(shù)字之和與偶位數(shù)字之和的差能被11整除，那么這個數(shù)能被11整除.3.分解法.主要用乘法公式.如=(1+8)m,+(2+7)m?+(3+6)m?得9|S.=(1+9)m?+(2+8)m?+(3+7)m?證明例20-1.2009年9月9日的年、月、日組成“長長久久、永不別離”的桔祥數(shù)字20090909,而它也恰好是一個不能再分解的素數(shù).假設(shè)規(guī)定含素因子20090909的數(shù)為桔祥數(shù)，請證明最簡分數(shù)的分子m是桔祥數(shù).其中p為正整數(shù)，有20090909×n×p=1×2×…×20090907×2009這說明，20090909整除1×2×…×20090907×20090908×m,但20090909為素數(shù)，不能整除1×2×…×20090907×20090908,所以20090909整除m,得m是桔祥數(shù).4.余數(shù)分類法.證明1任何整數(shù)n被3除其余數(shù)分為3類n=3k,n=3k+1,n=3k+2,(1)n=3k時，有證明2得5.數(shù)學(xué)歸納法.6.反證法.7.構(gòu)造法.例22k個連續(xù)整數(shù)中必有一個能被k整除.假設(shè)這k個數(shù)被k除沒有一個余數(shù)為0,那么這k個數(shù)的余數(shù)只能取1,2,…,k-1,共k-1種情況，a+i,a+j,0<i-j<k,與i-j<k矛盾.故k個連續(xù)整數(shù)中必有一個能被k整除.例23k個連續(xù)整數(shù)之積必能被k!整除.(1)假設(shè)這k個連續(xù)整數(shù)為正整數(shù)，那么只須證明，對任何一個素數(shù)p,分子中所含p的方次不低于分母中所含p的方次，由高斯函數(shù)的〔2〕假設(shè)這k個連續(xù)整數(shù)中有0,那么連乘積為0,必能被k!整除.為整數(shù).例24有男孩、女孩共n個圍坐在一個圓周上(n≥3),假設(shè)順序相鄰的3人中恰有一個男孩的那么“3人組”數(shù)值化為其中a+j=aj·有a個，得3(a?+a?+…+a?)=(a?+a?+a?)+(a?+a=3p+(-3)q+(-1)a+b=3(p-q)例25〔1956,中國北京〕證明對任何正整數(shù)n都是整數(shù)，并且用3除時余2.分析只需說明為整數(shù)，但不便說明“用3除時余2”,應(yīng)說明是3的倍數(shù).作變形命題可證.①根據(jù)定義，同余問題可以轉(zhuǎn)化為整除問題來解決；同時，同余本身有很多性質(zhì)，可以直接用來解例26正方體的頂點標上+1或-1,面上標上一個數(shù)，它等于這個面四個頂點處的數(shù)的乘積，求證，這樣得出的14個數(shù)之和不能為0.證明記14個數(shù)的和為S,易知，這14個數(shù)不是+1就是-1,假設(shè)八個頂點都標上+1,那么S=14,命題成立.對于頂點有-1的情況，我們改變-1為+1,那么和S中有4的數(shù)a,b,c,d改變了符號，用S'表示這說明，改變一個-1,和S關(guān)于模4的余數(shù)不變，重復(fù)進行，直到把所有的-1都改變?yōu)?1,那么①②f(x?)=0(mod2)?q+q?+與①矛盾.與②矛盾.未知數(shù)的個數(shù)多于方程個數(shù)的整系數(shù)代數(shù)方程，稱為不定方程.求不定方程的整數(shù)解，叫做解不定方程.解不定方