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

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

羅增儒

引言

數(shù)論的認(rèn)識(shí)：數(shù)論是關(guān)于數(shù)的學(xué)問，主要研究整數(shù)，重點(diǎn)對象是正整數(shù)，對中學(xué)生可以說，數(shù)論是

研究正整數(shù)的一個(gè)數(shù)學(xué)分支.

什么是正整數(shù)呢？人們借助于“集合”和“后繼”關(guān)系給正整數(shù)(當(dāng)時(shí)也即自然數(shù))作過本質(zhì)的描

述，正整數(shù)1,2,3,…是這樣一個(gè)集合

(1)有一個(gè)最小的數(shù)1.

(2)每一個(gè)數(shù)。的后面都有且只有一個(gè)后繼數(shù)除1之外，每一個(gè)數(shù)的都是且只是一個(gè)數(shù)的后

繼數(shù).

這個(gè)結(jié)構(gòu)很像數(shù)學(xué)歸納法，事實(shí)上，有這樣的歸納公理：

(3)對N.的子集M,假設(shè)leM,且當(dāng)awM時(shí)，有后繼數(shù)〃‘EM,那么M=N,.

就是這么一個(gè)簡單的數(shù)集，里面卻有無窮無盡的奧秘，有的奧秘甚至使得人們疑心：人類的智慧還

沒有成熟到解次它的程度.比方，哥德巴赫猜測：

1742年6月7日，普魯士派往俄國的一位公使哥德巴赫寫信給歐拉，提出“任何偶數(shù)，由4開始，

都可以表示為兩個(gè)素?cái)?shù)和的形式，任何奇數(shù)，由7開始，都可以表示為三個(gè)素?cái)?shù)的和.后者是前者的推

論，也可獨(dú)立證明(已解決).“表示為兩個(gè)素?cái)?shù)和的形式”就是著名的哥德巴赫猜測，簡稱1+1.

歐拉認(rèn)為這是對的，但證不出來.

1900年希爾伯特將其歸入23個(gè)問題中的第8個(gè)問題.

1966年陳景潤證得：一個(gè)素?cái)?shù)+素?cái)?shù)x素?cái)?shù)(1+2),至今仍無人超越.

?陳景潤的數(shù)學(xué)教師沈元很重視利用名人、名言、名事去鼓勵(lì)學(xué)生，他曾屢次在開講時(shí)，說過這樣

的話：“自然科學(xué)的皇后是數(shù)學(xué)，數(shù)學(xué)的皇冠是數(shù)論，哥德巴赫猜測那么是皇冠上的明珠.……”陳景

潤就是由此而受到了后示和鼓勵(lì)，展開了艱苦卓絕的終生奮斗和燦爛輝煌的奮斗終生，離摘4又“皇冠上

的明珠”僅一步之遙.

?數(shù)論題涉及的知識(shí)不是很多，但用不多的知識(shí)來解決問題往往就需要較強(qiáng)的能力和精明多的技

巧，有人說：用以發(fā)現(xiàn)數(shù)學(xué)人才，在初等數(shù)學(xué)中再也沒有比數(shù)論教材更好的課程了.任何學(xué)生如能把當(dāng)

今一本數(shù)論教材中的練習(xí)做出，就應(yīng)當(dāng)受到鼓勵(lì)，勸他(她)將來去從事數(shù)學(xué)方面的工作(U.Dudley

《數(shù)論根底》前言).下面，是一個(gè)有趣的故事.

當(dāng)代最高產(chǎn)的數(shù)學(xué)家厄爾多斯聽說一個(gè)叫波薩(匈牙利，1948)的小男孩很聰明，就問了他一個(gè)問

題加以考察(1959)：如果你手頭上有〃+1個(gè)正整數(shù)，這些正整數(shù)小于或等于2〃，那么你一定有一對

整數(shù)是互素的，你知道這是什么原因嗎？

不到12歲的波薩只用了1分半鐘，就給出了問題的解答.他將1?2〃分成(1,2),(3,4),…,

共〃個(gè)抽屜，手頭的，+1個(gè)正整數(shù)一定有兩個(gè)屬于同一抽屜，這兩個(gè)數(shù)是相鄰的正整數(shù),

必定互素.

通過這個(gè)問題，厄爾多斯認(rèn)定波薩是個(gè)難得的英才，就精心加以培養(yǎng)，不到兩年，14歲的波薩就發(fā)

表了圖論中“波薩定理”.

?重視數(shù)學(xué)能力的數(shù)學(xué)競賽，已經(jīng)廣泛采用數(shù)論題目，是數(shù)學(xué)競賽四大支柱之一，四大支柱是：代

數(shù)，幾何，初等數(shù)論，組合初步(俗稱代數(shù)題、幾何題、算術(shù)題和智力題).高中競賽加試四道題正好

是四大模塊各一題，分別是幾何題、代數(shù)題、數(shù)論題、組合題，一試中也會(huì)有數(shù)論題.數(shù)論受到數(shù)學(xué)競

賽的青睞可能還有一個(gè)技術(shù)上的原因，就是它能方便地提供從小學(xué)到大學(xué)各個(gè)層面的、新鮮而有趣的題

R.

數(shù)論題的主要類型：在初中競賽大綱中，數(shù)論的內(nèi)容列有：十進(jìn)制整數(shù)及表示方法；整除性，被2、

3、4、5、8、9、11等數(shù)整除的判定；素?cái)?shù)和合數(shù)，最大公約數(shù)與最小公倍數(shù)；奇數(shù)和偶數(shù)，奇偶性分

析：帶余除法和利用余數(shù)分類：完全平方數(shù)；因數(shù)分解的表示法，約數(shù)個(gè)數(shù)的計(jì)算：簡單的一次不定

