基礎數(shù)論講義

第一章整除性理論

一、整除的基本性質

-I和I同時成立的充要條件是，對任意的，e,有I+。

-I和I同時成立的充要條件是I1=1I

二設I.若貝UIIW||。不等于的整數(shù)只能有有限個除數(shù)；

、設+。那么，I的充要條件是I。一般地，對正整數(shù)，.

I的充要條件是I。

二、帶余除法

帶余數(shù)除法的基本形式）對任給的整數(shù)W和，一定存在唯一的一對整數(shù)和，滿足=+,W

<11。0

上式中的稱為是被除所得的部分商，稱為是被除所得的最小非負余數(shù)。此外，被整除的

充要條件是。

證先證唯一性。假設還有一對整數(shù)'和'滿足式（），即='+',<'<II。這

樣就有+='+\不妨設W'。若'，則有'，所以結論成立。若可得<'一=（一'）。

因而IIW'另一方面，<--<II。矛盾。所以，必有'，'。下面證存在性。若被整

除，即存在整數(shù)使得=,則可取…若不被整除，考慮集合{—：e}?顯見，不屬于，以及集

合中必有正整數(shù)（為什么）。由最小正整數(shù)原理知，在集合中必有最小的正整數(shù)，設為一出。必

有VVII。若不然，則有IIW。因不被整除，所以II〈（為什么）。因此<一II-oa-II

〈是屬于的正整數(shù)，這和是中的最小的正整數(shù)矛盾。這樣，取，，就得到式（）。最后，由式（）

知，被整除的充要條件是被整除。由此及WVII,就推出被整除的充要條件是。證畢。

三、最大公約數(shù)和最小公倍數(shù)

性質（），，…，的最大公約數(shù)與這些數(shù)的次序無關，即若，，…，是，，…，的一個重新

排列，貝工，…，）（，，?一，）。

（）任意改變,，…，的正負號，它們的最大公約數(shù)不變。事實上，總有

（，，…，）（II，II,II）?

（）若-I>則（，，…，）（,,…，-）。

（）對任意整數(shù)有，（，）=（,+）。一般的有，

（>1>）（>+'…'）°

（）設正整數(shù)1（,,…，）,則有（,，…，）（,，一,）?特別的，

（（,）,（,））=,及（,，…，），其中（,，…，）。

、裴屬定理

存在整數(shù)使得m+w?=（a,加

四、素數(shù)與唯一分解

、素數(shù)有無限多個。

、標準分解式：每個大于的正整數(shù)〃都可以唯一的表成n=P?P;…

的形狀，其中Pi<〃2<<P,是素數(shù)，而四,火，…，氏是正整數(shù)，這叫做〃的素因子標準

分解式。

11

例題設自然數(shù)滿足，^-=1--+-------1----,-證明2003|〃。

q2313341335

證明￡=11111

—+-----------1----------

q2313341335

“1111、￡11、

(1+—+-+++)2(+++)

2313341335241334

“1111、八11、

(1+—+-+++)(1+++)

23133413352667

1111

++

66866913341335

(----1-----)+(-----1-----)+(H----------)

66813356691334w1002

200320032003

H---------------------于是可得

668x1335669x13341001x1002

1

]335!p=2003qt,t=1335!(----------++)為整數(shù)，從而有

668x13351001x1002

20031335!〃,而(，！)，所以2003|0。

例題求所有的正整數(shù)、，滿足“5+4=7"-1.

解原方程等價于("-n+1)(/+?+1)=7?.

顯然，”X1.

當"22時，n3-"+1=(〃-l)(n2+n)+1>1,+n+1>1.

設〃3-〃+1=7",4+〃+I=7”,其中a,be乂.于是,

(n-1)(7〃-1)=(〃-1)(/+葭)=7"-1.

因此，(7〃-1)|(7"-1),即(7"-1,7"-1)=7"-1.

又因為(7"-1,7"-1)=7"-1,得到b=(a,b),BPa=kb{keN+).

A

則〃3-n+1=7"=7砂=(I+〃+1).

2

當％=1時，有“3-n+\=n+n+l,n-2.

當AN2時，有

(〃3-〃+1)-(“2+〃+1)*<(“3-〃+1)一(“2+〃+])2=-“4__"3_3"-3〃<0,

矛盾.綜上所述，”=2,加=2是原方程的唯一一組解.

評注在解決與多項式有關的數(shù)論問題時，代數(shù)變形(如因式分解，配方)非常重要。

引題設a>1,加,鹿均是正整數(shù)，試證(am-l,a"-l)=a(m'n)-l.

證明用帶余除法，當時，結論顯然成立，設〃?〉〃且機=飲2+r,0?尸<〃，則有

a"'-l=(優(yōu)—l)@""+a"2"++a*巧+a「_

于是,(。"'一1,4-1)=(優(yōu)一1,優(yōu)一1).如果，則有

3"—1,優(yōu)—1)=(優(yōu)一1"-1)=-1,0)=a"—1=即結論成立。

若不為零，不妨設

n-qxr+<r,r-q2r}+r2,0<r2<r},,

