《初等数论(闵嗣鹤、严士健)》第三版

cl第一章整数的可除性§!整除的概念•带余除法.证明定理3定理3若q,a2,--,a“都是相得倍数,卯も，…，依是任意〃个整数,则+q2a2+…+q“a”是相得倍数.证明:；a”％…,％都是〃，的倍数。,存在〃个整数0いタ2,…p“使at=ptm,a2=p2m,…，an=pnm又一,%,…,q”是任意〃个整数q四+%ム+…+4.。”=qlp{m+q2p2m+---+qnpnm=(Piqi+q2P2+~+q“p“)m即qtat+%ム+…+%4是〃1的整数.证明3|〃(〃+1)(2〃+1)证明vn(n+1)(2〃+1)=n(n+l)(/i+2+n-1)=〃(〃+1)(m+2)+(〃ー1)〃(〃+1)又•.•〃(〃+1)(〃+2)，(〃ー1)〃(〃+2)是连续的三个整数故31〃(〃+1)(〃+2),3|(n-l)M(/i+l)/.31〃(〃+1)(〃+2)+(〃ー1)〃(〃+1)从而可知 31〃(〃+1)(2〃+1).若0¥()+外〇是形如ax+by(x,y是任意整数,a,b是两不全为零的整数)的数中最小整数,PliJ(ax0+ )I(ax+by).证:,•・。カ不全为〇・・・在整数集合S={ax+by\x,yeZ}中存在正整数,因而有形如ax^by的最小整数叫+如Vx,ygZ,由带余除法有axby=(ax0+byG)q+r,04r<ax0+by0贝リr=(x-xQq)a+(y-yQq)bgS,由。ち+by。是S中的最小整数知r=O/.axQ+by。\ax+by•/axQ+by0Iax+by ( 为任意整数)/.ax0+刀〇\a,ax0+byQ\b/.ax0+byQI(a9b).又有(a,b)|a(a9b)\b/.(a9b)IaxQ+byQ故ax0+by0=(a9b).若a,b是任意二整数,且ルwO,证明:存在两个整数s,t使得a=加+f,If区成立,并且当b是奇数时,s,t是唯•存在的.当b是偶数时结果如何?证:作序列…,—U,ー网,-U,〇,LI■,瓦ーL1…则a必在此序列的某两项之间2 11 2 2112即存在一个整数り,使幺ル归〃<如(り当り为偶数时,若い〇.则令5=纟"="加=a-汐则有0<a-bs=t=aー里b=a-^\b\<^\b\/.|r|<"若bvO则令$=-£/=aー加=q+4み,则同样有レJくザ(n)当q为奇数时,若b>0则令s= =a-bs=a-^—^-b,则有^lb=a-^^lb=a-^咏。.•昨W--</=a-bs=a-2若b<0,则令5=ー纟土Lf=a-加=a+"^,则同样有|r|4回综上所述,存在性2 2 112.得证.下证唯一性当b为奇数时,设a=bs+f=加]+ム则レーム|=|b(S]-s)|>网而か省Ml碧，”心M+同训矛盾故s=s"=ム当b为偶数时,s」不唯一,举例如下:此时ン为整数へb-b,へ,b、hiib3.-=&.l+-=&.2+(--),/]=25W-2§2最大公因数与辗转相除法1.证明推论4.1推论4.1a,b的公因数与(a,b)的因数相同.证:设d’是a,b的任一公因数,，d'|a,dr|b由带余除法a=bq{+厶,/?=4%+り‘・・・，72=「国用，°=rn+lr„<r„-i<--<rt<b•••(a,b)=r“•••d'\a-bql=rt,d'\b-rxq2=r2,—,d'\rn_2=rn_tqn+rn=(a,b),即d’是(。力)的因数。反过来(a,b)|a且(a,b)ルI若d"|(a,b),则d"[a,d"|b,所以(a,b)的因数都是a,b的公因数,从而。,わ的公因数与5,。)的因数相同。.证明:见本书P2,P3第3题证明。.应用§1习题4证明任意两整数的最大公因数存在,并说明其求法,试用你的所说的求法及辗转相除法实际算出(76501,9719).解:有§1习题4知:bwZ,bw0,ヨsJ£Z,使〃=加+rJf区一。,ヨS1,ム,使/?= +ム,|ム区!•«ア,…,如此类推知:ヨS〃，ム，0ー2=レード〃+ム;ヨs”+i，ム+1，ムー1=ムL+】+ム+1；且I.i<LO<<...<l£l<lLL"-2~22~一2"-2"+,而b是ー个有限数,.,.ヨ〃eN,使ら+i=0.•.(4,/?)=(b,t)=(しム)=(ム冉)=…=(ム,ム+1)=(ら,〇)=ム，存在其求法为:(a,b)=(b,a-bs)=(a-bs,b-(a-加)s1)=….-.(76501,9719)=(9719,76501-9719x7)=(8468,9719-8468)=(1251,8468-1251x6)=(3,1)=1.证明本节(1)式中的〃く皿log2证:由P3§1习题4知在(1)式中有°=か<い号4,〈…く券《，而へ.・”2,，2“。, .•・〃勺。g/=皿,即〃4皿T 2log2log2§3整除的进ー步性质及最小公倍数.证明两整数a,b互质的充分与必要条件是:存在两个整数s,t满足条件如+初=1.证明必要性。若(a,b)=l,则由推论1.1知存在两个整数s,t满足:〃s+初=(〃,/?),as+bt=1充分性。若存在整数s,t使as-i-bt=l»则a,b不全为〇〇又因为(a9b)\a9(a9b)\b,所以又因|as+加)即伍,6)|1。又(スの>0,/.(a9h)=1.证明定理3定理3[al,a2---,a„]=[|at|,|a21•••,1a„|]证:设[。い。2,…,。」=叫，则ルム(i=l,2,…・・.|もII叫(i=l,2,…又设口ー・/I，…,a\]=m2则m2\m]O反之若|m2,则at\m2，.,・机]|m2从而㈣=加2,即…，叫=ロ％I，…，1。/23.设しバ+。〃_]ス〃ー+…+。拝+。0 (1)是ー个整数系数多项式且へ,。〃都不是零,则(1)的根只能是以。。的因数作分子以ム为分母的既约分数,并由此推出血不是有理数.证:设(1)的任一有理根为ム,(p,q)=l,q>l。则q（"）"+an-\（K）〃T+…+q"+%=0qqqa“P〃+a,iP”“q+…+〃]Pグ"+旬グ=〇 （2）由（2）-anpn=jp"-%+…+%pグ"+aQqn，所以q整除上式的右端,所以り丨ムP",又（p,り）=1,り>1,所以（り,p"）=L「•qk；又由（2）有〃"p"+*_]p"%+…+qpグ々二ー〃〇グ因为p整除上式的右端,所以尸为〇グ，（p,q）=l,り>1,所以（グ,p）=l,.*.pIan故⑴的有理根为ム,且q假设及为有理数,x=V2,.".x=ヒ,.ゝ2q2=ヒ,.ゝ2q2=p2,.\（卩2,ザ）=（2q2,p2）=q2>1Q但由（p,q）=l,タ〉1知（//,ダ）=1,矛盾，故也不是有理数。§4质数•算术基本定理1.试造不超过100的质数表解:用Eratosthenes筛选法（1）算出。100=10a(2)10内的质数为:2,3,5,7有有理根只能是±1,±2,这与为其有理根矛盾。故正为无理数。另证，设正为有理数8=K,（p,q）=l,g>l,则q(3)划掉2,3,5,7的倍数,剩下的是100内的素数将不超过100的正整数排列如下:7-8-9-W17+«192027282950375859404748495057585960676869707778798087888990979899400.求82798848及81057226635000的标准式.解:因为8|848,所以8|んん=82798848=8x10349856=2'xB,又8|856,所以8|B,B=8x1293732=23xC,又4|32,所以4|C,C=4x323433=22xD又9|(3+2+3+4+3+3),所以9|D,D=9x35937=32xE,又9|(3+5+9+3+7),所以9|E,E=9x3993又3993=3x1331=3x1产所以A=2835113；同理有81057226635000=23-33-54-73-112-17-23-370.证明推论3.3并推广到n个正整数的情形.推论3.3设a,b是任意两个正整数，且a=p?'-P22 p„"<a>0,i=l,2,--,k,112+54--442224252627292+4243444546474S494+525455565759544264656b=pF•P?■•…Pケ,dNO,i=l,2,…，k,则(a,b)=pMp/……,[a,b]=p,.p/♦p?,其中先=min(%,以)，^=min(a,,^),i=\,2,---,k证:,/ =min(%,4)，.•.0</,<a,,0<<艮IPia,,Pi'I(i=l,2---k)：•fl姉ルバ，flP『f!ガ./=1 Z=1 i=l/=1•a•PilP2pFI(。,シ)，又显然のIpi'p?…p?:.pfP?…P；*=(a,b),同理可得p：'p£…p；*=[a,切，4=max{a,.,g}推广设q=p卜pキ…Ptk,阴=pヤPi1…p伊,…,ム=pFp件…pT(其中P,为质数，=1,2,…,为任意n个正整数i=l,2,…,〃,4N0), 则P："P并…=(《,。2,…,ム),加=min/},ノ=1,2,…,左P『P号…P)=M。2,ル=哽{片}，ノ=1,2,…，た.应用推论3.3证明§3的定理4(ii)证:设。=pf'p会…pf*，b=pppや…pf：其中Pl,P2,…,Pセ是互不相同的素数,6,Pi(1<|<^)都是非负整数,有

