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

羅增儒

引言

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

說，數(shù)論是研究正整數(shù)的一個數(shù)學(xué)分支.

什么是正整數(shù)呢？人們借助于“集合”和“后繼”關(guān)系給正整數(shù)（當(dāng)時也即自然數(shù)）作

過本質(zhì)的描述，正整數(shù)1,2,3,…是這樣一個集合N.：

（1）有一個最小的數(shù)1.

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

一個數(shù)的后繼數(shù).

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

（3）對N+的子集若ItM,且當(dāng)。時，有后繼數(shù)則M=

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

類的智慧還沒有成熟到解決它的程度.比如，哥德巴赫猜想：

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

由4開始，都可以表示為兩個素數(shù)和的形式，任何奇數(shù)，由7開始，都可以表示為三個素數(shù)

的和.后者是前者的推論：也可獨立證明（已解決）.”表示為兩個素數(shù)和的形式”就是著名

的哥德巴赫猜想，簡稱1+1.

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

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

1966年陳景潤證得：一個素數(shù)+素數(shù)x素數(shù)（1+2）,至今仍無人超越.

?陳景潤的數(shù)學(xué)教師沈元很重視利用名人、名言、名事去激勵學(xué)生，他曾多次在開講時，

說過這樣的話：“自然科學(xué)的皇后是數(shù)學(xué)，數(shù)學(xué)的皇冠是數(shù)論，哥德巴赫猜想則是皇冠上的

明珠.……”陳景潤就是由此而受到了啟示和激勵，展開了艱苦卓絕的終生奮斗和燦爛輝煌

的奮斗終生，離摘取“皇冠上的明珠”僅一步之遙.

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

明多的技巧，有人說：用以發(fā)現(xiàn)數(shù)學(xué)人才，在初等數(shù)學(xué)中再也沒有比數(shù)論教材更好的課程

了.任何學(xué)生如能把當(dāng)今一本數(shù)論教材中的練習(xí)做出，就應(yīng)當(dāng)受到鼓勵，勸他（她）將來去

從事數(shù)學(xué)方面的工作（U.Dudley《數(shù)論基礎(chǔ)》前言）.下面，是一個有趣的故事.

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

了他一個問題加以考察（1959）：如果你手頭上有〃十1個正整數(shù)，這些正整數(shù)小于或等于2〃，

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

不至IJ12歲的波薩只用了1分半鐘，就給出了問題的解答.他將1?2〃分成（1,2）,（3,

4）,…，（2〃-1,2"）共〃個抽屜，手頭的〃+1個正整數(shù)一定有兩個屬于同一抽屜，這兩

個數(shù)是相鄰的正整數(shù)，必定互素.

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

歲的波薩就發(fā)表了圖論中“波薩定理”.

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

支柱是：代數(shù)，幾何，初等數(shù)論，組合初步（俗稱代數(shù)題、幾何題、算術(shù)題和智力題）.高

中競賽加試四道題正好是四大模塊各一題，分別是幾何題、代數(shù)題、數(shù)論題、組合題，一試

中也會有數(shù)論題.數(shù)論受到數(shù)學(xué)競賽的青睞可能還有一人技術(shù)上的原因，就是它能方便地提

供從小學(xué)到大學(xué)各個層面均、新鮮而有趣的題目.

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

除性，被2、3、4、5、8、9、11等數(shù)整除的判定；素數(shù)和合數(shù)，最大公約數(shù)與最小公倍數(shù);

奇數(shù)和偶數(shù)，奇偶性分析；帶余除法和利用余數(shù)分類；完全平方數(shù)；因數(shù)分解的表示法，約

數(shù)個數(shù)的計算；簡單的一次不定方程.

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

二次剩余，不定方程和方程組，高斯函數(shù)［x］,費馬小定理，格點及其性質(zhì)，無窮遞降法，

歐拉定理"孫子定理

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

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

（2）約數(shù)與倍數(shù)、素數(shù)與合數(shù)；

（3）平方數(shù);

（4）整除;

（5）同余；

（6）不定方程；

（7）數(shù)論函數(shù)、［x］高斯函數(shù)、歐拉函數(shù)：

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

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

的數(shù)論問題作分類講解.

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

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

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

定義1（帶余除法）給定整數(shù)如果有整數(shù)名「（047'＜網(wǎng)）滿足

a=c/b+r,