〃-2=%〃T+〃，于是有(m,〃)=(〃")=〃，所以

(a"-"-l)=(a'--1)==a"-l=?(,nn)-l.

例題試確定使+人+7整除a2h+a+b的全部正整數(shù)對(a,b).

解：b(a2b+a+b)-a(ab2+b+7)=b2-7a.ab2+b+7^b2-7a)

()若從一7a>0則有：。62+。+7〈從—7a<〃.矛盾；

()若從一7。<。則a/+。+7<7。一人2<7〃，82<7).?.b=l或匕=2.

當6=1時，題設成為a+8整除7a—1,有7a—l=7(a+8)—57得a+8|57=3x29,

.,.a=21或。=49

當6=2時，4a+9|4-7a由于0<7。-4<2(4a+9)知：4a+9=7a—4無整數(shù)解；

()若尸—7a=0則人=7Z,a=7A2其中％eZ+此時/人+。+人除以?！?入+7商

恰為，題設條件滿足。

綜上：所有滿足條件的正整數(shù)對為(。力)=(21,1),(49,1)(742,7。(&eN+)

類題求所有正整數(shù)滿足加2—〃整除機+〃2,并且〃2—相整除“+/〃2.

分析由對稱性，我們不妨設〃2加，并估計的大體范圍。

解不妨設〃2m則(機+11-機=(m+1)+m2顯然〃2〃.對于

“>m+1成立。因此，〃>加+1時，滿足條件的整數(shù)不存在，我們只要考慮〃=加與

n=m+\.

假設〃=〃2,則〃之一九整除+〃。若〃>3則〃2>3〃=>2（〃？一〃）>/+〃顯然

22

n—n<n+no所以九>3,一〃不整除〃？「.〃=？與〃=3且易知成立。

假設〃=/%+1.我們求)篦2-勿2-1整除〃/+3/72+1.的.若77126,貝IJ

m(m-5)>3=>2(/n2-zn-1)>m2+3，〃+l.又m2-m—l<m2+3m+1.所以

m2-m-\不整除m2+3〃z+1.則對于根=1,2,3,4,5逐一驗證得：m=1或機=2.

綜上所述,解為(m,n)=(2,2),(3,3),解2),(2,1),(3,2),(2,3).

ap

例題若。。1,3/)=1,〃為奇素數(shù),證明(。+b,a十")=1,或者〃。

a+b

ap+bpap^bp

證明設3+"---------)=dna+b=kd,---------=Id,(k,1)=1

a+ba+b

屋+〃=ld(a+b)=kld2,另外

Q〃+bp=ap+(kd—d)p=ap+(kd)l)-C；(以尸々++c^kd(-a)p-}+(-a)p

