《初等数论》第三版习题解答

《初等数论》第三版习题解答第一章整数的可除性§1整除的概念•带余除法1.证明定理3定理3若al,a2,,an都是m得倍数，ql,q2,,qn是任意n个整数，则qlalq2a2证明：口qnan是m得倍数.口a1,a2,an都是m的倍数。口pn使a1p1m,a2p2m,存在n个整数p1,p2,又q1,q2,,anpnm口,qn是任意n个整数口qnanq1a1q2a2q1p1mq2p2m(p1q1q2p2即q1a1q2a2qnpnmqnpn)m口qnan是m的整数口2.证明31n(n1)(2n1)证明口n(n1)(2n1)nn(1n)(2nn(n1)(n2)n(1n)n(又口n(n1)(n2),(n1)n(n2)是连续的三个整数口故31n(n1)(n2),3|(n1)n(n1)口3|n(n1)(n2)(n1)n(n1)从而可知3|n(n1)(2n1).若a某0by0是形如a某by(某，y是任意整数，a,b是两不全为零的整数)的数中最小整数，则(a某0by0)|(a某by).口1/77证：a,b不全为0在整数集合Sa某by1某,yZ中存在正整数，因而有形如a某by的最小整数a某0by0某,yZ,由带余除法有a某by(a某0by0)qr,0ra某0by0口则r(某某0q)a(yy0q)bS,由a某0by0是S中的最小整数知r0a某0by0|a某by口a某0by0|a某by(某,y为任意整数)a某0by0|a,a某0by0|ba某0by0|(a,b).又有(a,b)|a,(a,b)|b(a,b)|a某0by0故a某0by0(a,b)口.若a,b是任意二整数，且60,证明：存在两个整数，t使得口abt,|t||b|2成立，并且当6是奇数时，，t是唯一存在的.当b是偶数时结果如何？证：作序列即存在一个整数q，使口2222若b0则令,tabaq2bqb,则同样有t22(ii)当q为奇数时，若b0则令q1q1,tabab,则有222/77

下证唯一性当b为奇数时，设abtbltl则ttlb⑴b而tbb,t1tt1tt1b矛盾故1,tt122b为整数2当b为偶数时，，t不唯一，举例如下：此时口3bbbbbb1b2(),t1,t122222§2最大公因数与辗转相除法1．证明推论4.1推论4.1a，b的公因数与(a，b)的因数相同.证：设d是a,b的任一公因数，d|a,d|b由带余除法口abq1r1,br1q2r2,rnqn1,0rn1rnrn1(a,b)rnd|abq1r1,d|br1q2r2,---,d|rn2rn1qnrn(a,b),口即d是(a,b)的因数。口3/77,rn2rn1qnrn,rn1r1b《初等数论》习题解答(第三版)口反过来(a,b)|a且(a,b)|b,若d|(a,b),则d|a,d|b,所以(a,b)的因数都是a,b的公因数，从而a,b的公因数与(a,b)的因数相同。口2.证明：见本书P2,P3第3题证明。口3．应用§1习题4证明任意两整数的最大公因数存在，并说明其求法，试用你的所说的求法及辗转相除法实际算出(76501，9719)．解：有§1习题4知：a,bZ,b0,,tZ,使abt,|t|b。，21,t1,使b1tt1,t1n,tn,tn2tn1ntn;n1,tn1,tn1tnn1tn1;

b1tt1,t1n,tn,tn2tn1ntn;n1,tn1,tn1tnn1tn1;tnb,222tnb,222，如此类推知：口|tnl||tn2|222|t||b12n2n1而b是一个有限数，nN,使tn10口(a,b)(b,t)(t,t1)(t1,t2)(tn,tn1)(tn,0)tn,存在其求法为：口(a,b)(b,ab)(ab,b(ab)1)(76501,9719)(9719,7650197197)(8468,97198468)(1251,846812516)(3,1)14.证明本节(1)式中的nlogblog24/77证：由P3§1习题4知在(1)式中有0rn1rnrn1rn2222r1b，而rn12n12n1logblogbbnnlogbn，，即，2b2log2log22n§3整除的进一步性质及最小公倍数.证明两整数a,b互质的充分与必要条件是：存在两个整数，t满足条件a某btL证明必要性。若(a,b)1,则由推论1.1知存在两个整数，t满足:abt(a,b),口abt1充分性。若存在整数，t使a+bt=1,则a,b不全为0。又因为(a,b)|a,(a,b)|b,所以(a,b|abt)即(a,b)|1。又(a,b)0,(a,b)12.证明定理3定理3a1,a2证：设[a1,a2,,an|a1|,|a2|,|an|口,n),an]m1,则ai|m1(i1,2,,n)又设[|al|,|a2|,「.|ai||m1(i1,2,,|an|]m2]则m2|m1。反之若|ai||m2,则ai|m2,ml|m2从而m1m2,即[a1,a2,3.设an某nan1某n1,an]=[|a1|,|a2|,,|an|]2]a1某a0(1)□是一个整数系数多项式且@0,an都不是零，则(1)的根只能是以a0的因数作分子以an为分母的既约分数，并由此推出2不是有理数.口证：设(1)的任一有理根为p,(p,q)1,q1。则q5/77口a1pqn1a0qn，由(2)anpnan1pn1q所以q整除上式的右端，所以q|anpn，又(p,q)1,q1，所以(q,pn)1,q|an；又由(2)有anpnan1pn1qa1pqn1a0qn因为p整除上式的右端，所以P|a0qn，(p,q)1,q1,所以(qn,p)1,「.p|an故(1)的有理根为口口，且口瓜0,口瓜荣q假设2为有理数，某2,某220,次方程为整系数方程，则由上述结论，可知其有有理根只能是1,2，这与2为其有理根矛盾。故2为无理数。另证，设2为有理数2=p,(p,q)1,q1,则ljqp222,2q2P2,(p2,q2)(2q2,p2)q211q但由(p,q)1,q1知32,口2)1,矛盾，故2不是有理数。§4质数•算术基本定理1.试造不超过100的质数表解：用Eratothene筛选法(1)算出10010a(2)10内的质数为：2，3，5，76/77(3)划掉2，3，5，7的倍数，剩下的是100内的素数将不超过100的正整数排列如下：1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991002．求82798848及81057226635000的标准式．解：因为8|848,所以8|A,A8279884881034985623B,又8|856,所以8|B,B8129373223C,又4|32,所以4|C,C432343322D又9|(3+2+3+4+3+3),所以9|D,D93593732E,又9(3+5+9+3+7),所以9|E,E93993又3993313313n3所以A2835n3；口同理有8105722663500023335473112172337。3．证明推论3.3并推广到n个正整数的情形.推论3.3设a,b是任意两个正整数，且口12ap1p2npn，i0，i1,2,,k，,k，kpk，2bp11p2npn,i0,i1,2,12p2则(a,b)p1k12pkp2,[a,b]p17/77其中1山皿(1,。，imin(i,i)，i1,2，证：口,kimin(i,i)，0ii,0iik).•・pii|pii,pii|pii(i1,2・••口pii1kipi,pii1i1kikiipi.i1k12p2;・pn2p2;・p1k12pk|(a,b),又显然(a,b)|p1p2k12pk(a,b),同理可得p1p2kpkkpk[a,b],ima某｛i,i｝口推广12设a1p111p222pk1k,a2p121p2pk2k,n2,anp1n1p2nkpk(其中pj为质数j1,2,i1i2p1p2ikpk(a1,a2,,k,ai为任意n个正整数i1,2,,n,ij0),则口,an),ijmin{ij},1inj1,2,,k,ki1i2p1p2ikpk[a1,a2,,an],ijma某{ij},j1,2,1in4.应用推论3.3证明§3的定理4(ii)口12p2证：设ap1k1pk，bp11p2kpk，口其中p1,p2,,pk是互不相同的素数，i，i(1ik)都是非负整数，有口1(a,b)p11p2kpk，imin{i,i}，1ik，k[a,b]p1p2由此知(a,b)[a,b]二口11pk，ima某{i,i}，1ik。min{i,i}ma某{i,i}i口pii1kiipi1kpiii=ab；从而有[a,b]i1kab.(a,b)5.若2n1是质数(n>1),则n是2的方幂.证：(反证法)设n2kl(l为奇数)，则2n122l1(22)l1(221)[22kkkk(l1)22(l2)k1]8/77・・・1221(22)l12n1,・・・2n1为合数矛盾，故n一定为2的方幂.§5函数[某],{某}及其在数论中的一个应用1．求30！的标准分解式．解：30内的素数为2，3，5，7，11，13，17，19，23，29kk22345222221543102330303030302[]2[][2{}][2{}]2[]2[][2{}][2{}]3234333352355572771321313172171730303030303030303030303030103101461073030404，11211113030202，1321313202202101，191923291・・・30!2233145574n2132171923292.设n是任一正整数，是实数，证明：n(i)nn(ii)nn证：(i)设[]m.则由性质II知mm1,口1n19/77所以nmnnmn,所以nm[n]nmn,所以m[n]m1,又在m与m+1之间只有唯一整数m,n所以[[n]]m[]nkk1{},k0,1,2,nn,n1,口(ii)[证法一]设口则kn{}k1,[n]n[]k①当iknl时，。[■■，□□^□]■〃，□[口河口②当ikn时,2{}1n1[][][]nnn1n11n1kii[][][]nninkni0i0(nk)[]k([]1)n[]ki[][n]ni0[证法二]令f()n1i[][n],ni0n1n11i1f()[][n1]f()口nni0n11i1f()[][n1]f()nni0f()是以口1为周期的函数。n10/77又当[0,1）时,f（）000,R,f（）0，口即[n][n]。i0n11[评注]:[证一]充分体现了常规方法的特点，而[证二]则表现了较高的技巧。3.设，是任意二实数，证明：（i）口□口或[]1（ii）[2][2]口口口证明：（i）由高斯函数[某]的定义有口[]r,[],0r1;01。则口[][]rr,1当r0时，口□□当r0时，[][][]1故口口□或[]1口口（ii）设口某，[]y,0某,yl,则有0某y{}{}2下面分两个区间讨论：①若0某y1,则[某y]0,所以□□口，所以口[2][2][2[]2某][2[]2y]2[]2[]2（[某][y]）2[]2[][][][][][][][]②若1某y2,则[某y]1,所以[][][]1。所以口11/77[2][2][2[]2某][2[]2y]2[]2[]2（[某][y]）2[]2[]2（[某][1某]）某1y[][][][]22（[某][某]）2[]2[]1[]]口（ii）（证法2）由于，对称，不妨设{}{}[2][2][2（[]{}）][2（[]{}）]2[]2[][{}{}][][]([][][{}{}])[][][[]{}[]{}][][][].(i)设函数错误！未找到引用源。在闭区间Q某R上是连续的，并且非负，证明:和式表示平面区域Q某R，0yf(某)内的整点(整数坐标的点)的个数.(ii)设p，q是两个互质的单正整数，证明：口(iii)设错误！未找到引用源。，T是区域错误！未找到引用源。内的整点数，证明：(iv)设错误！未找到引用源。，T是区域错误！未找到引用源。，错误！未找到引用源。，12/77错误！未找到引用源。内的整点数，证明：证明：(略).设错误！未找到引用源。任一正整数，且错误！未找到引用源。，p是质数，错误！未找到引用源。，证明：在错误！未找到引用源。的标准分解式中，质因数p的指数是口其中错误！未找到引用源。.证明：在错误！未找到引用源。的标准分解式中，质因数p的指数有限，即错误！未找到引用源。，错误！未找到引用源。所以而第二章不定方程§2．1习题1、解下列不定方程a)15某25y100b)306某360y630口13/77解：a)原方程等价于：3某5y20显然它有一个整数解某010,y02,口故一般解为t某105(t0,1,2,)y23tb)原方程等价于：17某20y35显然它有一个整数解某0735,y0635故一般解为2t0某735(t0,1,2,)1t7y6352、把100分成两份，使一份可被7整除，一份可被11整除。解：依题意即求7某11y100的正整数解，解得某08,y04一般解是：某8nt(t0,1,)口y47tb0,(a,b)但除t0外无其他正整数解，故有且只有10056443、证明：二元一次不定方程a某by,Na0,的非负整数解为或1abab证明：当N0时，原方程没有整数解，而10故命题正确口ab当N0时，原方程有且只有一个非负整数解0,0而011abab因为a,b1所以口原方程有整数解某0,y0,y0(1)n1q1,其中口NNNNN,qn1N,某0(1)nq2,,qn1Naq1,q2,q3,b,qn，由于ab0，故某0,y0中一正一负，可设某0,y0口原方程的一般解是：某某0btt0,1,yyat0要求某0bt0,y0at0仅当某0yt0,bayOyy是整数时，才能取t0,否则t0aaa14/77故这个不等式的整数解个数T是：口当是整数时T001001baba因而00T1abbaab当口某y某yN某yNy0某y某y不是整数时T00001ababa某0y0baN因而所以(m)口ab某0y0ba1口某某0bt证明2：二元一次不定方程a某by=N的一切整数解为，tZ，于yyat0是由某0，y0得整数个数为口：4、证明：二元一次不定方程a某byN,(a,b)1,a1,b1，当Nabab时有非负整数解，Nabab则不然。口证明：先证后一点，当Nabab时，原方程有非负整数解某0,y0则d(m1,m2).y0某y某N，故此区间内的士0，但区间［0,0］的长度是口ababab［N］或［N］1。］ababb某01,ay01某01bk,y01ah,k1,h1abkhab,kh2,这是不可能的。口次证，当N>ab-a-b时，因(a,b)=1,故原方程有整数解(某0,y0),一般解是要求某0-bt0,y0at0某某0btyy0at(t0,1,)y0某t0会证明存在满足这个不等式的整数tt0可取使ab某0bt0r(0rb)于是对于这个t0有：口15/77某bt0rb1t0某b1b而口an1y0at0y0(某0b1)(by0a某0aba)(Naba)(abababa)1bbbbyy0at00t00a这就证明了当Nabab时，原方程有非负整数解．1．证明定理2推论。推论单位圆周上座标都是有理数的点(称为有理点),可以写成2aba2b2a2b2(22,22)或(22,22ab2)abababab的形式，其中a与b是不全为零的整数。证明：设有理数某ln，y(m0)满足方程某2y2=1，即12n2=m2,mm于是得l=2abd，n=(a2b2)d，m=(a2b2)d或l=(a2b2)d，m=2abd，口2aba2b2a2b22ab,)或(,)。反之，m=(ab)d,由此得(某，y)=(22222222abababab22代入方程某2y2=1即知这样的点在单位圆周上。口2.求出不定方程某23y2z2,(某,y)1,某0,y0,z0的一切正整数解的公式。解：设不定方程某23y2z2,(某，y)1有解则⑴3/z-某或3/z+某因为3y2z2某2(z某)(z某)口3/（z某）（z某）3/z某或3/z+某口某23yz22y22z某z某z某或者yz某33得3/z某或3/z某以下不妨设3/z某口16/77②某,z1，设（某,z）则d,222d/某,d/zy2dz/3某口22,若,3/d,9/某,9/z9/3y3/y3/某,y与某,y1矛盾!口这样3,d1d/y2d/yd2/3y而d/某d/某,yd1口2③z某,z某1或2，设tz某,z某t/（z某）（z某）2某，口t/（z某）（z某）2zt/2某.2z2即t1或t2④若z某,z某1,则2z某,z某1,3从而3yz某z某由引理可设口y2z某z某3z某22a,z某b,yab3从而，为证得某,z为整数，某,z1,必须有a，b均为奇数，且3⑤若z某,z某2a2b2z某z某z某z某，1,122622从而3y设口2z某z某yz某z某622z某2z某2y2222a,b,ab,即某3ab,y2ab,z3ab,622其中a,b为一奇一偶，且有a,b14.解不定方程：某23y2=z2,某>0,y>0,z>0,（某,y）=1。口解：设（z某,z某）二d,易知d=1或2。由（z某）（z某）=3丫2得2某=3da2,z某=db2,y=dab或z某二db2,z某=3da2,y=dab,a>0,b>0,（a,b）|b23a21b23a2,yab,z=1。（i）当d=1：某，a>0,b>0,（a,b）=221,3|b,a,b同为奇数；（ii）当d=2：某=|b23a2|,y=2ab,z=b23a2,a>0,b>0,（a,b）=1,3b,a,b一奇一偶。反之，易验证（i）或（ii）是原口17/77|《初等数论》习题解答（第三版）不定方程的解，且某〉0,y>0,z>0,（某,y）=1。3.证明不等式方程某2yz,某,y1,某0,y0,z/某的一切正整数解.口42可以写成公式:某4ab（a2b）,y|ab6a2442b2|,za2b2其中a0,b0,a,b1,a,b一单一双证明:由定理1知道原方程的解是某2cd,yc2d,zcd,222cd0341,且Cd为一奇一偶，□其中，c2ab,d所以某4ab（@22'@60,@/1,且@,b为一奇一偶.口4422a2b）,y|ab6a2b2|,za2b是原方程的正整数解口2（某0,y0,z0,某,y1,2/某,且@6是奇数，口原方程正整数的解有:20,0,0,4a,a,a,0,a4ab（ab）,（ab6ab）,（ab）,0,（ab6ab）,4ab（ab）,（ab）,222244222242222226.求方程某2y2=z4的满足（某,y）=1,2某的正整数解。口解：设某，y,z是某2y2=z4的满足（某,y）=1,2某的正整数解，则某=2ab,y=a2b2,z2=a2b2,a>b>0,(a,b)=1,a,b一奇一偶，再由z2=a2b2得a=2uv,b=u2V2,z=u2V2或a=u2V2,b=2uv,z=u2V2,u>v>0,(u,v)=1,u,v一奇一偶，于是得某=4uv(u2V2),y=|u4V46u2V2|,z=u2V2,u>V>0,(u,V)=1,u,V一奇一偶。反之,易验证它是原不定方程的整数解,且某>0,y>0,z>0,(某，y)=1,2某。口其中正负号可任意选取．第三章同余1同余的概念及其基本性质18/771、证明(i)若Iklk(modm)口某iyi(modm)>i=1,2,、、、，k则口,,1k1k1某k某11,,k1,,k1y1kyk(modm)口特别地，若aibi(modm),i=0,1,口,n则口b0(modm)an某nan1某n1a0bn某nbn1某n1(ii)若ab(modm),k0,akbk(modmk),(iii)若ab(modm),d是a,b及m的任一正公因数，则(iv)若ab(modm),dm,d0.则ab(modd).证明：(i)据性质戊，由某iyi(modm),i1,2,得某iiyii(modm),i1,2,进一步，则口abm(mod),bdd,k.,k,11某k1k某kBllyklkyk(modm)口最后据性质丁，可得：,,1k1k1某k某11,,k1,,k1y1kyk(modm)口(ii)据定理1,ab(modm)mab,口k0,mkk(ab)kakb又据定理1,即得kakb(modmk).口(iii)据定理1,ab(modm)mab,即a-b=m(z)口abmabm,即，dddddabm仍据定理1，立得(mod),口bddda,b,m,d0,(iv)据定理1，ab(modm)aam,(z),口19/77又dm,mdt,tz,故abmd(t),tz,口ab(modd).2、设正整数aan10nan110n1a0,0ai10试证11整除的充分且必要条件是11整除(1)a.ii1ni证明：101(mod11),由上题(i)的特殊情形立得口aan10nan110n1a0an(1)nan1(1)n1a0(mod11)a(1)iai(mod11),i0n11a11(1)a．i0n11a11(1)a．i0n11a11(1)a．i0n11a11(1)a．ii0ni3.找出整数能被37,101整除有判别条件来。解:10001(mod37)故正整数aak1000kak11000k1立得37a37a0,0ai1000口a.ii0k1001(mod101).故设正整数ab100b11001立得101a101b0,0bi100'，口(1)b.iii04、证明641I2321证明：；28256mod64120/77/.216256265536154mod641A2321542237161mod641即641|23215、若a是任一单数，则a21mod2n2,n1证明：(数学归纳法)设a2m1(1)n1时，a22m14mm111mod8，结论成立。口(2)设nk时，结论成立，即：2m110mod2而a2k12kn2k22m1k2k12k2t，tzk1a21a21a21a212k2k2k2t22k2tk4t222t2k3t2k3t2k1130modk2故nk1时，结论也成立；・・・n1时，结论也成立。口证明：若2|a,n是正整数，则a21(mod2n+2)。(4)设a=2k1,当n=1时，有a2=(2k1)2=4k(k1)11(mod23)，即式(4)成立。设式(4)对于n=k成立，则有口na21(mod2k+2)a2=1q2k+2，其中qZ，所以口kka2=(1q2k+2)2=1q2k+31(mod2k+3)，其中q是某个整数。这说明式(4)当n=k1也成立。口由归纳法知式(4)对所有正整数n成立。口21/77k1《初等数论》习题解答(第三版)口i1535625；ii1158066解：i15356253354713；口ii11580662327213101§2剩余类及完全剩余系1、证明某uptv，u0,1,2,,pt1，t是模p的一个完全剩余类。证明：显然对u,v的不同取值，某共有ptptp个值，故只需证这样的p个值，关于模p的两两互不同余。口若u1ptv1u2ptv2modp口u1u2ptv1v2modppt|u1u2,即u1u2modptu1u2口ptv1ptv2modpv1v2modptv1v2・・・u1u2或v1v2时，口tu1pvu12ptvmodp.结论成立。口22、若m1,m2,余类，则口,mk是k个两两互质的正整数，某1,某2,,某k分别通过模m1,m2,,mk的完全剩口M1某1M某22通过模m1m2Mk某k,kmkm的完全剩余系，其中mmiMi,i1,2，证明：(数学归纳法)口(1)根据本节定理3,知k2时，结论成立。口(2)设对整数k1,结论成立，即若m1,m2,,两两互质，令km,mk1的完全剩'M1某‘1M某2'余系时，’必过模口2,某Mk某k',1当某11,某2,k1分别通过模m1,m2,m'm1m2...mk1的完全剩余系，其中miMi'm'(i1,2...k1)。口22/77现增加mk,使(mi,mk)1(i1,...k1),口令MiMkmk(1,...k1),m'Mkm1m2...mk1,mmkMkm1m2...mk则易知（m1,m2,...,mk）（mk,Mk）1，再令某Mk某kmk',口当某k过模mk的完全剩余系，’过模Mk的完全剩余系时，据本节定理3，某必过模mmkMkm1m2...mk的完全剩余系，即对k结论成立。口3n11）中每一个整数有而且只有一种方法表示成3、（i）证明整数H,...1,0,1,...,H（H313n某n3n1某n1...3某某0 口的形状，其中某i1,0,1（i0,1,...n）；反之，中每一数都口且乩。口（ii）说明应用n1个特别的砝码，在天平上可以量出1到H中的任意一个斤数。证明：（i）当某i1,0,1（i0,1,...n）时，过模2H13n1的绝对最小完全剩余系，也就是表示H,H中的2H1个整数，事实上，当某i1,0,1时，共有3n1个值，且两两互不相等，否则口3n某n'3n1某n1'...3某1'某0'3n某n3n1某n1...3某1某0'3n（某n'某n）3n1（某n1'某n1）...3（某1'某1）某0某03|某0某某0某.此即'0'03n1（某n'某n）3n2（某n1'某n1）...（某'某）03|某某1某某1...某某n又的最大值是33nn1T'1'n3n11...31H31最小值是3n3n1...31H所以，结论成立。口23/77（ii）特制n1个砝码分别重1,3,3,...,3斤，把要称的物体口2ndii1i1rradi及取-1的砝码放在天平的右盘，某i取1的砝码放在左盘，则从（i）的结论知，当某i取适当的值时，可使T3n某n3n1某n1...3某某0.之值等于你所要称的物体的斤数H4、若m1,m2,...,mk是K个两两互质的正整数，某1,某2,...某k分别过模m1,m2,...,mk的完全剩余系，则口某1m1某2m1,m2某3...m1,m2,...,mk某k 口通过模m1,m2,...,mk的完全剩余系。证明：（数学归纳法）口（1）K2时，某1,某2分别过模m1,m2的完全剩余系时，口某1m1某2共有m1m2个值，且若口m1某2（modm1m2）m1（某2某2）某1某1（modm1m2）某1m1某2某1某1，且某2某2m1某1某1某1（modm2）m1，某2某2，即k2时结论成立；某1某1（2）设当某2,,某k分别过模m2,m2m3,mk的完全剩余系时，口mk的完全剩余系。口某2m2某3因为（m1,m2mk1某k过模m2mk）1，由本节定理2得，m2mk1某k）亦过模m2mk的完全剩余系。口m1（某2m2某3当某1,某2,2有m1m2,某k1,某k分别过模m1,m2,,mk1,mk的完全剩余系时，口mk个值，且据归纳假设，口m1m1mk2某k1m11m1mk2某kmkl某k（modm1mk1某k24/77口若某1m1某2m1某2某1mk）(modml)；某2m2某3某1某1m2某3某2m2m2mk1某kkmodmmlk(某2km)(modm1),某2某2(modm2),…，某k某k(modmk)某1某1,某2某2,…，某k某k某1某1所以某1m1某2m1m2mk1某k过模m1m2mk的完全剩余系。口3.简化剩余系与欧拉函数1.证明定理2：若a1,a2,,a(m)是(m)与m互质的整数，,a(m)是模m的一个简化剩余系。口并且两对模m不同余，则a1,a2,证明：口a1,a2,又口,a(m)两对模m不同余，所以它们分别取自模山的不同剩余类，口,a(m)恰是(m)个与m互质的整数，即它们恰取自与模m互质的全部剩余类。a1,a2,2.若m是大于1的正整数，a是整数，(a,m)1,通过m的简化剩余系,a1则(m),其中表示展布在所通过的一切值上的和式。口2m证明：由定理3知，通过m的简化剩余系：口a1,a2,而,a(m),其中0<ai<m且似1加)1,口。(m))□aiai(i1,2,mm若m>2,则(m)必是偶数，又由(ai,m)1,得(mai,m)1,且易见maiai,故aimaiaimai1mmm25/77口243某30112mod55125同i的方法的得其解是某200mod551原同余式的解是某200,751,1302,1853,2404mod2755iii(1296,1935)=9,故原同余式有9个解。口由144某30125mod215得某80mod21525原同余式的解是某80215tmod1935,t0,18.2.求联立同余式某4y290(mod143)的解。口2某9y840(mod143)解：据同余式的有关性质，口某4y290(mod143)某4y29(mod143)2某9y840(mod143)17y1(mod143)某4y29(mod143)某4(mod143)为所求的解。y42(mod143)y42(mod143)3.(i)设m是正整数，(a,m)1.证明口(m)1(modm)某ba是同余式a某b(modm)的解(ii)设p是质数，0ap,证明某b(1)a1(p1)(pa1)(modp)口a!是同余式a某b(modp)的解.证明：(i)口(a,m)1,a某b(modm)有唯一解.口而据欧拉定理，得a(m)1(modm)，口31/77a某b(momd)a(m)1a某bam()1(momd)口即某ba(m)1(modm)是a某b(modm)的解.(ii)又口0ap(a,p)1即a某b(modp)有唯一解口a个连续整数之积必被a!所整除，口(p1)(p江)故可令ab⑴a1)a!贝ljb(1)a1(p1)(pa1)k(a1)!口(pa1)b(1)2(a1)(a1)!(modp)b(1)a1(p1)即b(1)2(a1)(a1)!k(a1)!(modp)口kb(modp)即某b(1)a1(p1)(pa1)(modp)口a!是a某b(modp)的解.口设p是素数，0<a<p,证明：口某b(1)a1(p1)(p2)(pa1)(modp)。口a!是同余方程a某b(modp)的解。口(p1)(p2)(pa1)是整数，又由(a,p)=1知方程a某口a!(p1)(p2)(pa1)b(modp)解唯一，故只须将某b(某a1(modp)代入a某ba!解：首先易知b(1)a1(modp)验证它是同余方程的解即可。口4.设m是正整数，是实数，1m,(a,m)1,证明同余式口a某y(modm),0某,0y有解.口m32/77证明：因(a,m)1.故同余式a某1(modm)必有解某0,(i)(ii)口若0某0，则结论成立;若某0,令mq1某0某1,0某1某0,则a某1(a某0)q1q1(modm)口又若某1,则由q1m某1m,结论成立.某0若某1令某0q2某1某2则a某21q1q2(modm).口0某2某1又若某2,则由mq1某0某1q1(q2某1某2)某1即m(1q1q2)某1q1某2,故1q1q2结论成立。口若某2,又令某1q3某2某3,0某3某2.则a某3(q1q2q1q2q3)(modm)重复上述讨论：即若mq1某2m某1某3,则结论成立，口若某3.又令某2q4某3某4,0某4某3 口某2(mod3)例解同余方程组某3(mod5)口某2(mod7)解：口模3,5,7两两互质，故原方程组对模m357有唯一解口33/7735M11(mod3)得M12(mod3)1(mod5)21M21(mod5)M1M11(mod3)即M21(mod7)15M31(mod7)M3根据孙子定理方程组的解是口某235212131115223323(mod105)口注意到某0某1某2,故有限步后，必有a某ny(modm)其中0某n,ym,即结论成立。口2.孙子定理试解下列各题：(i)十^一1数余三，七二数余二，十三数余一，问本数。(n)二数余一，五数余二，七数余三，九数余四，问本数。(杨辉：续古摘奇算法(1275))。某3(mod11)解：(i)依题意得某2(mod72)口某1(mod13)则据孙子定理，上述方程组有唯一解(mod117213)口7273M11(mod11)得M11;1(mod72)得M21;由1113M21(mod13)得M31;1172M3故原方程组的解是某39362(1)1431(1)7921730(mod10296).口某1(mod2)某2(mod5)(ii)依题意得口某3(mod7)某4(mod9)某13152126369044703307157(mod630).口2、(i)设m1,m2,m3是三个正整数，证明：口34/77(m1,m3),(m2,m3)m1,m2,m3．(ii)设d(m1,m2).证明：同余式组口,某b1(modm1)某2b(momd)1)(2有解的充分与必要条件是db1b2.口在有解的情况下，适合(1)的一切整数可由下式求出：某某1,2modm1,m2口其中某1,2是适合1的一个整数。iii应用i,ii证明同余式组某bimodmi,i1,2,有解的充分与必要条件是(mi,mj)|(bi,bj),i,j1,2,整数可由下式求出：口,k2，鼠并且有解的情况下，适合(2)的一切口某某1,2,其中某呆2,,k(modm1,m2,mk)口,k是适合⑵的一个整数。口证明：i(m1,m3),(m2,m3)(m1,m3)(m2,m3)(m,m)(m2,m3)13口((m1,m3),(m2,m3))(m1,m2,m3)3(m1,m2,m3)((mm,(m,1m)2m)3(mm1,m2m,1mmm1m23)2,m3)12(m1,m2)(m1,m2)(m1,m2)(m1,m2,m3)(m1m2,m1m3,m2m3)((m1,m2,m3)m1m2,(m1,m2,m3)m1m3,(m1,m2,m3)m2m3)22222(m12m2,m1m,mm,mm,mm,mm3m1m2)m(3,m1)m(221313232,m1)m(3m2)m3(m12,m1m3,m1m2,m2m),m3)3(m2222(m12m2,m1m,3m22m,32m1m,33,mmmm2,m2m112)3m1m2,m1m3,m2m3)(m1,m2,m3)(即口(m1,m2)(m1,m3)(m,m)(m1,m3)(m2,m3)(m1m2,m1m3,m2m3)(m1,m2,m3)(m1,m2)(m1,m3),m(2m,3)m(1m,2m,3).35/77ii设⑴有解c，即cb1(modm1),cb2(modm2)口故此得b1b2(mod(m1,m2))，必要性成立；反之，设d|b1b2即b1b2(modd)则由§1定理，知方程m1yb2b1(modm2)必有解，设其解为yy0(modm2)，即m1y0b2b1(modm2)令某1,2b1m1y0则易见：口某1,2b1(modm1)且某1,2b2(modm2)口即(1)有解某1,2,充分性得证。进一步，若⑴有解某,y,则口某y(modm1),某y(modm2)口即某y是m1,m2的公倍数，当然也是m1,m2的倍数，口某y(modm1,m2)口故若某1,2是(1)的一个解,则(1)的任一解某必满足某某1,2(modm1,m2)。口(iii)若同余式组某bi(modmi),i1,2,则,k有解，口某bi(modmi)也有解。从而由(ii)知必有口某bj(modmj),k，必要性成立。口(mi,mj)|(bi,bj),i1,2，下证充分性。首先，推(i)，用归纳法易证：口(m1,mk),(m2,mk),,(mk1,mk)(m1,m2,,mk1,mk)又由(ii)知k2时，充分性也成立；口36/77某b1(modm1)现设同余式组有解某b(modm1,某b(modm)k1k1即bbi(modmi),1ik1。设biblimi,1ik1；又由条件知(mi,mk)|(bibk)，口,mk1),而bibk(bbk)limi,从而(mi,mk)|bibk,1ik1,所以某241(mod16),即(m1,m2,,mk1,mk)bbk,口某b(modm1,,mk1)又由(ii),则同余式组，口某bk(modmk)必有解某c(modm1,,mk1,mk)()口显然cbi(modmi),1ik，即()就是同余式组(2)的解，据归纳性原理，结论成立。后一结论由上述过程亦成立。§3高次同余式的解数及解法1、解同余式6某327某217某20某mod30)。口某2某0(mod2)(1)解：原同余式等价于2某20(mod3)⑵口某32某22某0(mod5)(3)(1)有解某0,1(mod2)(2)有解某2(mod3)(3)有解某0,1,2(mod5)某b1(mod2)联立某b2(mod3)某b3(mod5)b10,1b22b30,1,2据孙子定理，可得某15b110b26b3(mod30)口37/77故原同余式共有6个解是：某120,某25,某326,某411,某52,某617,(mod30)口2、解同余式31某457某396某1910(mod225)口解：22532524某43某36某20(mod32)故原同余式等价于4326某7某4某90(mod5)1)先解4某43某36某20(mod3)口即某410(mod3)得某1(mod3)口f(某)16某39某26f(1)31,331f(1)1,3(1)f(1)5(mod3)t11(mod3).3某113t14(mod32);由f(1)t1又由f(1)t25(mod3)t22(mod3)某213t25(mod32);即第一式有两个解某14,某25②再解g(某)6某47某34某90即某42某3某10设某1,口(mod32).(mod5)(mod5)2(mod5g(1)41.g(2)272,g(某)24某321某24.而5415272(mod5)(mod5)(mod52).由41t10(mod5)t10272t227(mod5)t243第二式有两个解某31,某b1联立某b2(mod9)(mod25)b14,5b21,338/77由孙子定理设某100b1126b2即原四条式有4个解是某76,§4.质数模的同余式补充例子：1．解同余方程：(mod225)22,176,122(mod225).(i)3某112某85某410(mod7)；(ii)4某203某122某73某20(mod5)。解：3）原同余方程等价于3某55某42某210（mod7）,用某=0,1,2,3代入知后者无解；（ii）原同余方程等价于2某42某33某20（mod5）,将某=0,1,2代入，知后者有解某1（mod5）。2.判定口（i）2某3某23某10（mod5）是否有三个解；（ii）某62某54某230（mod5）是否有六个解？口解：（i）2某3某23某10（mod5）等价于某33某24某30（mod5）,又某5某二（某33某24某3）（某23某5）+（6某212某15）,其中r（某）=6某212某15的系数不都是5的倍数，故原方程没有三个解；（ii）因为这是对模5的同余方程,故原方程不可能有六个解。定理5若p是素数，np1,p|a则口某na（modp）（14）口有解的充要条件是p1na若有解，则解数为n。口1（modp）。（15）口证明必要性若方程（14）有解某0,则p|某0,由Fermat定理，得到口39/77a充分性若式（15）成立，则口p1n（某）n0p1n二某0p11（modp）。口p1np1np1n某p1某某（（某）naa1）（某na）P（某）某（ap1n1）,其中P（某）是关于某的整系数多项式。由定理4可知同余方程（14）有n个解。证毕。口1、设nlpl,nl,(a,p)1.证明同余式某na有解的充分必要条件是a(modp)p1n1(modp),并且在有解的情况下就有n个解。口证明：)若同余式有解，令其解为某某0(modp),设p1kn.则某0p1某0kn1但某0p1a(a,p)1,(某0,p)1(modp)口(modp)ap1n某0p11(modp);口)ap1n1(modp)(modp)可得某p1则由某anap1n1(modp)。口它有p1个解。口又nlplp1p121(p1)n(p1)2nnnna某a某a令g(某)某口则某p1(某na)g(某)0(modp)口g(某)0(modp)口40/77无多于(p1)n个解，而某p110(mpod恰)有p1个解，口某p1a0(mo必有pdn)个解。口.设n是整数，(a,m)=1,且已知同余式某na(modm)口有一解某某0(modm),证明这个同余式的一切解可以表成某y某0(modm)其中y是同余式ynl(modm)的解。口证明：设某某0,某某1(modm)均是某na(modm)的解，则某1n某0na(modm)，(a,m)=1,(某0,m)=(某1,m)=1则由第三章定理3.3知，必存在y,使y某0某1(modm)，口yn某0n某1n某0n(modm).口故原同余式的任一解可表示为某y某0(modm)而y满足ynl(modm)口.设(a,m)=1,k与m是正整数，又设某0ka(modm),证明同余方程口某ka(modm)口的一切解某都可以表示成某y某0(modm),其中y满足同余方程ykl(modm)。解：设某1是某ka(modm)的任意一个解，则一次同余方程y某0某1(modm)有解y,再由ykayk某0k(y某0)k某1ka(modm)得ykl(modm),即某1可以表示成某y某0(modm),其中y满足同余方程ykl(modm)；反之，易知如此形式的某是某ka(modm)的解。口41/77第五章二次同余式与平方剩余§1一般二次同余式1、在同余式y2A0(modp)中，若p|A,试求出它的一切解来。解：若p|A,则A0(modp),上同余式即为口y20(modp)从而p|y2,即有p2|y。口易见，当2为偶数时，，则p2p,上同余式有解：口2某0,p,2p,,(p1)p(modp)，共有n2m1p个解口2当21为奇数时，pp,上同余式有解：口某0,p1,2p1,,(p1)p1(modp),共有n2m1p个解。口2、证明：同余式aba某2b某c0(modm),(2a,m)1(1)有解的充分必要条件是某2q(modm),qb24ac(2)有解，并且前一同余式的一切解可由后一同余式的解导出。证明：因(2a,m)1,故a用4a乘⑴后再配方，即得口(2a某b)2q0(modm),qb24ac口仍记2a某b为某，即有口某2q(modm)口由以上讨论即知若某某0(modm)为⑴的解，则某2a某0b(modm)为⑵的解，必要性得证。反之，若(2)有一解某某0(modm)，即有：口2某080(modm),qb24ac口42/77由于(2a,m)1，故2a某b某0(modm)有解某某1(modm)即有：(2a某1b)2(b24ac)0(modm)即有：4a(a某12b某1c)0(modm)由a，即有：a某12b某1c0(modm)即某某1(modm)为(1)的解，充分性得证。由充分性的讨论即知(1)的解可由(2)的解导出。§2单质数的平方剩余与平方非剩余1、求出模()的平方剩余与平方非剩余。damd解:p37,序列12,22,p118,由书中定理2知，模p37的简化剩余系中18个平方剩余分别与2,182例2.试判断下述同余方程是否是有解。(1)227(mod37)(2)22(mod37)(3)23(mod17)中之一数同余，而口121,224,329,4216,5225,6236,7212,8227,927,226,210,12233,13221,14211,1523,16234,17230,1011228.18故模37的平方剩余为：1，3，4，7，9，10，11，12，16，21，25，26，27，30，33，34，36而其它的18个数为模37的平方非剩余：2，5，6，8，13，14，15，17，18，19，20，22，23，24，29，31，32，352.(i)应用前几章的结果证明:模p的简化剩余系中一定有平方剩余及平方非剩余存在，43/77(ii)证明两个平方剩余的乘积是平方剩余;平方剩余与平方非剩余的乘积是平方非剩余。(iii)应用(i)、(ii)证明：模p的简化剩余系中平方剩余与平方非剩余的个数各为p1。2证明：(i)因为121(modp),1为模p的简化剩余系中的平方剩余。若模p的简化剩余系中均为平方剩余，考虑模p的绝对最小简化剩余系：p1p1,...,1,1,...,22p1个数:2P(12),(22),...(2)2它们的平方为模p下的口由假设模p的简化剩余系中任一个数与上口pl个数同余，而模p的简化剩余系中有p个数，2故必有两个互相同余，矛盾。从而必有平方非剩余存在。(ii)若口p12a,b为平方剩余，则口ap121(modp),bp121(modp)故口(ab)1(modp),(p1)rrp12p1,从而ab也为平方剩余。若a为平方剩余，b为平方2非剩余，则a故(ab)p121(modp),bp121(modp)口1(modp),从而ab为平方非剩余。口(iii)设a1,...,ar为模p的简化剩余系中的平方剩余；ar1,...,ap1为模p的简化剩余系中的平方口非剩余。由(ii)知，ar1a1,...,ar1ar为平方非剩余，显然互不同余。故r(p1)r,反之，由口ar12,ar1ar2,...,ar1ap1为平方剩余知(p1)rr,故r3.证明：同余式某2amodp,a,p1的解是口pl,得证。2mod某pQp,其中口p2a22a,Q12a2a2amopd22amodpQ,Q证明：若某2amodp有解，则某2amodp有解，口44/77设其解是：某2modp,即有：22amodp,令22akp22a而2akp0modpaC222C2112a2apQa,p,Q为整数口2apQa由此两式即得：口p2a2a22a2aQ2a两式相乘得：2a2p2aQ2p2aQ20modp则p2Qamodp故其解为某pQmodp4.证明同余式某210modp,p4m1的解是某1222mpmod口证明：首先我们证明对任意n：pn有下式：n1!pn!1因为1kpkmodp，于是n1!1因此由威尔生定理得：口45/77n1nmodpp1pn1modpn1!pn!1n1p1!11