則9和廠分別稱為。除以）的商和余數(shù).特別的，r=o時，則稱。被人整除，記作耳。，或

者說。是人的倍數(shù)，而人是。的約數(shù).（4/?的存在性由定理1證明）

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

公約數(shù)是能整除其中每一個整數(shù)的最大正整數(shù)，記作（a,%,???,4）?

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

簡單性質(zhì)：（%,%,…q）=（同，同

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

定義3（最小公倍數(shù)）非零整數(shù)卬,華，???，?！钡淖钚」稊?shù)是能被其中每一個

q（1?i?〃）所整除的最小正整數(shù)，記作［6,生，…，4］?

簡單性質(zhì)：如果人是正整數(shù)的公倍數(shù)，則存在正整數(shù)〃z使攵=m［。/］

證明若不然，有々二間旬+〃（0＜”］。,句），由女,［。/］都是〃力的公倍數(shù)得廣

也是〃力的公倍數(shù)，但目，與可的最小性矛盾.故2二〃取河.

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

定義5大于1且除I及其自身外沒有別的正整數(shù)因子的正整數(shù)，稱為素數(shù)（也稱質(zhì)

數(shù)）.其余大于1的正整數(shù)稱為合數(shù)；數(shù)1既不是素數(shù)也不是合數(shù).

定理1若。力是兩個整數(shù)，/?＞（）,則存在兩個實數(shù)/八使a=qb+r（O?rvb）,

并且q/是唯一性.

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

…,—3b.—2b,—b,0,b,2b,3b「,

則〃必在上述序列的某兩項之間，從而存在一個整數(shù)9，使

qb4a＜（q+l）b.

即0<a-qb<b,