方程.

在高中競賽大綱中，數(shù)論的內(nèi)容列有：同余，歐幾里得除法，裝蜀定理，完全剩余類，二次剩余，

不定方程和方程組，高斯函數(shù)［1］，費(fèi)馬小定理，格點(diǎn)及其性質(zhì)，無窮遞降法，歐拉定理",孫子定理".

根據(jù)已出現(xiàn)的試題統(tǒng)計(jì)，中學(xué)數(shù)學(xué)競賽中的數(shù)論問題的主要有8個(gè)重點(diǎn)類型：

(1)奇數(shù)與偶數(shù)(奇偶分析法、01法)；

(2)約數(shù)與倍數(shù)、素?cái)?shù)與合數(shù)：

(3)平方數(shù)；

(4)整除;

(5)同余;

(6)不定方程；

(7)數(shù)論函數(shù)、［可高斯函數(shù)、0(〃)歐拉函數(shù)；

(8)進(jìn)位制(十進(jìn)制、二進(jìn)制).

下面，我們首先介紹數(shù)論題的根本內(nèi)容(10個(gè)定義、18條定理)，然后，對數(shù)學(xué)競賽中的數(shù)論問題

作分類講解.

第一講數(shù)論題的根本內(nèi)容

中學(xué)數(shù)學(xué)競賽中的數(shù)論問題涉及的數(shù)論內(nèi)容主要有10個(gè)定義、18條定理.

首先約定，本文中的字母均表示整數(shù).

定義1(帶余除法)給定整數(shù)見仇如果有整數(shù)小網(wǎng))滿足

a=qb+r,

那么g和廠分別稱為。除以〃的商和余數(shù).特別的，廠=（）時(shí)，那么稱。被〃整除，記作可。，或者說。

是〃的倍數(shù)，而6是。的約數(shù).（夕”的存在性由定理1證明）

定義2（最大公約數(shù)）設(shè)整數(shù)4,生，，勺中至少有一個(gè)不等于零，這〃個(gè)數(shù)的最大公約數(shù)是能

整除其中每一個(gè)整數(shù)的最大正整數(shù)，記作（q,%,,4）.

（%,%,,%）中的4沒有順序，最大公約數(shù)也稱最大公因數(shù).

簡單性質(zhì)：（4嗎,伽同,，㈤）?

一個(gè)功能：可以把對整數(shù)的研究轉(zhuǎn)化為對非負(fù)整數(shù)的研究.

定義3（最小公倍數(shù)）非零整數(shù)q,生，…的最小公倍數(shù)是能被其中每一個(gè)4。所整除

的最小正整數(shù)，記作［4,。,，

簡單性質(zhì)：如果攵是正整數(shù)。力的公倍數(shù)，那么存在正整數(shù)〃?使

證明假設(shè)不然，有攵=河。，0+廠（0<r<［t7,/?］）,曰仁［〃,句都是。/的公倍數(shù)得7?也是41

的公倍數(shù)，但（）<〃<［〃,句，與的最小性矛盾.故攵=聞。,句.

定義4如果整數(shù)。力滿足（。力）=1,那么稱。與〃是互素的（也稱互質(zhì)）.

定義5大十1且除1及其自身外沒有別的止整數(shù)因子的止整數(shù)，稱為素?cái)?shù)（也稱質(zhì)數(shù)J.其余大

于1的正整數(shù)稱為合數(shù)；數(shù)1既不是素?cái)?shù)也不是合數(shù).

定理1假設(shè)。力是兩個(gè)整數(shù)，b>0,那么存在兩個(gè)實(shí)數(shù)qj,使。=夕〃+廠（0工廠<〃），并且以〃

是唯一性.

證明1先證存在性.作序列

,—3b.—2b,—b,0,b,2b,3b,

那么。必在上述序列的某兩項(xiàng)之間，從而存在一個(gè)整數(shù)q,使

qb￡av（q+l）b,

即04。一qb<b,

取r=a-qb,0<r<b,

得a=qb+r,

即存在兩個(gè)實(shí)數(shù)夕，廠，使〃一夕/?十廠（OK/?<〃）.

冉證唯一性.假設(shè)小唯一，那么同時(shí)存在多”與使

4=4力+/（0?q</?）,

a=q2b+r2（（）</;<b）,

相減([_/)〃=與一{，

%一%|〃=,_用<方，

。引4-％|<1，

但|%一%|為整數(shù)，故.一％|二0，得夕i=%，從而4=與.

注：如果取消0<rc〃，當(dāng)廠<()或〃>〃，不保證唯一.

經(jīng)典方法：緊扣定義，構(gòu)造法證存在性，反證法證唯?性.

證明2只證存在性，用高斯記號(hào)，由

記r=q一”,故存在4一使

a=c/b+r(0<r<b).

證明3只證存在性，作集合

M={a-bx\x^Z,a-bx>0]

這是一個(gè)有下界的非空整數(shù)集，其中必有最小的，設(shè)x=g時(shí)，有最小值/上20)

a=qb+r.

再證尸《人，假設(shè)不然，r>b,記/=6+4，有

4=q/7+廠=q/7+(〃+4)=/?(〃+1)+彳

/；=4一/?(夕+1)GM

即M有4比，?更小，這與r為最小值矛盾.

故存在兩個(gè)實(shí)數(shù)使。=4〃+40<〃<人).

定理2設(shè)。/,c是三個(gè)不全為0的整數(shù)，滿足a=q/?+c,其中夕也為整數(shù)，那么(。3)=伍,。).

證明設(shè)4=｛。/的公約數(shù)｝,

B=｛b,c的公約數(shù)｝.

d\a_d\c=a-bq

'=dwB=AuB,

任取d￡A=,d\b^

d\b

,d\bd\b