所以，ld={kdyx-C\{kdy-2a++C廣(-口尸

于是，d\C^(-a)p-[=>d\pap-[

如果(d,a)=4=41(Q+/?)=dj(a,a+b),

而(a,a+0)=(a,b)=1=>&=1=>(d,a)=1

從而由Mpa"i=d|p=d=1,或4=p

例題設,，是正整數(shù)，且cgcd—c+l),(/+1)|(〃+。)證明：，中有一個數(shù)等于，另

一個數(shù)等于Y—c+l。

證明：.,?設=氏(/+1),keN.

則a=k(c2+\}-bH%(02+1)-Z?]|C(C2-C+1)

Z?[/:(c2+1)-/?]|c(k@-kc+k+b-b)k(c2+1)-Z?|c(一kc+b)

al^c(c2-c+1)，若均大于。

則。+/?<。+(o2-C+1)=C2+1與。2+1。+人矛盾。

???不妨設J???c(-kc+b)<0等號成立當且僅當k=1且方=c

若等號不成立，則C(一比+切4一根(，2+1)-回

*,?—k/+be4—kd—k+bhe<b—k矛盾°

/.一定有c(—kc+b)=0.從而攵=1且。=c

?*.u-k(c~+1)—/?=c~—c+1二命題成立。

類題設為正整數(shù)，且I(4〃)求證(年試題)

證明：(4a*—1jb~=(Aa~b—b]=a(4ab—11+a—61

=a2(4a6—1j"+2a(a—6j(4a6—1)+(a—6j

4ab—1S-l)=4就_]忻(4/_1)204就-1(0-域.

{^b2,4ab—1]

反設有正整數(shù)a工b滿足4ab-1(a—bf,則必有一組這樣的(a,b)使a+b最小.

令(a—=k^4ab—1).不妨設a>b.

貝“Q—6)2=乂4ab—1)即a2-(4A+2)ba+l)2+k=0.

二次方程/一(4及+2M+b~+k=0的一個根為%=a,

另一根弓=(4*+2)b-a=^也是正整數(shù).故(4?)也滿足條件.

由所設a+b最小得到022a(〉b),即k>a2-b2.

a

于是(a—b)=k(4ab-1)2(Q?-b~)(4a6—1j.

HPa—b>(a+6)(4a6—1).矛盾.

例題.設。力,esZ使得a+力+c|/+〃+c2,證明：存在無窮多個正整數(shù)，使得

a+h+c\an+hn+cn

證明設c'“=Snt(m￡N+).可知數(shù)列S,“滿足遞推公式

S〃+3=(a+入+c)S,〃+2-(ab+bc+ca)Sm+}+abcSm?(牛頓幕和公式)①

由于a+匕+cla:+/+，，(a+/?+c)2=(a24-/?2+c2)4-2(ab+be+cd),可以得到

a+h+c\2(ab+he+cd).②

下面證明：若4+/?+c|S,“，則。+8+C|S,H+3.

()a+b+c為奇數(shù)，由②得〃+〃+c|aZ?+bc+ca.又因為a+/?+c|S,〃，所以

a+b+c\[(a+b+c)Sm+2-(ab+he+cd)S,n^+abcSm]，

即4+/2+C|S,〃+3.

()a+b+c為偶數(shù),因為和"向，和".，和c*奇偶性相同，所以a+8+c和

"Z+"""+/向奇偶性相同，S"也是偶數(shù)，結合②,^a+b+c\(ab+bc+ca)Sm+],又因為

〃+6+c|S,〃，所以

a+Z?+c|[(〃+/?+c)Sm+2-(ab+8c+ca)Sm+}-cibcSm],

即a+"c|Sm+3.

因為S1能被a+A+c整除，所以S,H,So也能被a+A+c整除，符合要求的有無窮多個.

例題已知24|力+1,證明24b(九)。

解顯然，n=-\(mo故不是完全平方數(shù)，從而?eZ,若

力〃，且d<〃=4>〃，這就表明和是兩個不等的因子，從而的因數(shù)是兩兩相對的，故有

d

偶數(shù)個。

A?Y]d?-I-n

設只需要證明d|(d+—),注意到(，)，d+—=------,所以只需要證明

ddd

24|(6/2+n)=J2-l+(/?+l)<^24|j2-lo因為為奇數(shù)，設，則

儲_1=4k*+1)=8|/_1,又(24,d)=1=>3不整除d=儲三1(mod3)

所以3M2—1.又(，)，從而24|屋—1.這樣的每一對因子都被整除，結論成立。

例題設〃是一個合數(shù).證明存在正整數(shù)“2,滿足機|〃，且"(〃)4〃3(⑼.這里

d(k)表示正整數(shù)k的正約數(shù)的個數(shù).

證明若〃有一個素因子p滿足令加=4,則有"2<?.由P>4知

(m,p)=l,因此d(〃)=d(p)d(/”A2d(歷.又由〃是合數(shù)知相>1,即d(/〃)N2.因此

d(n)<ct(m).

現(xiàn)在設〃的所有素因子都不大于血，取明為〃的不超過冊的最大因子，再取加，為△的

不超過〃的最大因子.我們先證明加2〉1?

若不然，則2沒有大于且不超過6的因子，但若2是合數(shù)，則它在區(qū)間內(nèi)至

町m]叫

少有一個因子，矛盾！因此乙是素數(shù).但前面已假設〃的所有素因子都不大于〃，又

->-^=7^.故只有2=占且是素數(shù).但此時有膽=6,與假設的血=1矛盾！

網(wǎng)yjnm}

由網(wǎng)>1知m]m2>m,,且叫/巧是〃的因子.由，叫的選取可知in[n^>4n,因此令

砥二n,則有/二=1,2,3).

'm{m2

因此，d{ri)=4(根附2加3)<d(叫)d(加2)d(63)<max{/(g),/(/%),/(砥)}

故取叫，加2,g中因子數(shù)最多的一個為機即可.

注以上用到一個基本的事實：若〃,為正整數(shù)，則d(〃u)Wd(")d(u),這可用數(shù)d(x)的計

算公式推出來.

例題設為一個正整數(shù)，為一個質數(shù)，證明，如果滿足

an-Vph=bn+pc=cn+pa,則。=6=c。

證明若有兩個相等，則。=Z?=c。若互不相等，則

a〃一b〃=一p(b-c),b"-c"=一p(c-a),c〃一a〃=一p(a-b),故

若〃為奇數(shù)，則。"-Z?"與。-胴號，y-。"與1)-洞號,c"-a"與c-〃同號，

于是，(1)式的左邊是正的，而右邊是負的，因此n一定為偶數(shù)。

設d是a-b,b-c,c-a的最大公因數(shù)，且設

a-b=du,b-c=dv,c-a=dw,(u,v,w)=l,u+v+w=O

由an-bn=-p(b-c)=(〃一b)\p(b-c)=>w|/?v,同理葉pw,w\pu.

由(u,v,w)=l,u+v+w=O=>u,v,w中最多一個被p整除。

若p不整除u,v,w中任意一個，則Ww,w\u=>|w|=|v|=|wj=l,

這與u+v+w=O矛盾。從而，p恰好整除u,v,w中一個。不妨設p|〃.〃=p〃]

和前面類似，可得=>M=M=W=i。

由p4+u+w=O,則p一定是偶數(shù)，即p=2,因此v+w=-2U]=±2=u=卬(±1)

u=-2v=>a-b=-2(Jb-c),設〃=2左，由an-bn=-p(b-c)得

Cak—bk)(ak+//)=—2(。-C)=Q—由。一闿/一//=>ak+//=±1,因此中

恰有一項是奇數(shù)，這與a-h=-2S-c)是偶數(shù)矛盾。

