數(shù)學(xué)競(jìng)賽中的數(shù)論問(wèn)題

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