取r=a-qb,0</*<Z?,

得a=qb+r,

即存在兩個實數(shù)使a=+，?<〃）.

再證唯一性.假設(shè)不唯一，則同時存在小，弓與1,弓：使

〃=姑+弓（0"<〃），

4=%：+）（044<b），

相減（？一%）〃=芍-4，

\q.-q^b=\r2-r\<b,

0<|^,-^2|<1,

但為整數(shù)，故|0-%|=0，得[=%，從而

注：如果取消當(dāng)/*<0或不保證唯一.

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

證明2只證存在性，用高斯記號，由

有一_[.kr,

記）?="〃[*,故存在qm，r=q-n，o工廠<力使

a=qb+z*（0<r</?）.

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

M={a-bx\xe：Z,a-hx>（）]

這是一個有下界的非空整數(shù)集，其中必有最小的，設(shè)x=q時，有最小值，?（廠之0）

a=qb+r.

再證/〈A,若不然，r>b,記/一5+4，有

a=q〃+r=q〃+(〃+A)=〃(q+l)+q

q=q_/?(q+l)￡M

即M有“比，?更小，這與/■為最小值矛盾.

故存在兩個實數(shù)9",使4=”?+〃(0工廠<〃).

定理2設(shè)。，仇c是三個不全為0的整數(shù)，滿足。=彼+*其中q也為整數(shù)，則

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

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

dIa[d\c=a-bq

任取dA.=>\=>=d￡〃=zlu8,

z,[d\b\d\b

任取d=>ndsAnBqA,

d\c\d\a=bq->t-c

得A=B.

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

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

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

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

^a,b)-\a,b\=ab.

證明因為c力是。力的公倍數(shù)，所以。泊的最小公倍數(shù)也是?！ǖ募s數(shù)，存在4使

ah='[億〃],

[a,b][a,b]

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

bb

故鄉(xiāng)是。的約數(shù).同理“是人的約數(shù)，即q是。,〃的公約數(shù).下面證明，是。力的最大公

約數(shù).若不然，有

"="[凡可＜(a㈤[4句.①

設(shè)=可見攵是。的倍數(shù)，同樣k==b廠',Z是8的倍

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

數(shù)，即2是4力的公倍數(shù)，則存在正整數(shù)，〃使攵=〃?[〃,可，有

念=加[〃/]4〃，句，

得cib=q\a,b\>^a,b)[?,b\

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

ah

-k力)a

注也可以由1?〃?二「討二r一二證y,得與夕<(。⑼矛盾.

q

兩步=q[a,，|M〃=(〃,/?)%可以交換嗎？

定理4。步是兩個不同時為0的整數(shù)，若.+byQ是形如ax+by(x,y是任意整數(shù))

的數(shù)中的最小正數(shù)，則

(1)a%+byQax+by；

(2)%+姐=(“〃).

證明(1)由帶余除法有

cix+by=(ax0+b%)9+〃，0?廠<a%+by0,

得〃%—g))x+人()'—q)'o)v‘/+b'o，

知，?也是形如at+Ay的非負(fù)數(shù)，但外°是形如水+力的數(shù)中的最小正數(shù)，故r=0,

即

ax()+by。\ax+by.

(2)由(1)有

ax。+by。1+d()=ci，

ax{}+by()q?0+b?l=b,

得a%+〃)，。是的公約數(shù).另一方面，。力的每一個公約數(shù)都可以整除州)十b。,所以

a%+hyQ是,a,b的最大公約數(shù)，ar。+by0=.

推論若=則存在整數(shù)使4S+初=1.(很有用)

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

(1)(1,6Z)=1.

(2)+=

(3)(2/7-l,2/?+l)=l.

(4)若〃是一個素數(shù)，。是任意一個整數(shù)，且。不能被p整除，則(〃,p)=l.

證明因為(a,p)|p,所以，素數(shù)p的約數(shù)只有兩種可能：(a,p)=l,(ap)=〃.但

〃不能被p整除，工〃，得(a,〃)=1.

推論若〃是一個素數(shù)，〃是任意一個整數(shù)，則(〃,p)=l或(a,p)=〃.

(5)若(a,〃)=l,則存在整數(shù)s,1,使心+初=1.(定理4推論)

(6)若==1,則(〃,bc)=1.

證明由(〃,〃)=1知存在整數(shù)s",使as+初=1.

有a(cs)+/?cf=c,

得(a,bc)=(a,c)=l.

(7)若=則(a±b,a)=l,(a±b,1)=1,(a土b,而)=1.

證明^a±b,a)=(±b,ci)=(b,a)=\?

(a±-)=(a㈤=1,

由(6)^a±b,ab)=\.

(8)若(48)=1,則(""/')=1,其中以〃為正整數(shù).

證明據(jù)(6),由(〃/)=1可得(a”)=l.

同樣,由(優(yōu)\時=1可得(14)=1.

定理6設(shè)。是大于1的整數(shù)，則。的除1之外的最小的正約數(shù)q必是素數(shù)，且當(dāng)。是

合數(shù)時，q<4a.

證明用反證法，假設(shè)夕不是素數(shù)，則存在正整數(shù)數(shù)4,1<功<q,使力①，但q|a,

故有qI。，這與4是。的除1之外的最小正約數(shù)矛盾，故4是素數(shù).

當(dāng)。是合數(shù)時?，設(shè)〃=。闖，則《也是〃的一個正為數(shù)，由q的最小性得從而

2

q<atq=a,開方得

定理7素數(shù)有無窮多個，2是唯一的偶素數(shù).

證明假設(shè)素數(shù)只有有限多個，記為/不〃2，?-，〃〃，作一個新數(shù)

若〃為素數(shù)，則與素數(shù)只有〃個P“2,…,P”矛盾.

若P為合數(shù),則必有必￡｛四，〃2,…,4｝，使〃,|〃，從而“JI，又與P,>1矛盾.

綜上所述，素數(shù)不能只有有限多個，所以素數(shù)有無窮多個.

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

注：這個證明中，包含著數(shù)學(xué)歸納法的早期因素：若假設(shè)有〃個素數(shù)，便有〃+1個素

數(shù).(構(gòu)造法、反證法)秒

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

(1)\\a>-\\ax當(dāng)。聲0時，a\a,a|0.

(2)若臼a，4Ho，則網(wǎng)工同；若,網(wǎng),則a=0;若出?>0,且〃|凡口弧,

則a=Z?.

證明由麗，"0,有a=bq,得同=例|4之河.

逆反命題成立“若麗，例>同，則〃=0"；

由.4時且2同得同=|小又ab>0,得a=b.

(3)若a+〃=u+d.口c,則41d.

(4)若c|Z?,b\a,則.

證明(定義法)由d。，b\a,有

b=qic,a=q2bt

即c\a.

(5)若，則歷|而.

(6)若c\b,則對任意整數(shù)，幾〃，有和〃。+汕.

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

a=q[c,b=q2cf

得ma+nb=("町+nq?)c,

即+

(7)若(4,〃)=1,且,則〃|c.

證明由(4,〃)=1知存在整數(shù)5",使45+4=1,有

a(cs)+(Oc)f=C,

因為"a,a\bc,所以。整除等式的左邊，進(jìn)而整除等式的右邊，即。卜.

注意不能由。匠且力得出水.如6|4x9,但6|4且619.

(8)若且〃卜,qC,則，而卜.

證明由(〃,/?)=1知存在整數(shù)S",使4S+為=1,有

acs+bct=c,

又由4卜,〃卜有c=aqx,c=bq2代入得

ab(%s)+ab(qj)=c,

所以(活卜.

注意不能由4。且匕上得出出?|c.如不能由03()且10|30得出60|30.

(9)若〃為素數(shù)，]：.〃匠，則或a|c.

證明若不然，則a|'〃且a【c,由〃為素數(shù)得(4為)=l,(a,c)=l,由互素的性質(zhì)(6)

得(凡歷)=1,再由。為素數(shù)得。[力c,與。匠矛盾.

注意沒有a為素數(shù)，不能由4以推出a性或a|c.如6|4x9,但6]4且6/9.

定義6對于整數(shù)c,HcwO,若-〃)，則稱出人關(guān)于模c同余，記作

a=Z2(modc)；若<?/(〃-/?),則稱a,〃關(guān)于模c不同余，記作。壬/mode).

定理9(同余的性質(zhì))設(shè)a,m為整數(shù)，m>0,

(1)若a三伙modm)且〃三c(modm)，則a=c(modni)：

證明由。三力(modtn)且/?三(?(modm),有

a—b=mq、,b—c=mq?,

a-c=m(c[x+%)，

得。三c(modm).

(2)若。三b(mod加)且c="(modni)，則a+c=b+J(modm)且ac=bd(modni).

證明由。三Z?(mod/zz)且c三J(mod/n),有

a-b=mq、,c-d="?%,①

對①直接相加，有

(a+c)—(〃+4)=相(功+%)，

得a+c=Z?+J(modin).

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

ac—bd=(ac-be)-(bc-bd)=m(cq、+bq),

得ac=M(modtn).

(3)若a三伏mod〃?)，則對任意的正整數(shù)〃有a"=(modm)Ii,an=加(modtnn).

若。三"且對非零整數(shù)〃有則

(4)mod，”)，9=2什

kk

證明由。三/?(mod機)、，有

a=b+mq,

又用(。/,加)，有色、2,竺均為整數(shù)，且

kkk

—=—+—q,

kkk

“，ab（

得一三一mod—.

kk[k）

定理10設(shè)。,b為整數(shù)，〃為正整數(shù)，

（1）若。工人則（〃一〃"優(yōu)—夕）.

aH-bn=[a-與（"i+cT2b+a^b1+…+abn-2+上）.

（2）若aw—〃，則（4+與心產(chǎn)1+/，1）.

a2n-\+/?2?-1=（?+0）,2"-2一〃2〃-3〃+j”2----加戶-2）

（3）若QW—0,則（。+/川（。2〃一從〃）

a2n-b2n=（4+3（/小_/〃一2〃+/〃_3從_...+4戶-2_6,1）

定義7設(shè)〃為正整數(shù)，攵為大于2的正整數(shù)，q,生，…M,”是小于2的非負(fù)整數(shù)，且

4>0.若

H2

n=a/'""+a2k'~+…+am_xk+am,

則稱數(shù)4%…分為〃的A進(jìn)制表示.

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

,,r-1w-2

n=ax\04-a210+???+am_x104-am,0<^.<9,^>0（10進(jìn)制）

M,_|m2進(jìn)制）

n=a,I2/+a.2-+.f'l?~?I+a,nf,ft2+am.I0<a.I<l,a>0（2

定理12（算術(shù)基本定理）每個大于1的正整數(shù)都可分解為素數(shù)的乘積，而且不計因

數(shù)的順序時，這種表示是唯一的

〃=〃：〃2%…〃產(chǎn)，

其中Pl<〃2<???</〃為索數(shù)，%,%，…，%為正整數(shù).（分解唯一性）

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

〃=〃1〃2…〃…①

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

當(dāng)正整數(shù)〃為合數(shù)時，〃的正約數(shù)中必有一個最小的，記為Q，則P1為素數(shù)，有

n=PM,\<a[<n.

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

n=PM=口p2a2,\<a2<aA<n.

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

過有限次后，比如切次，〃就變?yōu)樗財?shù)的乘積

w=p,p2...pm.

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

〃二彷％…％，②

則有Pl〃2…憶〃，％…%。③

因為等式的右邊能被名整除，所以左邊也能被修整除，于是名整除P1,/4,???,%中的

某一個8,但為素數(shù)，所以心與％相等，不妨設(shè)死為四,有

d=q「

把等式③兩邊約去Pi=i,得

P2-3…外

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

這時，如果另一邊的因數(shù)沒有約完，比如右邊沒有被約完（〃2<，），則有

1=-④

但夕…心+2,…，。均為素數(shù)，素數(shù)都大于1，有心+臼厘…0>1，這表明等式④不

可能成立，兩個分解式的因數(shù)必然被同時約完，即分解式是唯一的.

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

其中P\<Pl<,<P*為素數(shù)，%,%，…，%為正整數(shù).

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

〃=P\P?…Pm，Pl<????〃〃「

（1）當(dāng)〃=2,因為2為索數(shù)，命題成立.

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

這時，若〃為素數(shù)，命題成立；若〃不為素數(shù)，必存在。/，使

由歸納假設(shè)，小于〃的。功可分解為素數(shù)的乘積

a=p；p；…p；，p；wp；w,Yp；，

b=〃川p.…p\'/4iq〃+2工…工

得〃=p；H…忒4+0+2…/，

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

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

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

n=p,p2...p?J,p,<p2

得P|〃2…億”=1%…功?

有Pi0%…0且1IP〃2…億〃，

這就存在％,Pj,使

Pil一且如巴，

但Pi，/，l，Pj均為為素數(shù),所以

Pi=%，%=〃〃

又Pi=%之名=PjNPi，

所以〃[=4.

把等式兩邊約去Pi=1,得

P2P3……

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

這時，如果另一邊的因數(shù)沒有約完，比如右邊沒有被約完（〃zvr）,則有

1-“m+10”+2…

但％)，％+2,…，%均為素數(shù)，素數(shù)都大于1，有金+1冊+2…0>1，這表明上述等式

不可能成立，兩個分解式的因數(shù)必然被同時約完，即分解式是唯一的.

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

〃=P/'〃2”…"J”?

其中P\<Pl<,,<Pjfc為素數(shù)，a],%，。、%為正整數(shù).

定理13若正整數(shù)〃的素數(shù)分解式為〃則〃的正約數(shù)的個數(shù)為

"5)=(4+1)3+1)???(4+1)，

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

S⑺…^1.

2一1p2-\/%-1

證明對于正整數(shù)〃二〃，它的任意一個正約數(shù)可以表示為

m=p，'p；，…])心,0<<a,,①

由于四有0』,2,-一，4.共/+1種取值，據(jù)乘法原理得〃的約數(shù)的個數(shù)為

"(〃)=(q+1)3+1)???(%+1)?

考慮乘積

(P1°+〃]'+???+)(〃2°+P1+…+),?,(Pk+Pk+…+p/")，

展開式的每一項都是〃的某一個約數(shù)(參見①)，反之，〃的每一個約數(shù)都是展開式

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

S(〃)=(P\]+P：+…+p1?(〃/+Pk+…+Pk，)

p/2+,-lP『H_]

=-----------------?????--------,

P「1P2TPk7

注構(gòu)造法.

定義8(高斯函數(shù))時任意實數(shù)X,[可是不超過A：的最大整數(shù).亦稱[目為犬的整數(shù)

部分，+

定理14在正整數(shù)出的素因子分解式中，素數(shù)/"勺為因子出現(xiàn)的次數(shù)是

nnn

一十+F+….

LPJLPJ」

證明由于〃為素數(shù)，故在川中〃的次方數(shù)是1,2,…，〃各數(shù)中〃的次方數(shù)的總和（注

意，若〃不為素數(shù)，這句話不成立）.

在1,2,…,〃中，有巴個〃的倍數(shù)；在-個〃的倍數(shù)的因式中，有4個/的

LP」L/dL/rJ

倍數(shù)；在A個p?的倍數(shù)的因式中，有A個夕?的倍數(shù)；…，如此下去，在正整數(shù)〃!

I，」L，」

的素因子分解式中，素數(shù)〃作為因子出現(xiàn)的次數(shù)就為

注省略號其實是有限項之和.

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

50!=203%5%7%1產(chǎn)13%17勺9%23%29?31?37?41?4347

定理15（費瑪小定理）如果素數(shù)〃不能整除整數(shù)。，則〃|（。『-|一1）.

證明1考察下面的個等式:

a=pq}+f],0</;</7,

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

由于素數(shù)〃不能整除整數(shù)。，所以，〃不能整除每個等式的左邊，得大弓，…均不

為0,只能取1,2,…，〃-1.下面證明小公…力一各不相等.

若不然，存在，,<sW〃-1,使

sa=pq、+4，

ta=pql+rl,

【小

相減（s—f）a=p（4—0）.

應(yīng)有素數(shù)〃整除（$-/）。，但素數(shù)〃不能整除。，所以素數(shù)〃整除卜一。，然而由

1<r<5<〃-1可得

0<s-t<p-2<p,

要素數(shù)〃整除(s—。是不可能的，得不馬,各不相等.有

，唱…小T?2?TP-1)=(P-1)!?

再把上述〃-1個等式相乘，有

(〃一1)"1=珈+7內(nèi)…小，

即(〃_1)力上|=帥+(〃_1)!,

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

亦即(p_l)!(〃i_l)=坳.

由于〃是素數(shù)，不能整除(〃—1)!,所以素數(shù)〃整除得證

證明2改證等價命題：如果素數(shù)〃不能整除整數(shù)。，則?！ㄈ?mod

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

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

(2)假設(shè)命題對?！?1)成立，則當(dāng)。=%+1時，由于

p|￡，G=l,2,…,〃一1),故有

gi)〃=叱++…+c；%+]

=+1=X：+1(mod/?).(用了歸納假設(shè))

這表明，命題對a=k+l是成立.

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

又素數(shù)〃不能整除整數(shù)a,有(a,p)=l,得司(4-1).

定義9(歐拉函數(shù))用表示不大于〃且與〃豆素的正整數(shù)個數(shù).

定理16設(shè)正整數(shù)〃=〃Jp2a2...p*,則

/xJ1丫11[,1]

(P\n)=n1-----1----------???1--------.

I月人Pi)IPkJ

證明用容斥原理.設(shè)5={1,2,???,〃},記4為S中能被整除的數(shù)所組成的集合

（i=l,2..?,〃），用|4|表示從中元素的個數(shù)，有

n

IAI=—?|AnA；|=，…,IAnA2n…nA|=------

PiPiPjPlPz…Pk

易知，S={1,2,…/}中與〃互素的正整數(shù)個數(shù)為

|AHAn一聞.

由容斥原理得

-n4n??國=葉z⑷+Z.聞

~Z|巾AnAJ+-.+（-I）［Ar）A2n…n4|

ii〃/\kn

=n-y—+>------>--------------+???+（-1t）---------------

必必Pi田<網(wǎng)P,PjPjPjPmA/A…Pk

=〃QLZ—--Z—…+（-以一［—

\<i^xPi\<,i<j<.kPjPjPjPjPniP\P1'"Pk

11Yi1111

IPi八Pi）IPk）

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

推論對素數(shù)〃有0（〃）二〃一1,0（〃"）=〃"一〃。一.

定理17整系數(shù)不定方程方+〃y=c（，心。0）存在整數(shù)解的充分必要條件是

（。/）卜.

證明記4=（〃,〃）.

（1）必要性（方程有解必須滿足的條件）.若方程存在整數(shù)解，記為=則

卜=為,

or0+by0=c,

由WIox0+by0,得證(a,A)|c.

（2）充分性（條件能使方程有解）.若d|c,可設(shè)c=止由于形如ax+b，的數(shù)中有

最小正數(shù)ax0+by0滿足

陰）+如=m〃）.

兩邊乘以e,得

々（氣）+6?，°）=。

這表明方程有解4x=ex°n,

卜二/

定理18若乃工0,（々/）=1,且產(chǎn)="'是整系數(shù)不定方程ox+b），=c的一個整數(shù)

）=%，

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

x=x飛Q-bt.（.reZ.）.①

[y=y0+at9

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

由（毛,%）是方程的一個解，有

町）+by（）=c，

又方程的任意一個解（乂），）滿足

ax+by=c,②

相減a（x-Xo）+O（y-）b）=O.③

但（。力）=1,故有

a|（y-%），

有三=0L=?z

-ba

得方程的任意?個整數(shù)解可以表示為

[』。一"（口.

尸兄+勿,

定義10（平面整點）在平面直角坐標(biāo)系上，縱橫坐標(biāo)都是整數(shù)的點稱為整點（也稱格

點）.類似地可以定義空間整點.

第二講數(shù)論題的范例講解

主要講幾個重要類型：奇數(shù)與偶數(shù)，約數(shù)與倍數(shù)（素數(shù)與合數(shù)），平方數(shù)，整除，同余,

不定方程，數(shù)論函數(shù)等.重點是通過典型范例來分析解題思路、提煉解題方法和鞏固基本內(nèi)

容.

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

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

奇數(shù).偶數(shù)可以表示為2”,奇數(shù)可以表示為2〃-1或2〃+1.一般地，整數(shù)被正整數(shù)，〃去

除，按照余數(shù)可以分為〃?類，稱為模機的剩余類G={M，E三i（mod〃z）},從每類中各取出

一個元素qwG，可得模〃？的完全剩余系（剩余類派出的一個代表團(tuán)），（）,1,2,…,〃2-1稱

為?！▃的非負(fù)最小完全剩余系.

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

分類、染色、數(shù)字化都有我系，在數(shù)學(xué)競賽中有廣泛的應(yīng)用.

關(guān)于奇數(shù)和偶數(shù)，有下面的簡單性質(zhì)：

（1）奇數(shù)二偶數(shù).

（2）偶數(shù)的個位上是（）、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ù).

（8）兩數(shù)和與兩數(shù)差有相同的奇偶性，〃+〃三a—h（mod2）.

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

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

（11）（-1?=1的充分必要條件是々為偶數(shù)，（-1）人=-1的充分必要條件是攵為

奇數(shù).

（12）（2/?）2=0（mod4）,（2H-l）2三1（mod4）,（2〃-三1（mod8）.

（13）仟何整數(shù)都可以表示為〃=2'"（2々-1）.

例1（1906,匈牙利）假設(shè)％,生，…，%是L2,…，〃的某種排列，證明：如果〃是奇

數(shù)，則乘積

是偶數(shù).

解法1（反證法）假設(shè)（6-1）（々—2）.-（4—冷為奇數(shù)，則?均為奇數(shù)，奇

數(shù)個奇數(shù)的和還是奇數(shù)

奇數(shù)=（4-1）+（?2-z?）

=（4+4?4~?！保?+2+???+〃）=0，

這與“奇數(shù)工偶數(shù)”矛盾.所以（4一1）（%-2）???（%一.是偶數(shù).

評析這個解法說明（4-1）（%-2）…（4-〃）不為偶數(shù)是不行的，但沒有指出為偶數(shù)

的真正原因.體現(xiàn)了整體處理的優(yōu)點，但掩蓋了“乘枳”為偶數(shù)的實質(zhì).

解法2（反證法）假設(shè)（4一1）（%-2）…（4一〃）為奇數(shù)，則q-i均為奇數(shù)，出與

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

盾.所以（q-1）（生一2）…（。"一〃）是偶數(shù).

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

為什么“〃為奇數(shù)”時“乘積”就為偶數(shù)呢?

解法31,2「.,小4，。2，3，/中有〃+1個奇數(shù)，放到〃個括號，必有兩個奇數(shù)在同一

個括號，這兩個奇數(shù)的差為偶數(shù),得（q-1）（生-2）…（4-〃）為偶數(shù).

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

1,2,.一,〃中奇數(shù)與偶數(shù)個數(shù)不等，奇數(shù)多，某個括號必是兩個奇數(shù)的差，為偶數(shù)”.

類似題：

例1T（1986,英國）設(shè)4,生，…,。7是整數(shù)，4，打,…，力7是它們的一個排列，證明

（q-々）（以一占2）…（％-4）是偶數(shù)?

（4，生，…，/中奇數(shù)與偶數(shù)個數(shù)不等）

例I1-2萬的前24位數(shù)字為4=3.14159265358979323846264,t己4，〃2，一、〃24為

該24個數(shù)字的任一排列，求證（4一〃2）（〃3一%）…（%一々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ù)個數(shù)不等）

例2能否從1,2,…,15中選出1（）個數(shù)填入圖的圓圈中，使得每兩個有線相連的圈中的

數(shù)相減（大數(shù)減小數(shù)），所得的14個差恰好為1,2,???,14?

解考慮14個差的和S,一方面

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

另一方面，每兩個數(shù)的差與其和有相同的奇偶性,一。三〃十伙mod2）,因此，

14個差的和S的奇偶性與14個相應(yīng)數(shù)之和的和S'的奇偶性相同，由于圖中的每一個數(shù)。與

2個或4個圈中的數(shù)相加，對S”的貢獻(xiàn)為2?；?。，從而S'為偶數(shù)，這與S為奇數(shù)矛盾，

所以不能按要求給圖中的圓圈填數(shù).

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

時，則按兩種不同方式所求得的總和應(yīng)是相等的，這叫計算兩次原理成富比尼原理.計算兩

次可以建立左右兩邊關(guān)系不太明顯的恒等式.在反證法中，計算兩次又可用來構(gòu)成矛盾.

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

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

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

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

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

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

例4有〃個數(shù)不電，…，為”，乙，它們中的每一個要么是1，要么是一1.若

x1x2+x2x3+???+???++xnx1=0,求證41〃.

證明由七{{1,一1},有七大+［,再由

—+%2.+??.+???+/-/“+乙斗=0,

知〃個x/2［中有一半是1,有一半是一1,〃必為偶數(shù)，設(shè)〃=22.

現(xiàn)把〃個1丙+［相乘，有

22

（-1/（+1/=^2.x2x3...=x,\.....xn,,\=1,

可見，左為偶數(shù)，設(shè)k=?n,有〃=4機，得證4|〃.

例5〃個整數(shù)q.生，…，Mt。,，其積為〃，其和為0，試訐4|〃.

證明先證〃為偶數(shù)，若不然，由4d…〃“一心”=〃知，q,凡,全為奇數(shù)，

其和必為奇數(shù)，與其和為0（偶數(shù)），故〃必為偶數(shù).（4，。2，一?，見7，。〃中至少有1個偶數(shù)）

再證〃為4的倍數(shù)，若不然，由〃為偶數(shù)知，I，/恰有一個為偶數(shù)，其余

〃-1個數(shù)全為奇數(shù)，奇數(shù)個奇數(shù)之和必為奇數(shù)，加上一個偶數(shù)，總和為奇數(shù)，與

%,%，…，勺-1，%之和為0矛盾，所以，"為4的倍數(shù)，4|”.（卬4,…,〃中至少有

2個偶數(shù)）

評析要證4|%只須證q,外,…,4”,4中至少有2個偶數(shù)，分兩步，第一步證至少

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

例6在數(shù)軸上給定兩點1和J5,在區(qū)間（1,&）內(nèi)任取〃個點，在此〃+2個點中，

每相鄰兩點連一線段，可得〃+1條互不重疊的線段，證明在此〃+1條線段中，以一個有理

點和一個無理點為端點的線段恰有奇數(shù)條.

證明將〃+2個點按從小到大的順序記為\為,….A,會，并在每一點賦予數(shù)值處，

使

_f1,當(dāng)4為有理數(shù)點時，

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

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

=f-l,當(dāng)4,AM一為有理數(shù)點，另一為無理數(shù)時，

卬*=11,當(dāng)同為有理數(shù)點或無理數(shù)點時，

記卬如=-1的線段有k條，一方面

（乎2）（華3）一6）…（4+同“+2）=（7）"（+1）…=（-1/

另一方面（4%）（出％）（4。4>,?（%+14+2）

=4（出生…〃=勾耳+2=-1，

得（_琰=_1,故■為奇數(shù).

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

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

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

（1）短除法.

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

a=/廠￡…〃產(chǎn),%>0,i=1,2,…/,

b=P]-p2—??,P?，"N0，i=L2,???,h

記%=min{q,4},6=max{4,4},

則[a,b）=p；'pm上,

（3）輾轉(zhuǎn)相除法

(〃，))=(4「)=6,弓)=???=(小，4)=(力°)=%

例7(1)求(8381,1015),[8381,1015]：

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

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

8381=172x29,

1015=5x7x29,

得(8381,1015)=29,

[8381,1015]=5X7X172X29=293335.

方法2輾轉(zhuǎn)相除法.

8838110153

8120783

12612328