二章數(shù)論函數(shù)

一、高斯函數(shù)

、[x]<x<[x]4-1,

、若

、若為整數(shù)，[〃+幻=〃+[幻

、[x]+[y]<[x+j]<[x]+[j]+l

、若丁之0,y20=[孫]2[幻]川

、若為整數(shù)，[四]=[土]

nn

x

、若為實數(shù)，為正整數(shù)，則在不超過的正整數(shù)中，的倍數(shù)共有[―]

n

、設p是素數(shù)，如果則0("!)=[2]+[二]+...+[=]

PP-P

恒等式[zw]=[x]+[x+L]+[x+±]+…+[x+巴*■]

nnn

二、歐拉函數(shù)

、若為素數(shù)，則夕5)=2-1,夕(/)=//7(2-1),若為合數(shù)，則0(〃)《〃一2,

、不超過且與互質的所有正整數(shù)的和為則:〃0(〃)：

、若(a,。)=1=><p(ab)=夕(a)°S),

、〃=P「P片---)(1--)(1--),

PiPiPk

、設為的正約數(shù)，則不大于且與有最大公因數(shù)的正整數(shù)個數(shù)為雙方)，同時

￡p(d)=￡(pA

d\n口八4

、若很=夕(〃)限(。)

三、積性函數(shù)

設為一個正整數(shù)，分別用

T(〃),S(〃),P(〃)表示〃的所有約數(shù)個數(shù),所有正約數(shù)的和,所有正約數(shù)乘積.

T(")="(?,+1)；S(〃)="(〃);P(n)=〃2

/=]/=1Pi—1

例題已知a,/?,c￡R+,a+l+c=l,A/=<3a+1+<3b+1+J3c+1,求口

解M2+24+1b-Qb-4J+2c―~^~c4-=?k分1+61

.衍+問+目<(3a+l)+l+(3"l)+l+(3c+l)+l=45

222

[]

例題計算[&]+[及]+[6]]+…+[J〃2-1]

解因為[&]=[#7T]=Q(i+i)2-i]=i；

[萬]=h/?7i]==Q(2+i)2_i]=2；