(a,b)=p?p".p34=min{«,以},l<i<k,[a,b]=pfpj'…p34=maxa,以},1<z<由此知他")[ス贝=「[p产=「1p”佃㈤+max{a®=KTガ+4=。ル从而有口,切=’セー.'=7V V (a,b).若2"+1是质数(n>l),则n是2的方嘉.证:（反证法）设〃=2'（/为奇数）,则2"+1=2*,+1=(2プy+1=(22*+1)[22*(/-1)-22rz-2)< 1<2?+1<(22*)/+1=2"+1,二2"+1为合数矛盾,故n一定为2的方塞.§5函数[x],{x}及其在数论中的ー个应用1.求30!的标准分解式.23,29解:30内的素数为2,3,5,7,11,13,17,19,23,29=15+4+3+1+0=23<73=30T+•••=10+3+=15+4+3+1+0=23<73=30T+•••=10+3+1+0=14a73030T+■•=6+1+0=7+・••=4+0=4930I「30

11J|_11230I「30 + T

13J|_132+,••=24-0=2,a\j3013=2+0=230 30 130 30 1n, ,%7=五+谈+…=1+0=1，«19=a19=a23=a2g=l工30!=223-3,4-55-74-112-132-17-19-23-292.设n是任一正整数，a是实数,证明:(ii)[«]+1(X+—(ii)[«]+1(X+—n+•••+n-1a+ n=[〃a]证:⑴设［a］=m.则由性质II知相く。＜〃?+1,所以 nm<na<nm+n,所以〃"2«＜〃m+〃,所以"iく"ク＜"2+1,又在m与m+!之间只有唯一整数m,n所以［四!］=机=［©.nkk+\(ii)[证法一]设ー4{a}v ,k=0,1,2,・・・,十ー1,TOC\o"1-5"\h\zn n则k<n{a}<+1,/.[na]=n[a]+k①当i+kヱ几ー1时,{a}+丄く攵+1+i<],[a+口=[a];nn n②当i+kN〃时,2>{a}+丄N421,[a+2]=[a]+l;nn n1 n-\・・.[a]+[a+上]+…+[a+-—]n nn-\ 1 n-\-k j n-\ :=Z1a+T=X[«+-]+Z[a+Ti=Q 〃 i-0 〃 i=n-k 〃=(n-え)[a]+&([a]+1)=〃[a]+k/.>[a+—]=[〃a]Mn［证法二］令…乎+2孙n-l・・・y(a+-)=Y[a〃 i=0a+—]-[na+l]=/(a)n.•./(a)是以丄为周期的函数。n又当ae[0,1)时,/(a)=0-0=0,aeRJ(a)三〇,即£[a+-]=[〃a]。i=on[评注]:[证ー-]充分体现了常规方法的特点,而[证二]则表现了较高的技巧。3.设a,万是任意二实数,证明:[a]-[夕]=[a-夕]或[a-夕]+1[2a]+[2/3]>[a]+[a+/3]+[/3]证明：(i)由髙斯函数[x]的定义有a=[a}+r,p=[^]+5,0<r<1;0<5<1〇则a-p=[a~\-[p}+r-s,r-s<1当r-sNO时,[a一夕]=[a]-网当r一s<〇时,[a一用=[a]-网T故[a-p]=[a]-[^]<a->ff]+1=[a]-[fi](ii)设a=[a]+x,£=[4]+y,04x,y<1,则有04x+y={a}+{£}<2ド面分两个区间讨论：①若04x+y<l,则[x+y]=O,所以[a+夕]=[a]+[夕],所以[2a]+[2夕]=[2[a]+2x]+[2网+2y]=2[a]+2网+2([x]+[y])>2[a]+2网=[a]+[用+[0+[a]=[a]+[a+夕]+[切②若14x+y<2,则[x+y]=l,所以[a+£]=[a]+[尸]+1。所以[2a]+[2J3]=[2[a]+2x]+[2网+2y]=2冋+2网+2([x]+[y])>2[a]+2[/?]+2([x]+[l-x])...Xと]つ，)=[a]+[切+[切+[a]+2+2(印+[r])>2[a]+2[/?]+l=[a]+[a+仞+[仞(ii)(证法2)由于a,タ对称,不妨设{a}N{夕}[2a]+[2/7]=[2([a]+{a})]+[2(げ]+{夕})]=2[a]+2网+[2{a}]+[2{夕}]N2[a]+2[夕]+[{a}+{夕}]=[a]+[#]+([a]+[£]+[{a}+{6}])=[a]+[£]+[[a]+{a}+[£]+{尸}]=[a]+[a+ガ]+/].(i)设函数れ噂在闭区间。4x4R上是连续的,并且非负,证明:和式gピ21表示平面区域QWxWR,0<yW/(x)内的整点(整数坐标的点)的个数.(ii)设p,q是两个互质的单正整数，证明:エ削+2」冰アザ(iii)设r>0,ア是区域ズ+アス4芦内的整点数,证明:ヂ=1+4(ア]十8)レダー・]一・卜3(iv)设n>0,T是区域常>0,y>0,xy^n内的整点数,证明:T=2ヨー时证明:(略).设n是任一正整数,且n=a()+aが++…，p是质数,。。4<p,证明:在バ的标准分解式中,质因数p的指数是h~p-1'其中，=a0+血+a2+….证明:在!！!的标准分解式中,质因数p的指数有限,即n=a0(+ユ山+ク2が+…十・ぶ‘，0at<p所以ハ唱+依卜…+图=(旳+クび+・・・+生?>^"り+ +YP+・・・+ -り+…+at=血+a28+1)+ +p+1)+•»•+%(pL，+ +…+1)而- ナ=—、・[”(?-1)+旳(?2-1)+〃ヤ》ー1)+…+ -1)]p—丄p一丄=旳+C^2(P+1)+ 4-p4-1)+・・・+ 4* 4*…4-1)p-1第二章不定方程§2.1习题1、解下列不定方程a)15x+25y=100 b)306x-360y=630解:a）原方程等价于:3x+5y=20显然它有一个整数解七=10,%=-2故一般解为jc=故一般解为jc=10-5/y=-2+3/(r=0,±l,±2,-)b）原方程等价于:17x-20y=35显然它有一个整数解x0=-7x35,y0=-6x35Ix=-7x35+20/故一般解为 《 （/=0,±1,±2,…）[y=-6x35+17/2、把100分成两份,使ー份可被7整除,ー份可被11整除。解:依题意即求7x+lly=100的正整数解,解得x0=8,y0=4一般解是:x=一般解是:x=8—11/y=4+7/(/=〇,±1,…)但除/=0外无其他正整数解，故有且只有100=56+443、3、证明：二元一次不定方程ax+by=N,a>0,b>O,(a,b)=1的非负整数解为证明：当N<0时,N

abNab的非负整数解为证明：当N<0时,N

abNab原方程没有整数解,而N

ab+1<0故命题!E确NN1।—4-1=1ab当N=0时,原方程有且只有一个非负整数解（0,0）而—=0ab因为（a,b）=l所以原方程有整数解（x0,y0）,y0=（-1）"-1 •',qn.x}N,Xo=（-1）"{q2,--- }N其中巴=[4],%,%,…,%],由于。>b>0,故x（）,あ中一正一负,可设x>0,y40b"-原方程的一般解是:ド="一4（/=0,±1,…）[y=y0+ar要求スO->0,y04-af>0=>—>z> ,ba仅当ー&是整数时,才能取，二ー比,否则t>-比a a a故这个不等式的整数解个数T是:当是整数时T=［チ］当是整数时T=［チ］T+T+1N x0 y0„ N ,因而 ー =—+ — =>T= 一 +1ah b a abbNab所以(p(ni)当比不是整数时ア=血ーー比=bNab所以(p(ni)\x=xn—bt证明2：二元一次不定方程。ス+刀=N的一切整数解为4° ,teZ,于し=%+G是由xNO,yNO得一比4,4工,但区间［-&,厶］的长度是总,故此区间内的ab ab' ab整数个数为［*］或［包］+loabab4、证明:二元一次不定方程ax+by=N,(a,b)=l,a>T,b>l,当N>ab-a-b时有非负整数解,N=ab=a=b则不然。证明:先证后一点,当N=ab-a—b时,原方程有非负整数解(ム,ル)=>/?|x04-l,tz|y0+1=>x0+1=M,y0+1=ah,k>1,/?>1=>ab(k+h)=ab,k+hN2,这是不可能的。次证,当N>ab-a-b时,因(a,b)=l,故原方程有整数解(x〇,y〇),一-般解是｛エ閣"=0,±1,…)要求xo-bt>O,yo-GNOn-&4,く也会证明存在满足这个不等式的整数，=ん可取使abxQ=btQ+r(0<r<fc)于是对于这个ち有:TOC\o"1-5"\h\z, ,< xーみ+1 __x-bt0=r<b-\t0> 而by。+〃，〇N%H—(Xq—b4~1)—(by。+ciXq—ab+a)=—(N—cib+a)>—(ab—a—b—cib+a)——1“b b" b by0+at0>0=>t0>--a这就证明了当N>姉-a-ル时,原方程有非负整数解..证明定理2推论。推论单位圆周上座标都是有理数的点(称为有理点),可以写成(±-^T，±4^)或(士4^，±-^7)a'+b~a+b~7a~+b~a+b~7的形式,其中a与わ是不全为零的整数。证明:设有理数x=丄,y=—(mw0)满足方程/+y2=I,gpl2+n2=m2,于是得I=±2abd,n=±(a2-b2)d,m=±(a2+b2)dsE/=±(a2-b2)d,m=±2abd,,2,2、, .uzbzヽZ,2ab cT-b~\_4x/1a~~b~2ab\ヒ亠m=±(a2+b2)d,由此得(x,y)=(±-5~^-,±—-~~77,±—~-7)0反之,cT+b~a+ケ a~+ba+b代入方程X?+y2=1即知这样的点在单位圆周上。2.求出不定方程x2+3y2=z2,(x,y)=l,x>0,y>0,z>0的一切正整数解的公式。解:设不定方程x?+3ザ=，，(x,y)=l有解则3/z-x或3/z+x因为3y2=z2-x2=(z-x)(z+x)=>3/(z-x)(z+x)=3/z-x或3/z+x202 2 -Z+X/ \——p--far.2/ \Z一XX+3y=Zny=アセー力或者y=(z+x)--イ导3/z+x§Jc3/z—x以下不妨设3/z+x②(x,z)=l,设(x,z)=d^Jd/x,d/znd/3y-=z2-_x；若,3/d,n9/ズー,9/エー=9/3y=>3/yn3/(x,y)与(x,y)=1矛盾!这样(3,の=lnd/ynd/y(•.・イ/3y)而1/xnd/(x,y)nd=1③(z+x,z-x)=l或2,设，=(z+x,z-x)n〃(z+x)-(z-x)=2x,，/(z+x)+(z-x)=2znr/(2x.2z)=2即.=l或r=2④若(z+x,z-x)=1,则=1,从而3y-二(z+x)(z-x)=> .(z-x)由引理可设平=q；z-x=h2,y=ab从而三,为证得x,z为整数,(x,z)=l,必须有a,b均为奇数,且3グ>ど⑤若(z+x,z⑤若(z+x,z-x)=2=>z+xz-x=1=>z+xz-x=1从而3y，=(z+x)(z_x)n|jj==.デ设・^―==ガ，；=",即X=3a2-1j2,y=2ab,7=3〃ユ+//,其中。,わ为ー奇ー偶,且有(a,b)=l4,解不定方程:x2+3y2=z2,x>0,y>0,z>0,(x,y)=1〇解:设(z-x,z+x)=ム易知[=l或2。由(z-x)(z+x)=3y2得z-x=3da2,Z+x=db2,y=daい或z—x=d。“，z+x=3da2fy=dab,a>0,b>0,(a,b)=1〇(i)当d=1：x=- Ly=ab,z ，a>0,b>0,(〃,/?)=1,3\b,a"同为奇数;(ii) 当d=2：x=|Z?2-3a2|,y=lab,z=b2+3a2,a>0,b>0,（a,b）=1,3，わ,明いー奇ー偶。反之,易验证（i）或（ii）是原不定方程的解,且x>0,y>0,z>0,（x,y）=l。3.证明不等式方程ザ+y2=z4",y）=i,x>o,y>o,z/x的一切正整数解.可以写成公式:x=4的，ーガ）,y=|グ+ガーI,Z=q2+が其中a>0,b>0,（a,b）=1,a,ルー单一双证明:由定理1知道原方程的解是・=2しZ,丁=ピーd；z=c-+d；c>d>0,（c,t/）=1»且c,d为一奇ー偶,其中，c=2ab,d=〇ー-ガ,a>b>0,（a,b）=1,且a,b为一奇ー偶.所以X=4姉（ビード），y=|グ+ドー6イガ|,Z=〃ユ+/Z是原方程的正整数解（x>0,y>0,z>0,（戈,y）=1,2/ズ,且ビ+ガ是奇数，原方程正整数的解有:（0,