任取d￡3=<=>=>d￡A=BqA,

d\cd\a=bq+c

得A=B.

有4中元素的最大值=8中元素的最大值，即

(a,〃)=S，c).

注：這是輾轉(zhuǎn)相除法求最大公約數(shù)的理論根底.

經(jīng)典方法：要證明A=8,只需證AqB且

定理3對任意的正整數(shù)。力，有

證明因?yàn)槌?是。功的公倍數(shù)，所以。力的最小公倍數(shù)也是C力的約數(shù)，存在q使

ab=q\ci,b\，

十[〃肉口[a,b]見擊“她

有a=q-——i且1——1為整數(shù)，

bb

故4是。的約數(shù).同理q是〃的約數(shù)，即q是的公約數(shù).下面證明，q是。力的最大公約數(shù).假設(shè)

不然，qv(a,b).有

cib=q\a,b\<(a,b)\a,b\.①

設(shè)攵/T，可見％是。的倍數(shù)，同樣=，攵是〃的倍數(shù)，即k是出。

(〃,/?)(〃,/?)(a.b)(a,b)

的公倍數(shù)，那么存在正整數(shù)/〃但女=〃?[。,5|,有

-^—=ui[ayb]>[a,b],

得ab=q[a,b\>[a,Z?)[a,b\

與①矛盾，所以，q=(a,b),得證句.

ah

?k(。力)q

注也可以由二廠司二R-二值同，得”(4/)，與4<(班)矛盾.

q

兩步必=4。,可,"二(。力)々可以交換嗎？

定理4b是兩個(gè)不同時(shí)為0的整數(shù)，假設(shè)4%+與，0是形如QX+by(x,y是任意整數(shù))的數(shù)中

的最小正數(shù)，那么

(1)axQ+by0ax+by；

(2)a7+甌=(4〃).

證明(1)由帶余除法有

ax+by=(q)+b)%+廠，0<r<ar0+by0,

得〃=a(x-/o)x+。(y-油〈”+by。,

知r也是形如以十力的非負(fù)數(shù)，但辦o+b%是形如ar+外的數(shù)中的最小正數(shù)，故/*=0,即

ar0+by0\ax+by.

(2)由⑴有

ar0+by01a?l+b?0=a，

axQ+by0|a?0+b?l=b,

得aq+/?%是的公約數(shù).另一方面，的每一個(gè)公約數(shù)都可以整除,所以也+打加是

。力的最大公約數(shù),a0+"%=(〃,/?).

推論假設(shè)(。/)=1,那么存在整數(shù)型，使廢+初=1.(很有用)

定理5互素的簡單性質(zhì)：

(1)(1,f/)=l.

(2)(〃,〃+1)=1.

(3)(2/1-1,2/?+1)=1.

(4)假設(shè)〃是一個(gè)素?cái)?shù)，。是任意一個(gè)整數(shù)，且。不能被p整除，那么(a,p)=l.

證明因?yàn)?。,〃)|〃，所以，素?cái)?shù)〃的約數(shù)只有兩種川能：但〃不能被〃

整除，(a,p)wp，得“)=1.

推論假設(shè)〃是一個(gè)素?cái)?shù)，。是任意一個(gè)整數(shù)，那么或(a,p)=〃.

(5)假設(shè)那么存在整數(shù)sj,使as+初=1.(定理4推論〕

(6)假設(shè)(a,b)=l,(a,c)=l,那么(a,〃c)=l.

證明由(。/)=1知存在整數(shù)s,1,使心+初=1.

有a(cs)+bct=c,

得加、)=(〃,c)=l.

(7)假設(shè)?b)=l,那么(a±b,a)=l,(a±b,b)=l,(a±b,ab)=l.

證明(a±〃,a)=(±Z?,a)=(〃M)=1,

(4±仇〃)=(4力)=1,

由⑹(a±b,ab)=\.

⑻假設(shè)(。力)=1,那么(，/〃)=1,其中〃〃為正整數(shù).

證明據(jù)(6)，由(〃㈤=1可得(a、〃)=l.

同樣，由(優(yōu)")=1可得(a"〃)=1.

定理6設(shè)。是大于1的整數(shù)，那么4的除1之外的最小的正約數(shù)^必是素?cái)?shù)，且當(dāng)。是合數(shù)時(shí)，

q<4a.

證明用反證法,假設(shè)q不是素?cái)?shù)，那么存在正整數(shù)數(shù)價(jià)，1</vq,使［|q,但q|a,故有名|。，

這與q是。的除1之外的最小正約數(shù)矛盾，故夕是素?cái)?shù).

當(dāng)。是合數(shù)時(shí)，設(shè)a=那么。i也是。的一個(gè)正約數(shù)，由的最小性得夕wq，從而

2

q<a1q=a,開方得q￡&i.

定理7素?cái)?shù)有無窮多個(gè)，2是唯一的偶素?cái)?shù).

證明假設(shè)素?cái)?shù)只有有限多個(gè)，記為8，生,…,〃〃，作一個(gè)新數(shù)

口=%?小?…?P“+1>L

假設(shè)〃為素?cái)?shù)，那么與素?cái)?shù)只有〃個(gè)Pi，〃2,…，〃〃矛盾.

假設(shè)〃為合數(shù)，那么必有化儀〃],%…，〃"}，使從而〃[1，又與P,>1矛盾.

綜上所述，素?cái)?shù)不能只有有限多個(gè)，所以素?cái)?shù)有無窮多個(gè).

2是素?cái)?shù)，而大于2的偶數(shù)都是合數(shù)，所以2是唯一的偶素?cái)?shù).

注：這個(gè)證明中，包含著數(shù)學(xué)歸納法的早期因素：假設(shè)假設(shè)有〃個(gè)素?cái)?shù)，便有〃+1個(gè)素?cái)?shù).(構(gòu)造

法、反證法)秒

定理8(整除的性質(zhì)〕整數(shù)通常指非零整數(shù)

(1)\\a,-1Rz；當(dāng)。工0時(shí)，a\aftz|O.

⑵假設(shè)@a,awO,那么網(wǎng)《時(shí);假設(shè)他，例>時(shí),那么a=O;假設(shè)">0,且作用,

那么。=/?.

證明由awO,有a=bq,得同=憐同之例.

逆反命題成立“假設(shè)”a,網(wǎng)>同，那么。=0”；

由同工同且網(wǎng)引《得同=例，又或>0,得

(3)假設(shè)a+>=c+d,且e|a,e|6,e|c,那么e|d.

(4)假設(shè)c|〃，b\a,那么c|a.

證明(定義法)由c|〃，b\a,有

b=q}c,a=q2b,

得a=([%)，,

即布.

(5)假設(shè)c|a,那么。c]而.

(6)假?zèng)]c|a,c\b,那么對任意整數(shù)/%〃，c\ma+nb.

證明(定義法)由c|a,c\b,有

a=q]c,b=q2c,

得ma+/?/?=(mq、+〃％)c，

即c\ma+nb.

⑺假設(shè)=且4仇?，那么dC.

證明由(。力)=1知存在整數(shù)S/，使4S+4=1,有

a(cs)+(〃(?)/=c,

因?yàn)閍\bc,所以。整除等式的左邊，進(jìn)而整除等式的右邊，即。卜.

注意不能由。忸。且?！?得出。上.如6|4x9,但6]4且6/9.

(8)假設(shè)(0力)=1,且*,*,那么曲|c.

證明由(。/)=1知存在整數(shù)$,/,使心+初=1,有

acs+bci=c,

又由a|c,〃|c有c=aqi，c=。%代入得

ab(q)s)+ab(q/)=c,

所以砌c.

注意不能由可。且@c得出如不能由6|30且10|3()得出6()|3().

19)假設(shè)a為素?cái)?shù)，且《林，那么々M或a|c.

證明假設(shè)不然，那么且Q/C,由〃為素?cái)?shù)得(a,〃)=l,(a,c)=l,由互素的性質(zhì)(6)得

(tz,Z?c)=1,再由〃為素?cái)?shù)得a|〃c,與4Z?c矛盾.

注意沒有〃為素?cái)?shù)，不能由白匠推出或〃卜.如l6|4x9,但6|4且6|9.

定義6對于整數(shù)。也c,且cwO,假設(shè)c|3-力，那么稱。力關(guān)于模c同余，記作a三b(modc)；

假設(shè)。/(。一。)，那么稱關(guān)于模c不同余，記作。壬伙mode).

定理9(同余的性質(zhì))設(shè)。,兒。,”,6為整數(shù)，相》(),

(1)假設(shè)。三伙mod/%)且b三c(mod〃2),那么。三c(mod〃i)；

證明由。三Z?(modm)且b三c(modm),有

a-b=mq]yb-c=mq2,

a-c=〃?(q+%),

得。三c(modm).

(2)假設(shè)a=/?(modm)且。三d(modm),那么〃+c三。+4(modm)且ac三/7a(mcxim).

證明由。三Z?(modin)且。三"(modin),有

a-b=，nq、,c-d=mq2,①

對①直接相加，有

(a+c)-(O+d)=m(Q+%)，

得a+c=b+d(n】odin).

對①分別乘以c/后相加，有

ac-hd=(^ac-be)-(be-bd^=tn^cqi+bq),

得ac=bd(mod/?t).

(3)假設(shè)。三〃(mod〃?)，那么對任意的正整數(shù)〃有a"=bn(modm)JSLan=bn(modmn).

(4)假設(shè)。三伏mod〃z),且對非零整數(shù)&有川那么￡=工mod?.

KK\Ky

證明由。三Z?(modm)>,有

a=b+mg,

又有均為整數(shù)，目

abm

———i—q，

kkk

定理10設(shè)〃/為整數(shù)，〃為止整數(shù)，

(1)假設(shè)那么(4-6)|(."一力").

a"-bn=(a-3(a'i+an-2b+an-3b2++abn-2-bn-l).

(2)假設(shè)aw-/?,那么(〃+6)|(1小+/E).

〃2,1+一/-3〃+/1/----刈2〃-3+〃〃-2)

(3)假設(shè)"一匕，那么(〃+以?產(chǎn)—廬).

a211-b2n=（a+b）（a2n-l-a2n-2Z>+a2n-V+ab2n~2-b2'1'1）.

定義7設(shè)〃為正整數(shù)，%為大于2的正整數(shù)，q,令，，《“是小于人的非負(fù)整數(shù)，且可>。.假

設(shè)

n1

ti=a^k'+612km'+,,,+a,”_\k+cint,

那么稱數(shù)a.a2ant為〃的左進(jìn)制表示.

定理11給定整數(shù)々>2,對任意的正整數(shù)〃，都有唯一的々進(jìn)制表示.如

-2

n=+a210"+...+am_x10+,0?qY9,q>0（10進(jìn)制）

x,n2

n=a,T'-+a22-++-2+a,n.0<a.<l,a,>0]2進(jìn)制）

定理12（算術(shù)根木定理）每個(gè)大于1的正整數(shù)都可分解為素?cái)?shù)的乘積，而且不計(jì)因數(shù)的順序時(shí)，

這種表示是唯一的

〃=P?P0…PB,

其中Pi<P2V…vP人為素?cái)?shù)，%,％，…，%為正整數(shù).（分解唯一'性）

證明1先證明，正整數(shù)〃可分解為素?cái)?shù)的乘積

…I"?…1?、?/p>

如果大于1的正整數(shù)〃為素?cái)?shù)，命題已成立.

當(dāng)正整數(shù)〃為合數(shù)時(shí)，〃的正約數(shù)中必有一個(gè)最小的，記為〃「那么P1為素?cái)?shù)，有

n=pial,\<ax<n.

如果4為素?cái)?shù)，命題已成立.當(dāng)外為合數(shù)時(shí)，4的最小正約數(shù)〃2為必為素?cái)?shù)，有

n=Pi%=Pip2a2,1v%<4v〃?

這個(gè)過程繼續(xù)進(jìn)行下去，由于〃為有限數(shù)，而每進(jìn)行一步q就要變小一次，于是，經(jīng)過有限次后，

比方加次，〃就變?yōu)樗財(cái)?shù)的乘積

下面證明分解式是唯一的.假設(shè)〃還有另一個(gè)分解式

〃=②

那么有pm…Pm=q。…③

因?yàn)榈仁降挠疫吥鼙?整除，所以左邊也能被名整除，于是％整除由，〃2,中的某一個(gè)化，

但為素?cái)?shù)，所以p,與卬相等：不妨設(shè)1入為Pi,有

Pl=Q.

把等式③兩邊約去Pl=0,得

P2P3…An=%%…%?

再重復(fù)上述步驟，又可得〃2二%,凸=%，…，直到等式某一邊的因數(shù)被全部約完，這時(shí)，如果

另一邊的因數(shù)沒有約完，比方右邊沒有被約完(〃?〈/),那么有

i=—,q「④

但%+-/+2，，%均為素?cái)?shù)，素?cái)?shù)都大于1，有或+闖小2%>1，這說明等式④不可能成立，

兩個(gè)分解式的因數(shù)必然被同時(shí)約完，即分解式是唯一的.

將分解式按P,的遞增排列，并將相同的P,合并成指數(shù)形式，即得

-P\Pl…Pk?

其中P\<Pl<-?<〃人為素?cái)?shù)，四烏,…,%為正整數(shù).

證明2用第二數(shù)學(xué)歸納法證明

n=P\P丁

(1)當(dāng)〃=2,因?yàn)?為素?cái)?shù)，命題成立.

(2)假設(shè)命題對一切大于1而小于〃的正整數(shù)已成立.

這時(shí)，假設(shè)〃為素?cái)?shù)，命題成立；假設(shè)〃不為素?cái)?shù)，必存在。涉，使

n=ab,\<a<n,\<b<n,

由歸納假設(shè)，小于〃的。力可分解為素?cái)?shù)的乘積

〃="+瓜+2???"，P.2WP；+2￡??4〃；，

得〃=〃；〃；???P.Z'42，

適當(dāng)調(diào)整〃；的順序，可得命題對于正整數(shù)〃成立.

由數(shù)學(xué)歸納法，命題對一場大于1的正整數(shù)〃成立.

下面證明分解式是唯一的.假設(shè)〃的分解式不唯一，那么至少有兩個(gè)分解式

n=PR…P,"，

"0%0，0工％?4％，

得P\P1Pm=q9?%?

有四I%％…0且"P/2…P”,，

這就存在?，/乙，使

〃|1%且51匕，

但Pi，4,%,Pj均為為素?cái)?shù),所以

Pi=%，/=Pj，

又Pi=4之1=Pj2%，

所以Pi=l.

把等式兩邊約去Pi=q「得

再重復(fù)上述步驟，又可得0=%，〃3=%，…，直到等式某一邊的因數(shù)被全部約完，這時(shí)，如果

另一邊的因數(shù)沒有約完，比方右邊沒有被約完(m<r),那么有

1=-2,?%?

但。向，或+2,…，0均為素?cái)?shù)，素?cái)?shù)都大于1，有夕”用心+2…Z>1，這說明上述等式不可能成立，

兩個(gè)分解式的因數(shù)必然被同時(shí)約完，即分解式是唯一的.

將分解式按P,的遞增排列，并將相同的〃,?合并成指數(shù)形式，即得

其中P1<〃2<???</〃為素?cái)?shù)，%,。2,…，火為正整數(shù).

定理13假設(shè)正整數(shù)〃的素?cái)?shù)分解式為〃=〃：P2%…那么〃的正約數(shù)的個(gè)數(shù)為

d(〃)=(q+l)(%+l)…(4+1)，

"的一切正約數(shù)之和為

?1+，-1?2+,-1^+1_1

s(/?)=-/^7——L0n——-??…區(qū)n——-.

Pi—P2TP「1

證明對于正整數(shù)〃=〃/力2%..“J*,它的任意一個(gè)正約數(shù)可以表示為

m=p0p/】p/*,0</?,.<ai,①

由于A有0,1,2,…,冬共％十1種取值，據(jù)乘法原理得〃的約數(shù)的個(gè)數(shù)為

"（〃）=（《+1）（%+1）…（%+1）?

考慮乘積

+++2+

（Pi°+P；+,,+P/）（P2°P?',,Pz）4,,（/A°Pk+-+〃*）,

展開式的每一項(xiàng)都是〃的某一個(gè)約數(shù)（參見①），反之，〃的每一個(gè)約數(shù)都是展開式的某一項(xiàng)，于

是，〃的一切約數(shù)之和為

5（〃）=（〃i°+p；+,+〃/）…仇°+〃J+..+〃/）

=P”-1〃2叫〃尸-1

P「1〃2T0T

注構(gòu)造法.

定義8（高斯函數(shù)〕對任意實(shí)數(shù)x,［可是不超過x的最大整數(shù).亦稱［司為x的整數(shù)局部，

［x］<X<［x］+1.

定理14在正整數(shù)〃!的素因子分解式中，素?cái)?shù)〃作為因子出現(xiàn)的次數(shù)是

十???.

證明由于〃為素?cái)?shù)，故在〃!中〃的次方數(shù)是1,2,?,〃多數(shù)中〃的次方數(shù)的總和（注意，假設(shè)"

不為素?cái)?shù)，這句話不成立）.

在1,2,…，〃中，有-個(gè)p的倍數(shù)；在［彳個(gè)〃的倍數(shù)的因式中，有A個(gè)〃2的倍數(shù)；在A

Pp~.pP~

個(gè)〃2的倍數(shù)的因式中，有二個(gè)p'的倍數(shù)：…，如此下去，在正整數(shù)川的素因子分解式中，素?cái)?shù)〃

_P.

作為因子出現(xiàn)的次數(shù)就為

升［升［孫,

注省略號(hào)其實(shí)是有限項(xiàng)之和.

畫線示意50!中2的指數(shù).

50!=2a'365/7%1P13勺7勺9%23%29.31?37?41.43.47

定理15（費(fèi)瑪小定理）如果素?cái)?shù)〃不能整除整數(shù)。，那么〃|（。內(nèi)一1）.

證明1考察下面的〃-1個(gè)等式：

a=pq、+r],0"v〃，

2a=pq2+r2,0<r2<p

=叫T+小，0，<P

由于素?cái)?shù)p不能整除整數(shù)。，所以，p不能整除每個(gè)等式的左邊，得小與,…，弓_|均不為0,只能

取1,2,…,p—1.下面證明不火各不相等.

假設(shè)不然，存在使

§a=pq盧q,

ta=pq,+rt,

IK

相減(s-i)a=p(q、-q)?

應(yīng)有素?cái)?shù)〃整除(S—但素?cái)?shù)〃不能整除。，所以素?cái)?shù)〃整除(S—。，然而由1WZCS《〃一1

可得

O<s-t<p-2<p,

要素?cái)?shù)p整除(s—f)是不可能的，得不弓,各不相等.有

任小T?2??(p-l)=(p-l)!.

再把上述〃-1個(gè)等式相乘，有

(〃-1叱=坳+柏?%，

即(〃_|)!小=帥+(〃—1)!,

其中M是一個(gè)整數(shù).

亦即(〃_1)!(屋Z_1)=帥.

由于〃是素?cái)?shù)，不能整除(〃一1)!,所以素?cái)?shù)〃整除。川一1,得證

H"i)

證明2改證等價(jià)命題：如果素?cái)?shù)〃不能整除整數(shù)。，那么〃'三〃(mod〃).

只需對。=1,2,…，〃—1證明成立，用數(shù)學(xué)歸納法.

(1)4=1,命題顯然成立.

(2)假設(shè)命題對a-A(lWAvp-1)成立，那么當(dāng)a—上十1時(shí)，由于〃|C；,(i一1,2,」〃一1),

故有

（八1）JM+C'*z++C；'k+1

三M+1三A+l（modp）.（用了歸納假設(shè)）

這說明，命題對。=攵+1是成立.

由數(shù)學(xué)歸納法得〃〃三a（mod〃）.

又素?cái)?shù)〃不能整除整數(shù)〃，有（a,p）=l,得

定義9（歐拉函數(shù)）用*（〃）表示不大F〃且與〃互素的正整數(shù)個(gè)數(shù).

定理16設(shè)正整數(shù)〃=p：p2s…〃產(chǎn)，那么

=〃1--

\P\八Pi)IPk)

證明用容斥原理.設(shè)S=[1,2,…記4為S中能被P,整除的數(shù)所組成的集合㈠=1,2,k）,

用|4|表示4中元素的個(gè)數(shù)，有

I止jlariAj=—,…,14。4n…n4|=-------------

PiPjP/2…&

易知，5={1,2,?,〃}中與〃互素的正整數(shù)個(gè)數(shù)為

|AA?AJ,

由容斥原理得

|4n用n…同二同-x⑷+Z|AA^

\<i<k\<i<j<k

-E|A「4na”|++(-i)14n&n?..n4|

l￡i<j<m<k

—+z---------工--------+?--------

14MPi\<i<j<kPiPj\<i<j<m<kPiPjP,nP\P1Pk

A

=wL_y1+yJ_一y—+(-i)—!—

Pi\<i<j<kPiPj\<i<j<m<kPiPjPmPl〃2-Pk

(1V1A(1)

=n1——1——…1——.

IAAPi)IAJ

注示意〃=3的容斥原理.

推論對素?cái)?shù)〃有夕(〃)=〃一1,0(〃。)=〃。一〃"7.

定理17整系數(shù)不定方程3?十外?=c（c心40）存在整數(shù)解的充分必要條件是㈤卜.

證明記〃=(4/?).

(1)必要性(方程有解必須滿足的條件).假設(shè)方程存在整數(shù)解，記為1"="°',那么

[y=加

ax0+by0=c,

由有d|ax()+〃y0,得證(a,9|c.

(2)充分性[條件能使方程有解).假設(shè)d|c,可設(shè)c二曲由于形如ar+by的數(shù)中有最小正數(shù)

O￥()+/?)、)滿足

axi}+by()=(a,b).

兩邊乘以e,得

a?)+b(.)=c

這說明方程有解《x=ex°(}i

.、fx=A,

定理18假設(shè)時(shí)工0,(。力)=1,一且{_°n是整系數(shù)不定方程or+勿=。的一個(gè)整數(shù)解，那么

y=%，

方程的一切整數(shù)解可以表示為

x=x-bt,..

°a(reZ).①

y=yQ+(it,

證明直接代入知①是方程的整數(shù)解，下面證明任意一個(gè)整數(shù)解都有①的形式.

由(毛,%)是方程的一個(gè)解，有

姐=c，

又方程的任意一個(gè)解(X,)，)滿足

ax+by=c,?

相減?(x-^))+/?(y-yo)=O.③

但(。/)=1,故有

〃l()f)，

有^=2ZA=MGZ

-ba

得方程的任意一個(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)是通過典型范例來分析解題思路、提煉解題方法和穩(wěn)固根本內(nèi)容.

一、奇數(shù)與偶數(shù)

整數(shù)按照能否被2整除可以分為兩類，一類余數(shù)為0,稱為偶數(shù)，一類余數(shù)為1,稱為奇數(shù).偶數(shù)

可以表示為2〃，奇數(shù)可以表示為2〃-1或2〃+1.一般地，整數(shù)被正整數(shù)機(jī)去除，按照余數(shù)可以分為〃?

類,稱為模"7的剩余類G={X%三，.(modm)},從每類中各取出一個(gè)元素qwG，可得模用的完全剩

余系(剩余類派出的一個(gè)代表團(tuán))，0,1,2,，機(jī)—1稱為?！ǎ康姆秦?fù)最小完全剩余系.

通過數(shù)字奇偶性質(zhì)的分析而獲得解題重大進(jìn)展的技巧，常稱作奇偶分析，這種技巧與分類、染色、

數(shù)字化都有聯(lián)系，在數(shù)學(xué)競賽中有廣泛的應(yīng)用.

關(guān)于奇數(shù)和偶數(shù)，有下面的簡單性質(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ù).

15)除2外所有的正偶數(shù)均為合數(shù)；

(6)相鄰偶數(shù)的最大公約數(shù)為2,最小公倍數(shù)為它們乘積的一半.

(7)偶數(shù)乘以任何整數(shù)的積為偶數(shù).

18)兩數(shù)和與兩數(shù)差有相同的奇偶性，。+〃三。一〃(mod2).

(9)乘積為奇數(shù)的充分必要條件是各個(gè)因數(shù)為奇數(shù).

(10)〃個(gè)偶數(shù)的積是2"的倍數(shù).

(11)(一1)"=1的充分必要條件是A為偶數(shù)，(一1)人=一1的充分必要條件是攵為奇數(shù).

(12)(2/?)2=0(mod4).(2/?-l)2=l(mod4),(2/2-l|2三1(mod8).

(13)任何整數(shù)都可以表示為〃=2"'(2k一1).

例1（1906,匈牙利J假設(shè)，?！ㄊ?，2,-的某種排列，證明：如果〃是奇數(shù)，那么乘枳

是偶數(shù).

解法1（反證法）假設(shè)儂一1）（出一2）也一〃）為奇數(shù)，那么q-i均為奇數(shù)，奇數(shù)個(gè)奇數(shù)

的和還是奇數(shù)

奇數(shù)=（一-2）++（4-〃）

=（4+〃■）+-+。〃）—（1+2++〃）=0,

這與“奇數(shù)工偶數(shù)，，矛盾.所以（0-1）（生一2）???（（一〃）是偶數(shù).

評析這個(gè)解法說明（4-1）（生-2）-（4-〃）不為偶教是不行的，但沒有指出為偶數(shù)的真正原

因.表達(dá)了整體處理的優(yōu)點(diǎn)，但掩蓋了“乘積”為偶數(shù)的實(shí)質(zhì).

解法2（反證法）假設(shè)（0―1）（勾—2）…（可一〃）為奇數(shù)，那么q-i均為奇數(shù)，q.與i的奇偶

性相反，｛1,2,,〃｝中奇數(shù)與偶數(shù)一樣多，〃為偶數(shù).但條件〃為奇數(shù)，矛盾.所以

（4—1）（%—2）是偶數(shù).

評析這個(gè)解法揭示了（4-1）（%-2）,（《「〃）為偶數(shù)的原因是“〃為奇數(shù)”.那么為什么“〃為

奇數(shù)”時(shí)“乘積”就為偶數(shù)呢？

解法31.2.…，幾生.….凡中有〃+1個(gè)奇數(shù)，放到〃個(gè)括號(hào)，必有兩個(gè)奇數(shù)在同一個(gè)括號(hào)，這

兩個(gè)奇數(shù)的差為偶數(shù)，得（4一1）（生一2）（4-〃）為偶數(shù).

評析這個(gè)解法揭示了（4-1）（%-2）…（為一〃）為偶數(shù)的原因是“當(dāng)〃為奇數(shù)時(shí)，1,2,?一,〃中奇

數(shù)與偶數(shù)個(gè)數(shù)不等，奇數(shù)多，某個(gè)括號(hào)必是兩個(gè)奇數(shù)的差，為偶數(shù)”.

類似題：

例1T（1986,英國）設(shè)%,生，，%是整數(shù)，4也,也是它們的一個(gè)排列，證明

（q—4）（出一偽）（％-白）是偶數(shù).

（4,4，???，的中奇數(shù)與偶數(shù)個(gè)數(shù)不等）

例1-24的前24位數(shù)字為1=3.14159265358979323846264,記《,生，…，生4為該24個(gè)數(shù)

字的任一排列，求證（4-%X%—%）…（。23?。24）必為偶數(shù).

（喑藏3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8,4,6,2,6,4中奇數(shù)與偶數(shù)個(gè)數(shù)不等）

例2能否從1,2,,15中選出10個(gè)數(shù)填入圖的圓圈中，使得每兩個(gè)有線相連的圈中的數(shù)相減〔大

數(shù)減小數(shù)），所得的14個(gè)差恰好為1,2,,14?；5木

解考慮14個(gè)差的和S,一方面V?■/.《

5=1+2+-?+14=105為奇數(shù).W…

另一方面，每兩個(gè)數(shù)。,人的差與其和有相同的奇偶性卜-耳三a+伙mo<12）,因此，14個(gè)差的和S

的奇偶性與14個(gè)相應(yīng)數(shù)之和的和S'的奇偶性相同，由于圖中的每一個(gè)數(shù)。與2個(gè)或4個(gè)圈中的數(shù)相加,

對S'的奉獻(xiàn)為2?；?〃，從而S'為偶數(shù),這與S為奇數(shù)矛盾，所以不能按要求給圖中的圓圈填數(shù).

評析：用了計(jì)算兩次的技巧.對同一數(shù)學(xué)對象，當(dāng)用兩種不同的方式將整體分為局部時(shí)，那么按兩

種不同方式所求得的總和應(yīng)是桂等的，這叫計(jì)算兩次原理成富比尼原理.計(jì)算兩次可以建立左右兩邊關(guān)

系不太明顯的恒等式.在反證法中，計(jì)算兩次又可用來構(gòu)成矛盾.

例3有一大筐蘋果和梨分成假設(shè)干堆，如果你一定可以找到這樣的兩堆，其蘋果數(shù)之和與梨數(shù)之

和都是偶數(shù)，問最少要把這些蘋果和梨分成兒堆？

解（1）4堆是不能保證的.如4堆的奇偶性為：（反例）

（奇奇），（偶偶），（奇偶），（偶奇）.

（2）5堆是可以保證.因?yàn)樘O果和梨數(shù)的奇偶性有且只有上述4種可能，當(dāng)把這些蘋果和梨分成

5堆時(shí)，必有2堆屬于同一奇偶性，其和蘋果數(shù)與梨數(shù)都是偶數(shù).

例4有〃個(gè)數(shù)芭,馬,di，%，它們中的每一個(gè)要么是1，要么是-1.假設(shè)

x1x2+々占+"??+???+Nix”=0，求證41n.

證明由斗有書句再由

王占+看毛+…+怎+當(dāng)玉=0，

知〃個(gè)七七+1中有一半是1,有一半是一1,〃必為偶數(shù)，設(shè)〃=2%.

現(xiàn)把〃個(gè)西一川相乘，有

(-1/(+1/=

可見，及為偶數(shù)，設(shè)4=2〃2,有九=4相，得證4|〃.

例5一個(gè)整數(shù)4,。2,…，4-1，?！?，其積為〃，其和為0，試證4|〃.

證明先證〃為偶數(shù)，假設(shè)不然，由4LQ〃=〃知，ci,%,全為奇數(shù)，其和必為

奇數(shù)，與其和為0（偶數(shù)），故〃必為偶數(shù).（q,%，，《“，可中至少有1個(gè)偶數(shù)）

再證〃為4的倍數(shù)，假設(shè)不然，由〃為偶數(shù)知，4,生,…恰有一個(gè)為偶數(shù)，其余，一1個(gè)數(shù)

全為奇數(shù)，奇數(shù)個(gè)奇數(shù)之和必為奇數(shù)，加上一個(gè)偶數(shù)，總和為奇數(shù)，與。|,生，…，之和為0矛盾，

所以，〃為4的倍數(shù)，4|〃.（/,3,。〃中至少有2個(gè)偶數(shù)）

評析要證4|〃，只須證4,。2，，4i，%中至少有2個(gè)偶數(shù)，分兩步，第一步證至少有1個(gè)偶數(shù)，

第二步證至少有2個(gè)偶數(shù).

例6在數(shù)軸上給定兩點(diǎn)1和正，在區(qū)間（1,血）內(nèi)任取〃個(gè)點(diǎn)，在此〃+2個(gè)點(diǎn)中，每相鄰兩點(diǎn)

連一線段，可得〃+1條互不重疊的線段，證明在此〃+1條線段中，以一個(gè)有理點(diǎn)和一個(gè)無理點(diǎn)為端點(diǎn)

的線段恰有奇數(shù)條.

證明將〃+2個(gè)點(diǎn)按從小到大的順序記為A，4,…,4,+2,并在每一點(diǎn)賦予數(shù)值《，使

=f1,當(dāng)4為有理數(shù)點(diǎn)時(shí)，

當(dāng)A為無理數(shù)點(diǎn)時(shí).

與此同時(shí)，每條線段44+1也可數(shù)字化為qam（乘法）

當(dāng)&As—為有理數(shù)點(diǎn)，另一為無理數(shù)時(shí)，

叫={1,當(dāng)同為有理數(shù)點(diǎn)或無理數(shù)點(diǎn)時(shí)，

記卬心二-1的線段有攵條，一方面

（%生）（廿3）（WJ…（%+得〃+2）=（T）"（+D…=（-D*

另一方面（―）（。2。3）（。3a4尸?（4+|。”+2）

=4（4%…?！?J%〃+2=44+2=T，

得㈠）人二一1,故左為奇數(shù).

評析用了數(shù)字化、奇偶分析的技巧.

二、約數(shù)與倍數(shù)

最大公約數(shù)與最小公倍數(shù)的求法.

（1）短除法.

（2）分解質(zhì)因數(shù)法.設(shè)

a=Pi"**,P：*,qN0,，=1,2,…，女，

b=p，pj、?p"2i=1，2,.、k.

記/=min{?,力},6=max{?,力},

那么（a,b）=,?,〃J，

［。，句-Q。"P/?

13）輾轉(zhuǎn)相除法

（〃，6）=修"）=（小弓）=一,=（*，/）=（%0）=大

例7(1)求(8381,1015)，[8381,1015]；

(2)(144,180,108),[144J80J08].

解⑴方法1分解質(zhì)因數(shù)法.由

8381=172X29,

1015=5x7x2