M==Q(3+1)2-1]=3;

I7F]=[VF+T]==[&+i)2-、=z；

所以，[-]+[行]+[g]]+…+[J〃2一]]

?一!?一!,一!

=1x3+2x5+3x74-+5—1)X(2(〃-1)+1)=Z-(2)+1)=2E4+Z'

k=\k=\k=\

(〃-l)〃(4〃+l)

6

例題求滿足下列條件的自然數(shù)，z：mink+lWlLzo。。，其中[幻表示不超過x的最

kwN+I卜)

大整數(shù).

解問題等價于k2+-^>2000,⑴存在即eN,k：+烏42001(2)

由(1)=(公一iooo)2+”-1000220nmi門(二一lOOOf+”-100()220當時，上述式子取

k

得最小值，所以有(322-1000)2+〃-WOO'20n〃。1024x976

向XFHr+i/\—U.ZR/7，2001、2/2001、2、八77^/7。20012001\2

同理，由()式得一(暗——不)--〃+(《一)-之0,而max一(噌一一—)-=-(32-———)~

H<1024x977

例題將與互素的所有正整數(shù)從小到大排成數(shù)列，求出這個數(shù)列的第項。

解一的所有正整數(shù)中共有0(105)=奴3)以5)0(7)=48個與互素，他們從小到排列為：

q=1,4=2,。3=4%=8,%=11,,48=1°4。對于任一的a“，由帶余除法存在唯一的使

得an=105q+r,q>0,Sr<

由(叫，)，可得(，)，即廣€{4，。2，,?48)?

反之，對于任意固定非負整數(shù)，，€{4，。2，，。48}有(，)，于是

都是數(shù)列的項，從而存在正整數(shù)，使得4=1054+，。因此數(shù)列伍“}僅由

10到+4g1,2,，的數(shù)由小到大排列而成的。因為*,所以有

a2oio=105x41+42,而由%8=104,求得“42=91,所以々(no=4396。

例題設/S)=〃+[6]，證明對于任意給定的正整數(shù)，序列〃附)，

……中至少包含一個整數(shù)的平方。

證明設加=/+r,04r42a,則\[m=a,f(m)=a2+a+r=(a+\)2+(r-a-

若，則是平方數(shù)。

設rw0,則A={r+sk，seN,0<sWZ},8=^Z：2+sk，seN,Z<sW2Z},

如果meB,則存在正整數(shù)，使機^k2+s,k<s<2k,于是

f(m)-k2+s+k=(k+1)2+(s-k-1),0<s-k—1<k-1,所以

因此，/(m)或為平方數(shù)()，或所以只需要討論mwA的情況。

此時存在與使得，m-k2+s,0<5<-m+k

/(/(m))=f(m+k)=m+2k-k2+s+2k=(k+l)2+s+\,

由0Ks-14-1,得知J(一(m))或者為平方數(shù)(當s-l=0時),或/V(，〃))eA

若/(/(/n))eA,則

/(/1(m)))=m+2k+[-Jm+2k]-m+2k+[yjk2+s+2k.]=m+3k+\

/(/(/(m))))=m+3k+l+[-Jm+3k+1]=m+3k+l+k+l=(k+2)2+s-2

如此繼續(xù)，可知或存在某正整數(shù)/使/(/。〃))為平方數(shù)，或數(shù)列

/(/(?!)),/(/(^))),的每一項與某平方數(shù)的差構成數(shù)列,，，……，由于對于給定的正

整數(shù)是一個固定的正整數(shù)，所以，以上差數(shù)數(shù)列必將終止于有限項，即存在某個正整數(shù)（偶

數(shù)），使得數(shù)列的某項為平方數(shù)。

例題設P為奇質數(shù)，。力是小于P的正整數(shù)，證明:

。+8=〃的必要充分條件是：對任何小于P的正整數(shù)〃，均有—+—=正奇數(shù).（其

pJLP.

中方括號［］表示取整.）

證明：必要性：若a+O=p,〃是小于p的任一正整數(shù)，記2段=〃，3=u，因p

pJLP_

為質數(shù)，故網(wǎng)，也皆不為整數(shù)，因此有d月,0＜。＜1,0＜尸＜1,使網(wǎng)="+a,

PPP

--=v+/7,相加得，2〃=〃+u+(a+/?)故a+尸為整數(shù)，由于0＜。+尸＜2,則必

P

有a+/?=l,從而〃+u=2〃—1=奇數(shù).

十八也升"/十rI-rV-Tg她但士2cm2bfl-rh跖

充分性：右對任何小于P的1正整數(shù)〃，均有---+-----=正奇數(shù).......

pJLP_

令c=〃—。，則a+c=p,據(jù)必要性的討論可知，對任何小于〃的正整數(shù)〃，均有

2an2cn

-----十——=正奇數(shù),因此由，，對任何小于p的正整數(shù)〃，均有

P\\_P

2bn2cn

+-=--偶-數(shù)由進而可得，對任何正整數(shù)團，均有

P_P

—+—=偶數(shù).....，（事實上，設根=pr+幾OK〃v〃，，則

PJLP_

2bm\\2cin\+\2c（pt+nf\「2加］F2cn聞”

.P］LP］LP」1P」

為證充分性，只要證，b=c,用反證法，假若。wc,不妨設?！礳,貝U

\＜h-c＜p9因p為質數(shù)，有（2（〃-c）,p）=l,因此有正整數(shù)機與左,使

2（b—c）m-pk=T,據(jù)此知，女必為奇數(shù)，且

—=—+-+，顯然，型+工。整數(shù)，（否則，若生"+'=整數(shù)，則由,

PPPPPPP

zr)in2rmI

—■為整數(shù)，因(24p)=l,則〃加=上=整數(shù)n—=整數(shù)，矛盾).

PPP

今由四+工。整數(shù)，則網(wǎng)+工=二絲,現(xiàn)對式兩邊取整，得

PPPP

+%=奇數(shù)，這與式矛盾.

故原假設不真，因此b=c,即b=p-a,所以a+h=p.

第三章同余理論

一、基本概念

.定義:若整數(shù)被整數(shù)(2)除的余數(shù)相同，則稱同余于模，或對模同余.記為三().

.性質(i)三()O,即G.

(ii)若三()三()，則三().

(iii)若三()三()，

則土三土()鹵三()

(iv)設()…0…是兩個整系數(shù)多項式,滿足三()(WW).若三()，則()三()().

(v)三()二三(/一),

（Gm）

(vi)若》,(),則存在整數(shù)使得三().

稱為對模的逆或倒數(shù)，記為()

a=b(mod町)

(vii)]、同時成立oa三b(口).

a=o(modm2)

(而)若三()三(),且(),則三(儂).

剩余

二、剩余類與剩余系

、設為正整數(shù)，把全體整數(shù)按對模的余數(shù)分成類，相應個集合記為：，…，其中{GW余數(shù)W}

稱為模的一個剩余類。

性質：對任意、丘，貝(I、6<=>=().

、完全剩余系：設,…為模的全部剩余類，從每個里任取一個，得個數(shù)，…組成的數(shù)組，叫

做模的一個完全剩余系。，…叫做模的最小非負完全剩余系。

性質(i)個整數(shù)構成模的一完全剩余系o兩兩對模不同余。

(ii)若()，則與同時跑遍模的完全剩余系。

、既約剩余系：如果里的每一個數(shù)都與互質，則叫與互質的剩余類，在與模互質的全部

剩余類中，從每一類任取一個數(shù)所做成的數(shù)組，叫做模的一個既約剩余系。

性質(i)與?；ベ|O中有一個數(shù)與互質；

(ii)與?；ベ|的剩余類的個數(shù)等于(p(m);

(iii)若()，則與同時跑遍模的既約剩余系。

(iv)設0,則是對于模的階O三()，且

，…對模兩兩不同余.

特別地①()O,…0°構成模的一個既約剩余系.

三、重要定理

、定理:設整數(shù)>，且0.則有"三().

、定理:設是素數(shù),則對任意正整數(shù)有三().

證明:若，則顯然成立.若(),則,2a,…,()對余數(shù)各不相同(若()(<W),則，矛盾!).

所以,2a...()......()(),

即?()!三()!()：()A=().

應用設()是使得三()的最小正整數(shù)，則④0.

、定理:設是素數(shù)，則()!三().

中國剩余定理:設，，而，…是個兩兩互質的正整數(shù)，令1012…1M…，則下列同余式組：

x=a](mod"?1)

j(mod”)的正整數(shù)解是

x=ak(modmk)

三1MiM2M2M2???().其中,是滿足A//A7]三l(mod〃5)

例題已知為正整數(shù)，且為奇數(shù),().證明Zk"■

k=\

證明:??,，…構成的完系，()，.,?，…,2m也構成的完系

...Z(2幻"三￡k"(modm),即(2"—1)工1三0(modm).

k=]k=\k=]

?.?(),...團工《得證.

k=l

例題求出大于的整數(shù)〃的個數(shù)，使得對任意的整數(shù)a,都有〃la?'—。

25

解設滿足條件的正整數(shù)組成集合，若〃|。25一。，m\a-a,則[加,"]]。25一。，因

此中全部數(shù)的最小公倍數(shù)也屬于，即中的最大數(shù)是其余每個數(shù)的倍數(shù)。m\a25-a,則加的

約數(shù)也整除。25一。，于是只需確定最大數(shù)m,其一切大于的約數(shù)組成集合。

vw|225-2,m|325-3,并且(22$-2,3?5-3)=2x3x5x7*13,由費馬小定理，易證

2x3x5x7xl3|a25-a,所以加=2x3*5x7x13,集合共有個元素。

評注利用特殊值法確定最大值，再進行證明是處理競賽問題的典型技巧。

例題設5={1,2,,400},7={%,4,，4oo}是S的一子集,且滿足

200

()的任兩個數(shù)之和不等于；()Z4=38452。

/=|

證明中奇數(shù)的個數(shù)是的倍數(shù)，且中所有數(shù)字的平方和為一定數(shù)。

證明由q。401—%對任何lWi"W200成立知

S={al9a29,a200}u{401-tZp401-a2,,401-a200},所以

400200200200200

=￡a,2+z(4m_卬2=2＞；—802〉.+4012x200,即

n=\z=li=\i=li=l

200

200x401x267=2^a,.2-802x38452+4012x200

/=1

若記中奇數(shù)的個數(shù)為，則將上式關于取模得

0三2x—0+0(mod8)nxm0(mod4),因此，中奇數(shù)的個數(shù)是的倍數(shù)，且求得

200

工卬=10045852。

/=!

例題已知為大于的素數(shù).且77+”+WH-------------—=--,a,beN,.(,)，證明p|a。

I22232(p-1)2b1

.證明對于不超過的自然數(shù)，由于(,),所以存在唯一的不超過的自然數(shù)，滿足

kx=l(modp)o而且，當或有或。當24人《〃一2時，有

2Kx<〃一2,九，故當取遍，，...,時，也取遍，，....，。

因為(，(〃-1)!)=1,由去三1(modp)可得到

(p-iy.kx=(p-l)!(modp)^(p-V)\x=―—―(modp),所以

k

卑出萼①(p.D”

b&=ikx=i

s((p-l)!)2P(Pl[2p-l)0)

o

因為是大于的素數(shù)，所以不小于，所以()!含有因數(shù)，從而

((.-1)!)2p—0""—I'三(Xmodp),即(也力)衛(wèi)三0(m0dp),因為

6b

(p,(p-l)!)=l,所以(p,((p-l)!『)=l,從而3三0(modp)n。三O(modp)

b

例題設為正整數(shù)，對任意的自然數(shù)有〃'+“,"+〃，則。

證明假設與不相等?？紤]有a+1,+1,則<。設是一個大于的素數(shù)，設是滿足條件

的正整數(shù)：〃三l(mod(p-l)),“三—a(modp),由孫子定理這樣的是存在的，如0().由費馬定

理a"=。"'7+'三a(mod(p-l)),所以a"+三Oh(也即

〃|》"+〃,再由費馬定理》"+〃三匕一。(p,所以p也一a,矛盾。

/(")

例題設/5)wN是使和式Zz能被〃整除的最小數(shù)，證明當且僅當〃=2"'時，

2=1

f(n)=2〃-1,其中7?iGZ,m>0。

/⑺

證明()首先證明若〃=2"',meZ,，〃20,則/(〃)=2”一1,是使工人能被整除的最

hl

小數(shù)。

2n-l2n-l

因為，一方面，Z&=(2鹿-D〃，所以，能被〃整除

k=\&=1

I1

另一方面,2〃-1是滿足條件的最小數(shù)。這是因為若/<2〃-2=￡"=-/(/+1).

A=I2

由于/,/+1中有一個為奇數(shù)，且

/+1W2〃—1=2w+,-1=>2",+'不整除/(/+1)n2'"不整除L(/+1)o

2

f(〃)

()再證若/(n)=2“—1,其中meZ,加20是使〃IZA成立的最小數(shù)，則必有〃=2"'?

k=\

否則當設〃=2"'p,meZ,加NO,pNl,〃為奇數(shù)。由于(2”小，〃)，故有孫子定理可知同余方

程組

x=OCmodZ')有解，即存在正整數(shù)/(O</<2""”=2〃)滿足上述同余方程組，且

x=p-l(modp)

都不是上述同余方程組的解，這是因為2〃—1/0(1110(12""1),2〃工〃一1(1110€1〃)，因為

/<2〃—1,且2!+'|/p\l+心'2p”Z0-H,從而，(心k2+這說明不是使

/(?)

〃|Z人成立的最小的/⑺。命題得證。

k=\

例題上22,勺,々，，％自然數(shù)，且滿足

引⑵-1)川(2J),聞(2%—1)川(*—1),證明勺=%==%=1。

證明設〃「股，，為中一個大于，不妨設勺>1。由勺|(2"*—1)得到2"，一1>1,即

2"*>2,所以々>1,由此可得%>1,同理可得k>1,%>1。

設4的最小素因子是Pi，因此有P21(2"'-1),即2"1三l(modp2).另外2°2TmKmodp)

設d=(4,P2-1)，則存在整數(shù)使

(/=加|+武。2-1),于是2"=(2叫)'(2—|)'三1(01(^02),從而d>l,故

P,<4<02-1<0252目是因。1是〃|的最小素因子)。同理可證

P2Vp3，，Pbl<0，P?<P|，從而Pl<P|，矛盾。

綜合所述，即有“=%==%=1

例題證明：存在無窮多個正整數(shù)，使得小+1有一個大于22+低的質因子.

證設(大于等于)是一個整數(shù)，是(帆!>+1的一個質因子，則P>加22°.

令整數(shù)滿足0<??<y,且〃三±/n!(modp).于是0<n<p-n<p9且

/i2=-1(modp)①

故(〃-=p2-4〃〃+4/=-4(modp)

所以(p-2〃)久〃-4,

p>2n+Jp-4>2n+《2n+dp-4—4>2n+\［2n偽

例題設是區(qū)間［,］中的整數(shù)，證明存在正整數(shù)使得是合數(shù).

證如果，令，則爐+產(chǎn)是一個大于的偶數(shù)，故為合數(shù)。

假設x*y,下面證明存在正整數(shù)，使得/"+y'是的倍數(shù)，且不等于。

設x2"+y2",令a=X2''',b=y2"^'a2+b2=257。如果a2/?=a=16,b=1,這與條件都

大于矛盾。下面只需要證明存在正整數(shù)，使得X*+y2”是的倍數(shù)。

事實上，由于x,y與互素，故存在正整數(shù)，使得，x三qXmod25'.因為xwy,

0Vx+y<257nq*0,±l(mod257)。又是質數(shù)，有費馬定理得

2571產(chǎn)-1=(q-l)(g+l)(q2+1)，+1)

在上述式子中()，()都不是的倍數(shù)，故存在正整數(shù)“G{1,2,,7},使得

/+1是的倍數(shù)，于是結論成立

第四章進位制與組合數(shù)

例題設為質數(shù).求證:C,：modp)

證明：.??三，…()必有某一個(WW)使得

nn-i

三(),從而

，。…()()…()三()…()…()三()!()

.n-i

rP()()???()()???()―r

o,因(())

p

應用問題.為奇素數(shù).求證,zC；￡,+i三().

/=0

,2

證.記則，

()()…(一)?(一)!(!…」)(一)!，

2p-1

由于((一)!(!).由于

2p-\

(一)!與互素，從而三().

對于ww—c](p+i)s+2*(p+i)，+({；)!?).而故三q().于是

2!(〃-1)!i=o

〃一1

三工。().

/=|

例題設為質數(shù)，，為兩個正整數(shù)，且，在進制表示下，分別為

。)出口區(qū))尸,仇＜證明

a={akak_xap,b=04q,p,

a=珠(modp)

b

證明考慮在模意義下的多項式(1+X)”的展開式中x在模意義下的系數(shù)，

(1+X)"=(1+x)atpk(1+幻華產(chǎn)'(1+幻％

三++(1+X)他()()

注意，這里用到了當為質數(shù)時，對任何均有p|C