初等数论 第三版 (闵嗣鹤 著) 高等教育出版社 课后答案 初等数论 课后答案 32页

'课后答案网，用心为你服务！大学答案---中学答案---考研答案---考试答案最全最多的课后习题参考答案，尽在课后答案网（www.khdaw.com）！Khdaw团队一直秉承用心为大家服务的宗旨，以关注学生的学习生活为出发点，旨在为广大学生朋友的自主学习提供一个分享和交流的平台。爱校园（www.aixiaoyuan.com）课后答案网（www.khdaw.com）淘答案（www.taodaan.com） 附录1习题参考答案第一章习题一1.(ⅰ)由ab知b=aq，于是b=(a)(q)，b=a(q)及b=(a)q，即ab，ab及ab。反之，由ab，ab及ab也可得ab；(ⅱ)由ab，bc知b=aq1，c=bq2，于是c=a(q1q2)，即ac；(ⅲ)由bai知ai=bqi，于是a1x1a2x2akxk=b(q1x1q2x2qkxk)，即ba1x1a2x2akxk；(ⅳ)由ba知a=bq，于是ac=bcq，即bcac；(ⅴ)由ba知a=bq，于是|a|=|b||q|，再由a0得|q|1，从而|a||b|，后半结论由前半结论可得。2.由恒等式mqnp=(mnpq)(mp)(nq)及条件mpmnpq可知mpmqnp。3.在给定的连续39个自然数的前20个数中，存在两个自然数，它们的个位数字是0，其中必有一个的十位数字不是9，记这个数为a，它的数字和为s，则a,a1,,a9,a19的数字和为s,s1,,s9,s10，其中必有一个能被11整除。4.设不然，n331=n2n3，n2p，n3p，于是n=pn2n3p，即pn，矛盾。5.存在无穷多个正整数k，使得2k1是合数，对于这样的k，(k1)2不能表示为a2p的形式，事实上，若(k1)2=a2p，则(k1a)(k1a)=p，得k1a=1，k1a=p，即p=2k1，此与p为素数矛盾。第一章习题二1.验证当n=0,1，2，…,11时，12|f(n)。2b2=3Qr222.写a=3q1r1，b=3q2r2，r1,r2=0,1或2，由3a1r2知r1=r2=0，即3a且3b。3.记n=10q+r,(r=0,1,…,9)，则nk+4-nk被10除的余数和rk+4-rk=rk(r4-1)被10除的余数相同。对r=0,1,…,9进行验证即可。4.对于任何整数n，m，等式n2(n1)2=m22的左边被4除的余数为1，202 而右边被4除的余数为2或3，故它不可能成立。5因a43a29=(a23a3)(a23a3)，当a=1，2时，a23a3=1，a43a29=a23a3=7，13，a43a29是素数；当a3时，a23a3>1，a23a3>1，a43a29是合数。6.设给定的n个整数为a1,a2,,an，作s1=a1，s2=a1a2，，sn=a1a2an，如果si中有一个被n整除，则结论已真，否则存在si，sj，i0，则|b|m，故有[a,b]=|b|。2.设m是a1,a2,,an的任一个公倍数，由a1m，a2m知[a1,a2]=m2m，由m2m，a3m知[m2,a3]=m3m，，由mn1m，anm知[mn1,an]=mnm，即[a1,a2,,an]m。abb(ab)3.只须证(ab)a，即只须证(b,ab)=(a,b)，此式显然。(a,b)(b,ab)4.由ab=120及ab=(a,b)[a,b]=24144=3456解得a=48，b=72或a=72，b=48。2222222abcabc5.因为[a,b,c]，[a,b][b,c][c,a]，故只须证2(ab,bc,ca)(a,b)(b,c)(c,a)明(a,b,c)(ab,bc,ca)=(a,b)(b,c)(c,a)，此式用类似于例3的方法即可得证。6.设s=1k2k9kk9k)(2k8k)(9k1k)=10q，则由2s=(11k9k)(1k8k)(9k0k)=9q及2s=(02得102s和92s，于是有902s，从而129=45s。第一章习题五1.(ⅰ)ab知b=ab1，由性质(ma,mb)=|m|(a,b)得(a,b)=(a,ab1)=a(1,b1)=a；(ⅱ)由性质(ma,mb)=|m|(a,b)得(a,b)=(2a1,2b1)=2(2a1,b1)；(ⅲ)b由性质(a,b)=1(a,bc)=(a,c)得(a,b)=(a,21)=(a,b1)；(ⅳ)由性质(a,b)ab=(|ab|,b)及(a,b)=1(a,bc)=(a,c)得(a,b)=(||,b)。22.作辗转相除：1387=(162)(8)91，162=91(2)20，91=20411，20=1119，11=912，9=241，2=120，由此得n=6，q1=8，q2=2，n1Qnq3=4，q4=1，q5=1，q6=4，x=(1)n=73，y=(1)Pn=625，又(1387,162)=rn=1，故138773162625=1=(1387,162)。3.(27090,21672,11352)=(4386,10320,11352)=(4386,1548,2580)=(1290,1548,1032)=(258,516,1032)=(258,0,0)=258。4.(Fn+1,Fn)=(FnFn1,Fn)=(Fn1,Fn)==(F1,F2)=1。204 5.设除数为d，余数为r，则由d45822836=1746，d51644582=582，d65225164=1358知d(1746,582,1358)=194，由此得d=97，r=23或d=194，r=120。6.作辗转相除：a=bq1r1，01，A是奇数，且A是6n5型的整数，故A必存在一个6n5型的素因数p，从而p=pi（1ik），由pA，pp1p2pk推出p1，矛盾。4.设p1，p2=dp1，p3=2dp1，首先p12且d是偶数，于是3|d，从而对任意给定的d，p1，p2，p3中有且只有一个被3整除，即p1，p2，p3有且只有一个等于3，故p1，p2，p3最多只有一组。5.显然下面n个正整数(n1)!2，(n1)!2，，(n1)!(n1)满足要求。116.设不然，则存在k，使得，设Q=p1p2pk，考虑1nQ，nN，nk1pn2显然它们都不能被p1,p2,,pk整除，即1nQ的标准分解式中的素数都只能在pk+1,pk+2,中，从而对于任意的r1，有r11n1n()()，n11nQnn11mk1pm211右边是一个收敛的级数，故由比较判别法知也收敛，但事实上n11nQn11nQ是一个发散级数，矛盾。第二章习题一1.定理1的证明：如果(ⅰ)成立，mab，ab=mq，a=bmq，知(ⅱ)成立；如果(ⅱ)成立，写a=q1mr1,b=q2mr2，0r1,r2m1，则q1mr1=q2mr2mq，由此得r1=r2，知(ⅲ)成立；如果(ⅲ)成立，a=q1mr,b=q2mr，0rm1，则ab=m(q1q2)，mab，知(ⅰ)成立。定理2的证明：结论207 (ⅰ)与(ⅱ)显然。(ⅲ)由定理1及ab，bc(modm)可知存在整数q1，q2，使得a=bq1m，b=cq2m，因此a=c(q1q2)m，推出ac(modm)。定理2得证。2.由xy(modm)得xiyi(modm)，由aiiibi(modm)得aixbiy(modm)，nnii再由可加性得aixbiy(modm)。i0i03.(ⅰ)由ab(modm)得mab，又dm，故dab，即ab(modd)；(ⅱ)由ab(modm)得mab，故kmkakb，即akbk(modmk)；(ⅲ)由ab(modmi)得miab，故[m1,m2,,mk]ab，即ab(mod[m1,m2,,mk])；(ⅳ)由ab(modm)得a=mqb，故(a,m)=(b,m)；(ⅴ)由acbc(modm)得macbc=c(ab)，又(c,m)=1，故mab，即ab(modm)。4.因为821(mod13)，所以81234=(82)617(1)617112(mod13)，即81234被13除的余数是12。5.对任意的整数x，xr(modm)，1rm，于是f(x)f(r)0(modm)，从而f(x)0，所以方程f(x)=0没有整数解。6.由99|62427得9|62427，11|62427。从9|62427得=6或=15，从11|62427得=2或=9，于是解关于，的方程组661515或或或2929得=2，=4。第二章习题二1.若A是模m的完全剩余系，显然(ⅰ)与(ⅱ)成立。反之，满足(ⅰ)与(ⅱ)的一组数必分别来自于模m的每一个不同的剩余类，即A是模m的完全剩余系。2.由威尔逊定理知1(2p)!=p!(p1)(2p)(1)p(p!)2(mod2p1)，由此得(p!)2(1)p0(mod2p1)。3.由(p1)!p1(modp)，(p1)!p1(modp1)以及(p,p1)=1得(p1)!p1(modp(p1))，又2N=p(p1)，故(p1)!p1(modN)。4.设不然，n=n1n2，112（1）；当2n=p，p为奇素数时，(p)=pp1>p（1）；现在设n2p1pk，1k则(n)(2)(p1)(pk)12p1pk1n。(ⅱ)设n是合数，1k1k22p0为n的最小素因数，则p0n，于是111(n)=n(1)n(1)n(1)nn。p|npp0n第二章习题四1.因103=2353，显然1978103197830(mod23)，再由19781001(mod53)得1978103197830(mod53)，故1978103197830(mod103)。2.313159=5159=(56)265353=255456(mod7)。3.因561=31117，对于一切整数a，(a,561)=1，有(a,3)=1，(a,11)=1，(a,17)=1，由费马定理可得a560=(a2)2801(mod3)，a560=(a10)561(mod11)，a560=(a16)351(mod17)，故a5601(mod561)。4.由费马定理qp11(modp)，pq11(modq)，pq1qp11(modp)，pq1qp11(modq)，故pq1qp11(modpq)。5.6121=(631)(631)(661)=54373146657，对于46657，它的素因数必为12k1型，经检验的46657=133797，故6121=571331374397。6.设素数pbn1，即bn1(modp)，于是b2n1(modp)，由例5得下面两种情形之一成立：(ⅰ)pbd1对于2n的某个因数d<2n成立；(ⅱ)p1(mod2n)。第二章习题五1.设12k12k（0np1p2pk，则n正因数可表示为d=p1p2pkii，210 k1ik），于是d(n)=11=(11)(12)(1k)。由上式立知d(n)d|ni10ii是积性函数，但d(4)=34=d(2)d(2)，故d(n)不是完全积性函数。2.若不恒为零的数论函数f(n)是完全积性函数，必为积性函数，故f(1)=1且f(p1p2pk)f(p)1f(p)2f(p)k。反之，若整数m，n中有一个等12k12k于1，显然有f(mn)=f(m)f(n)，若mp1pk，np1pk，则1k1kf(mn)f(p11pkk)1kf(p)11f(p)kkf(p)1f(p)kf(p)1f(p)k1k1k1kf(m)f(m)。11n1(n)3.d。d|ndnd|ndnd|nn4.(ⅰ)当n=1时，右边的连乘理解为1，等式成立。设np1pk，1k则有(d)f(d)(1(p)f(p)(pi)f(pi))(1f(p))；(ⅱ)iiiiid|npi|npi|n当n=1时，右边的连乘理解为1，等式成立。设np1pk，则有1k2(d)f(d)(12(p)f(p)2(pi)f(pi))(1f(p))。iiiiid|npi|npi|n5.当n=1时，(d)=1，设np1pk，则1kd|n(d)(d1)(dk)d|nd|p1d|pk11k1k[1(p1)(p1p11)][1(p1)(pkpk1)]111kkkp1pkn。1k第三章习题一1.对于任意的正实数，写=[]{}，则由定理1，定理2可知[]与{}kiii可分别唯一地表示为aib与aib形式，故可以唯一的表示为=aib（0aii0i1i1b1，且对于任何正整数m，都存在n>m，使得an1，又易知a1,a2,,an还可以另写成简单连分数a1,aa2,,an1,1，但仅此而已，故有理数仅有此两种表示成简单连分数的方法。b213 2.13=3,1,1,1,1,6,1,1,1,1,6,1,1,。3.经计算23=3,1,2,1,2,，由此得p1=3，p2=4，p3=11，p4=15，p5=41，p6=56，p7=153，p8=209，p9=571，p10=780，p11=2131，，q1=1，q2=1，q3=3，q4=4，q5=11，q6=15，q7=41，q8=56，q9=153，q10=209，78011780q11=571，，于是|23|，故即为所求。520920957110209514.sin18==0,3,4,4,4,4,，得p1=0，p2=1，p3=4，p4=17，4p5=72，p6=305，q1=1，q2=3，q3=13，q4=55，q5=233，q6=987，于是721172|sin18|，故即为所求。5233233987102333223333551039931043085.的前几个渐近分数为，，，，，，，其117106113331023321535510993中和分别满足误差满足106和109的要求。11333102156.=1,1,1,1,1,，由此易得pk=pk1pk2=FkFk1=Fk+1，2pkFk1qk=qk1qk2=Fk1Fk2=Fk，故。qkFk第三章习题四711.方程3x22x2=0的正根=0,1,1,4,1,1,1,4,1,1,1,4,。311512.=1,2,3=1，解得x。122222113.a1a(a1a)aa==22a1a2a(a1a)a,2a,2a,2a,2a,。4.若da1,a2,,an,2a1，则214 (a1d)pnpn1da1,a2,,an,2a1a1,a2,,an,a1d，(a1d)qnqn1得(dqna1pnpn1)(a1pnpn1pn)d0，由d是无理数得pn=a1qnqn1，dqn=a1pnpn1，反之，若pn=a1qnqn1，dqn=a1pnpn1，则(a1)pnpn1=a1,a2,,an,2a1a1,a2,,an,a1，(a1)qnqn12(a2得满足方程qn1qnqn1pn)(a1pnpn1)=0，即=d，=d。5.由第4题可得到。第四章习题一17xyz1.设，即35x21y15z=17，因(35,21)=7，(7,15)=1，105357117，故有解。分别解5x3y=t，7t15z=17得x=t3u，y=2t5u，uZ，t=1115v，z=47v，vZ，消去t得x=1115v3u，y=2230v5u，z=47v，u，vZ。对于任意的确定的u和v的值，都给出一种表示法。2.分别解x12x2=t，t3x3=41得x1=t2u，x2=u，uZ，t=413v，x3=v，vZ，消去t得x1=413v2u，x2=u，x3=v，u，vZ。由此得原方程的全部正整数解为(x1,x2,x3)=(413v2u,u,v)，u>0，v>0，413v2u>0。3.消去x1得9x214x3=3，解得x2=914t，x3=69t，tZ，从而得不定方程组的解为x1=4355t，x2=914t，x3=69t，tZ，4.设甲、乙班的学生每人分别得x，y支铅笔，则7x11y=100，解这个不定方程得x=8，y=4。xx0bt5.二元一次不定方程axby=n的一切整数解为，tZ，于是yy0aty0x0y0x0n由x0，y0得t，但区间[,]的长度是，故此区间内的整abababnn数个数为[]或[]1。abab6.因为0,1,2,,abab中共有(a1)(b1)个数，故只须证明n与gn（g=abab）有且只有一个能表示成axby（x0，y0）的形式。如果n与gn都能表示成axby（x0，y0）的形式，即axby=n（x0，y0），axby=gn（x0，y0），则a(xx)b(yy)=g，这是不可能的；如果n不能表示成axby（x0，y0）的形式，则因为二元一次不定方程axby=n215 xx0bt的一切整数解为，tZ，所以当t使0xb1时，必有y1，于yy0at是a(b1x)b(1y)=gn，即gn能表示成axby（x0，y0）的形式。第四章习题二ln1.设有理数x，y（m0）满足方程x2y2=1，即l2n2=m2，mm于是得l=2abd，n=(a2b2)d，m=(a2b2)d或l=(a2b2)d，m=2abd，m22222ababab2ab=(a2b2)d，由此得(x,y)=(,)或(,)。反之，22222222abababab代入方程x2y2=1即知这样的点在单位圆周上。2.由x2=(zy)(zy)及x是素数得zy=x2，zy=1，于是2z1=x2，2(xy1)=(x1)2都是平方数。3.设xy=a2，yz=b2，xz=c2，则a2b2=c2，由此得x=(u2v2)2t，y=(u2v2)2t或4u2v2t，z=t，u,v,tZ。4.设(zx,zx)=d，易知d=1或2。由(zx)(zx)=3y2得zx=3da2，zx=db2，y=dab或zx=db2，zx=3da2，y=dab，a>0，b>0，(a,b)=1。2222|b3a|b3a(ⅰ)当d=1：x，，yab，za>0，b>0，(a,b)=1，223|b，a,b同为奇数；(ⅱ)当d=2：x=|b23a2|，y=2ab，z=b23a2，a>0，b>0，(a,b)=1，3|b，a,b一奇一偶。反之，易验证(ⅰ)或(ⅱ)是原不定方程的解，且x>0，y>0，z>0，(x,y)=1。5.(ⅰ)设x，y，z是x2y2z2=x2y2的整数解，如果x，y同为奇数，则x2y2z22，3(mod4)，x2y21(mod4)，此不可能；如果x，y一奇一偶，则x2y2z21，2(mod4)，x2y20(mod4)，此也不可能。所以x，y同为偶数，z也是偶数，令x=2x2222221，y=2y1，z=2z1，代入原方程得x1y1z1=2x1y1，反复以上的推理可得x，y，z能被2的任意次乘幂整除，只能x=y=z=0。(ⅱ)类似于(ⅰ)可证。6.设x，y，z是x2y2=z4的满足(x,y)=1，2x的正整数解，则x=2ab，y=a2b2，z2=a2b2，a>b>0，(a,b)=1，a,b一奇一偶，再由z2=a2b2得a=2uv，b=u2v2，z=u2v2或a=u2v2，b=2uv，z=u2v2，u>v>0，(u,v)=1，u,v一奇一偶，于是得x=4uv(u2v2)，y=|u4v46u2v2|，z=u2v2，u>v>0，(u,v)=1，u,v一奇一偶。反之，易验证它是原不定方程的整数解，且x>0，y>0，z>0，(x,y)=1，2x。216 第四章习题三1.由x(xy)=6得(x,y)=(1,5)，(1,5)，(2,1)，(2,1)，(3,1)，(3,1)，(6,5)，(6,5)。2.由第一个方程得z=(xy)，代入第二个方程经化简得xyz=6，由此得(x,y,z)=(1,2,3)，(2,1,3)，(1,3,2)，(2,3,1)，(3,1,2)，(3,2,1)，3.当y=1时，x=2，若y2，x3，则3y1(mod8)，这是不可能的，故原方程的正整数解只有(x,y)=(2,1)。4.显然x>z，y>z，令x=zs，y=zt，s，tN，代入原方程可得z2=st，于是s=a2d，t=b2d，z=abd，其中a,b,dN，(a,b)=1，由此得x=abda2d，y=abdb2d，z=abd，反之，将上式代入原方程知它们是原方程的正整数解。5.不妨设xy，当p=2时，(x,y)=(2,2)。下设p是奇素数，令2x=ps，2y=pt，s，tZ，st，代入原方程可得p2=st，由此得s=1，t=p2或s=p，tp1p(p1)p(1p)p1=p或s=p2，t=1，即(x,y)=(,)(p,p)(,)。22226.设M，b为任意的有理数，容易证明：若a1,a2,,a2n+1具有性质P，则(ⅰ)M，Ma1,Ma2,,Ma2n+1也具有性质P；(ⅱ)a1b,a2b,,a2n+1b也具有性质P。由此我们可假定a1,a2,,a2n+1都是整数，且a1=0。由性质P易知aia1a2a2n1a1都是偶数，于是由(ⅰ)知,,,也具有性质P，并且它们都是整数，且=2222a1a2a2n10。反复以上推理可知对于任意的正整数k，,,,也具有性质P，故只kkk222可能a1=a1==a2n+1=0。第五章习题一1.(ⅰ)若f(x0)0(modm)，则f(x0)b(x0)b(x0)(modm)成立，反之，若f(x0)b(x0)b(x0)(modm)，则f(x0)0(modm)成立；(ⅱ)若f(x0)0(modm)，则bf(x0)0(modm)成立，反之，若bf(x0)0(modm)，则由(b,m)=1得f(x0)0(modm)成立；(ⅲ)若g(x0)h(x0)0(modm)，则由m是素数得g(x0)0(modm)或h(x0)0(modm)。2.(ⅰ)x4(mod17)；(ⅱ)x1，48，95，142，189(mod235)。3.消去y得8x41(mod47)，解得x11(mod47)，代入原方程组中的第二式得y1(mod47)。故原方程组的解为x11(mod47)，y1(mod47)。217 a1(p1)(p2)(pa1)4.首先易知b(1)是整数，又由(a,p)=1知方程a!a1(p1)(p2)(pa1)axb(modp)解唯一，故只须将xb(1)(modp)代入a!axb(modp)验证它是同余方程的解即可。5.必要性显然，下证充分性。当n=1时，由定理2知命题成立。假设n=k时结论已真，考虑a1x1a2x2akxkak+1xk+1b(modm)，令(a1,a2,,ak,m)=d1，(d1,ak+1)=d，因为同余方程ak+1xk+1b(modd1)有解，其解数为d，modd1，记m=d1m1，则解数为dm1，modm。现在固定一个解xk+1，由归纳假定知a1x1a2x2ak1kxkbak+1xk+1(modm)有解，其解数为d1m，modm，从而a1x1a2x2ak1kkxkak+1xk+1b(modm)有解，其解数为dm1d1m=dm，modm。由归纳原理知命题对于一切n1成立。6.因为(2,12)=2，(2,7)=15，故同余方程有解，其解数为11221=12，mod12。先解同余方程7y5(mod2)，得y1(mod2)，写成y12t(mod12)，t=0,1,2,,5，对于固定的t，解同余方程2x57(12t)22t(mod12)，得x1t(mod6)，写成x1t6s(mod12)，s=0,1，故原方程组的解为x1t6s(mod12)，y12t(mod12)，s=0,1，t=0,1,2,,5。第五章习题二1.m=56711=2310；M1=6711=462，M2=5711=385，M3=5611=330，M4=567=210；由462M11(mod5)得M1=3，385M21(mod6)得M2=1，330M31(mod7)得M3=1，210M41(mod5)得M4=1。所以原同余方程组的解为x3462b11385b21330b31210b4(mod2310)。2.因为(15,8)=185，(15,25)=5813，(8,25)=1513，故原同余方程组有解，解数唯一，mod[15,8,25]=600。将第一个同余方程的解x=815t1，t1Z，代入第二个同余方程得t13(mod8)，即t1=38t2，t2Z，x=53120t2，代入第三个同余方程得t23(mod5)，即t2=35t3，t3Z，x=413600t3，所以原同余方程组的解为x413(mod600)。注：此处所使用的解法思路简单，但比较繁。3.设士兵有x人，由题意得x1(mod3)，x2(mod5)，x3(mod11)，由孙子定理得x58(mod165)，故x=58人。4.可设n=235，由条件得1(mod2)，0(mod3)，0(mod5)；0(mod2)，1(mod3)，0(mod5)；218 0(mod2)，0(mod3)，1(mod5)，由孙子定理得15(mod30)，10(mod30)，6(mod30)，故n=21531056。5.作同余方程组：x0(modp1)，x1(modp2)，…，xn1(modpn)，由孙子定理知此同余方程组有解x，于是x，x1，…，xn1满足要求。6.因105=357，同余方程3x211x200(mod3)的解为x1(mod3)，同余方程3x211x380(mod5)的解为x0，3(mod5)，同余方程3x211x200(mod7)的解为x2，6(mod7)，故原同余方程有4解，mod105。作同余方程组：xb1(mod3)，xb2(mod5)，xb3(mod7)，其中b1=1，b2=0，3，b3=2，6，由孙子定理得原同余方程的解为x13，55，58，100(mod105)。第五章习题三1.(ⅰ)由定理知存在整数x22=apt1，t1Z，使得xx2(modp)是同余方2)的解，x2程f(x)0(modp2a(modp)。再由定理知存在整数x3=x2+pt2，t2Z，3)是同余方程f(x)0(modp3)的解，x使得xx3(modp3x2a(modp)，如此继1t续下去，最后知存在整数x=x1p1，t1Z，使得xx(modp)是同)的解，x余方程f(x)0(modpx1x2a(modp)；(ⅱ)由条件知同余方程f(x)0(modp)的每一个解xx1(modp)都不是f(x)0(modp)的解，即f(x1)0(modp)，于是由(ⅰ)知可导出f(x)0(modp)的解xx(modp)，且由(ⅰ)的证明过程知只能导出唯一的解xx)。(modp2.对x2(mod5)，令x=25t代入同余方程2x213x340(mod52)得t0(mod5)，于是x=25(5t231)=225t1，代入同余方程2x13x340(mod5)得到t0(mod5)，于是x=225(5t3)是同余方程2)=2125t2，即x2(mod52x213x340(mod53)的一个解。3.对x2220=4，则由(47x17x2)2(mod7)得x15(mod7)，x1=5。再由(47572x232)2(mod7)得x24(mod7)，x2=4，这样，求得原同余方程的一个解是x475724=235(mod73)4.因54=233，而x21(mod3)无解，故x21(mod54)也无解。5.因75=352，先解f(x)0(mod3)，用逐一代入法得解x0(mod3)；再解f(x)0(mod52)，用逐一代入法得f(x)0(mod5)的解为x0，2(mod5)，对于x0(mod5)，令x=5t代入f(x)0(mod25)得t2(mod5)，于是x=5(25t2)=1025t2，即x10(mod25)是f(x)0(mod25)的一个解，对于x2(mod5)，令x=25t代入f(x)0(mod25)得t4(mod5)，于是x=25(45t2)=2225t2，即x22(mod25)是f(x)0(mod25)的一个解；最后构造同余方程组xb1(mod3)，xb2(mod25)，b1=0，b2=10，22，由孙子定理得f(x)0(mod75)的两个解x10，72(mod75)。219 6.令m=p21p2pk，pi是不同的奇素数，由x1(modpi)的解数Ti=2，故T=Tkk1T2Tk=2，当k充分大时，必有2>n。第五章习题四1.(ⅰ)原同余方程等价于3x55x42x210(mod7)，用x=0，1，2，3代入知后者无解；(ⅱ)原同余方程等价于2x42x33x20(mod5)，将x=0，1，2代入，知后者有解x1(mod5)。2.(ⅰ)2x3x23x10(mod5)等价于x33x24x30(mod5)，又x5x=(x33x24x3)(x23x5)+(6x212x15)，其中r(x)=6x212x15的系数不都是5的倍数，故原方程没有三个解；(ⅱ)因为这是对模5的同余方程，故原方程不可能有六个解。3.设xk1是xa(modm)的任意一个解，则一次同余方程yx0x1(modm)有kaykxkkkk解y，再由y0(yx0)x1a(modm)得y1(modm)，即x1可以表示成xyxk1(modm)；反之，易知如此形式的x是0(modm)，其中y满足同余方程yxka(modm)的解。4.由kp1知同余方程xk1(modp)恰有k个解，又由kn知这k个解也是同余方程xn1(modp)的解。下证同余方程xn1(modp)的解必是同余方程xk1(modp)的解，事实上，若xn01(modp)，记k=snt(p1)。若s>0，t<0，kxkt(p1)kt(p1)snns则x00x0=x0=x0(x0)1(modp)；若s<0，t>0，则可类似证明。5.(ⅰ)xp110(modp)有解x1，2，，p1(modp)，故对于一切整数x，xp11(x1)(x2)(xp1)(modp)；(ⅱ)在(ⅰ)中令x=p。6.令(x1)(x2)(xp1)=xp1ap22p2xa2xa1xa0，其中p(p1)ap2=12(p1)=是p的倍数，考虑同余方程f(x)0(modp)，2f(x)=xp1ap32p3xa2xa1xa0，显然它有解x1，2，，p1(modp)，px=f(x)xr(x)中的余式r(x)=ap232故xp3xa2xa1x(a01)x的系数都是p的倍数。220 第五章习题五1311.因112116=121343121(mod13)，故x211(mod13)无解。2.模23的所有的二次剩余为x1,2,3,4,6,8,9,12,13,16,18(mod23)，二次非剩余为x5,7,10,11,14,15,17,19,20,21,22(mod23)。p1p1p13.设a，b为模p的二次剩余，有(ab)2a2b2111(modp)，再设p1p1p1c，d为模p的二次非剩余，有(cd)2c2d2(1)(1)1(modp)，以及p1p1p1(ac)2a2c21(1)1(modp)知结论成立。p1p14.由欧拉判别法知n21(modp)，两边乘n得(n4)2n(modp)，由此知p1x2n(modp)的解是xn4(modp)。n5.若x2n(modp)有解xx2=1，反0(modp)，则x0n(modp)，故()pn=1，则x2n(modp)有解xx2之，若()0(modp)，因p|2x0，故此解可导出xpn(modp)的一个解xx2(modp)，即xn(modp)有解。6.设x1,x2,,xk为模p的所有二次剩余，则p1p1x22p12221x2xk12()(1)(p1)!(1)(modp)。2第五章习题六17422044317141.(ⅰ)因()()()()()()()1，原同余方程有7697697697697693171503490254910133解；(ⅱ)()()()()()()()1，原同余1013101310131013101355方程有解。p111p2.由()1推出(1)2()1，由此得p11221 p1p1(1)21(1)21或，pp()1()11111即p1(mod4)p1(mod4)或，p1,3,4,5,9(mod11)p1,3,4,5,9(mod11)解之得p1，5，7，9，19(mod44)。233.由2QR(p)，3QR(p)推得()1，()1，即pp11()1()1pp22()1，或()1。pp33()1()1pp解之得p1，或11(mod24)。4.设奇素数px23y2，即x23y2(modp)，由(x,y)=1易证(3y2,p)=1，于23y3是()()1，由此得p的一般形式为12k1型。pp5.若8k5型的素数只有有限个，记为p21,p2,,pk，作A=(2p1p2pk)1，1显然A>1，A是奇数，设奇素数pA，即(2p21(modp)，1，1p2pk)()p由此得p的一般形式为8k1或8k5型，由A5(mod8)知A的素因数p中至少有一个是8k5型的，对这个p，有p=pi（1ik），由pA，pp1p2pk推出p1，矛盾。6.当p=4k1时，同余方程x21(modp)有解xn(modp)，即pn21，从而p(n21)(n22)(n22)；当p=8k3时，同余方程x22(modp)有解xn(modp)，即pn22，从而p(n21)(n22)(n22)；当p=8k7时，同余方程n22(modp)有解xn(modp)，即pn22，从而p(n21)(n22)(n22)。第五章习题七1.(ⅱ)显然；(ⅲ)设m=p1p2pk，则222 a1a2ata1a2ata1a2ata1a2at()()()()mp1p2pka1ata1ata1ata1a2at()()()()()()()()()。p1p1p2p2pkpkmmm2abaabb(ⅳ)()()()()()。mmmmm374218727312.因()()()(1)(1)()()()1，原同余方3019301930191871873程无解。d12d12d13.设d=2d1，d1为正奇数，()()()()()()，当>0时，pppppp2d1p1d2d1p=8n1型，()=1，当d1>1时，()()()=1，所以()()()=ppd1d1ppp1。4.由p=q4a知p，q同为4k1或同为4k3，当p，q同为4k1时，a4ap4aqpq4a4aa有()()()()()()()()，当p，q同为4kppppqqqqa4ap4aqpq4a4aa3时，有()()()()()()()()。ppppqqqq5.当a0(mod4)时，则2abb(mod8)，令a=2a1，a1为奇数，于是a2a12a1a1a1有()()()()()，若a11，()()，若2ab2ab2abb2ab2abba11b1a1ba1a2a1aa1>1，()(1)22()()，故得()()()()；当a2aba1b2abbbbaaaba1(mod4)时，若a=1，()()，若a1，()()()，故有2abb2ababaa()()；类似地，当a2(mod4)时，令a=2a1，a1为奇数，于是2abba2a12a12a1a()()()()()()()()；当a3(mod4)2ab2ab2abb2abbbb2ab12ab1时，(a)(1)2(2ab)(1)2(b)(1)a(a)(a)。2abaabba14acb1a1b1abba6.若a为奇数，有()(1)22()(1)22()()，若4acbaab223 22a为偶数，于是4acb与b同为8k1或同为8k3，即()()，设a=4acbba2a12a12a1，a1为奇数，有()()()()()=4acb4acb4acbb4acba114acb1a11b12b2b2a1a()(1)22()()(1)22()()()()。ba1ba1bbb第六章习题一1.设a，b，c是不定方程x2y2=z2的正整数解，则易知x=acn1，y=bcn1，z=c2是不定方程x2y2=zn的正整数解。2.对于每一个i，00，若k2，可得x，y，z都是偶数，于是2y22k2令x=2x1，y=2y1，z=2z1，代入得x11z1=2，若k22，类似于上面的的推理可得x21，y1，z1都是偶数，于是令x1=2x2，y1=2y2，z1=2z2，代入得x2y22k4222012z2=2，，最后推出，存在a，b，c>0，abc=2或2，显然这是不可能的。3.由n3n0(mod6)得n3n=6x，于是n=n3(x1)3(x1)3x3x3。4.若16k15=x44441x2x14，由x0或1(mod16)知上式不可能成立。5.若16k31=x44441x2x15，由x0或1(mod16)知x1,x2,,x15都是225 偶数，于是令x1=2x1,1，x2=2x2,1，，x15=2x15,1，代入得16k131=x4441,1x2,1x15,1，4x44反复以上推理，最后可得31=x1,k2,kx15,k，但易知31不能表示为15个四次方数的和，故16k31不能表示为15个四次方数的和。第七章习题一1.经计算得11(1)=1，11(2)=10，11(3)=5，11(4)=5，11(5)=5，11(6)=10，11(7)=10，11(8)=10，11(9)=5，11(10)=2，列表得a1234567891011(a)110555101010522.x3，5(mod14)是模14的全部原根。(m)3.因g1,g2,,g(m)构成模m的简化剩余系，由d=m(g)=得(,(m))(m)(m)(,(m))，令t，则dd(m)(,(m))=，1(m)(t,d)=1，1td，d故恰有(d)个t，使得(t,d)=1，从而知故恰有(d)个，使得)=d。特别地，m(g取d=(m)知模m的简化剩余系中恰有((m))个原根。4.(ⅰ)因g1,g2,,g(m)为模m的简化剩余系，设同余方程x21(modm)的解为xgr(modm)，即(gr)2=g2r1(modm)，由此得2r0(mod(m))，(m)(m)(m)2r，又由m3知(m)是偶数，得|r，r或(m)。另一方面，22同余方程x21(modm)至少有解x1，1(modm)，由g(m)1(modm)推出(m)g21(modm)。(ⅱ)因g1,g2,,g(m)也为模m的简化剩余系，故(m)((m)1)(m)(m)(m)(m)x1g2g(m)22221(modm)。1x2x(m)gggggp15.在模p的简化剩余系中有=2n1个二次非剩余，在模p的简化剩余2p1系中有((p))=(2n)=2n1个原根，又设g是模p原根，则g21(modm)，226 即g是模p的二次非剩余。6.(ⅰ)由2p1(modq)知q(2)p，于是q(2)=1或p，但易知q(2)1，故q(2)=p，再由q(2)(q)=q1知q1=pt，其中t必为偶数，故q为2pk12n2n1型；(ⅱ)由21(mod)21(mod)n+1，于是rq，即q知q(2)2q(2)=2，2n0rn1，又由r，0rn，故n+121(modq)知q(2)2q(2)=2，再由n+1q(2)(q)=q1知q1=2k，故q为2pk1型。第七章习题二1.因(29)=28=227，由(29)(29)21474221(mod29)，221(mod29)知2是模29的最小正原根。2.由2是模29的原根及2291=228=2281(mod292)知2是模293的原根；由2是模293的原根及2是偶数知2+293是模2293的原根。3.易得3是模17的原根，3i（i=0,1,2,,15）构成模17的简化剩余系，列表为i012345673i(mod17)139101351511i891011121314153i(mod17)16148741226816(mod17)，设x5y(mod17)，则12y8(mod16)，由此解得y由上表知312，y26，y310，y414(mod16)，查上表得x19，x215，x38，x42(mod17)。4.由4q(2)(q)=4p知q(2)=1，2，4，p，2p或4p，若21(modq)，则41=15=35，即q=3或5，这是不可能的，故q2q(2)1，q(2)2，q(2)4，q122p又q是8k+5型的数，2是q的二次非剩余，即221(modq)，故q(2)p，q(2)2p，所以q(2)=4p=(q)，2是模q的一个原根。5.存在一个，(,(m))=1，使得g+12g1(modm)，于是g1g2g1(modm)，又由m3知(m)是偶数，是奇数，1是偶数，(1,(m))1，故g=g1g2不是模m的原根。6.当p1n时，则1n2n(p1)np10(modp)，当p1|n时，设g是p的一个原根，则1n2n(p1)n(1g)n(2g)n[(p1)g]n[1n227 2n(p1)n]gn(modp)，得[1n2n(p1)n](1gn)0(modp)，由(1gn)0(modp)知1n2n(p1)n0(modp)。第八章习题一1.考虑函数nmnmnmi(x(ij))，(xij)与(x)。ji11ji11ji11j2.设是代数数，则bnn1nbn1b1b0=0，其中bi都是整数，bn1nn1n2n1n0，两边乘以bn得(bn)bn1(bn)bnb1(bn)bnb0=0，由此知bn是代数整数。3.有理数r是方程xr=0，若r是代数整数，则方程的系数r是整数，反之，若r是整数，则由定义知r是代数整数。第八章习题二111rn1.(ⅰ)令a，这里a=2，rn=n!，由2！n!222n1rn1(n1)!rlimlim知an是超越数。(ⅱ)类似于(ⅰ)即可得证。nrnnn!n1111pn2.令2!n!0,a1,a2,,an，是的第n个渐近101010qn分数，则pn111(n+1)!，由q||，这里an1=101511，取t=10<1，5E131055(mod8)，E231058(mod9)，E331059(mod11)，于是分配给三方的数据分别为E1=5，E2=8，E3=9。由E1，E2，E3中的任意两个都可以确定出M，例如，已知E2=8，E3=9，则由x8(mod9)，x9(mod11)可得解x53(mod911)，从而M=53105=3。第九章习题六1.因(a1,a2,a3,a4,a5,a6,a7,a8)超增背包向量，容易得到不定方程5p117p243p371p4144p5293p6626p71280p8=1999的01解为(p1,p2,p3,p4,p5,p6,p7,p8)=(1,1,0,1,0,0,1,1)，故密文E对应的明文P=(11010011)2=211。2.计算b177236(mod118)，取b1=36，b2773113(mod118)，取231 b2=113，b377767(mod118)，取b3=67，b4771357(mod118)，取b4=57，b57729109(mod118)，取b5=109，b6775959(mod118)，取b6=59，于是对外公开的加密向量是(36,113,67,57,109)，又P=51=(110011)2，故P对应的密文为E=36111316705701091591=317，若要从E=317得到明文P，则计算2331793(mod118)，解不定方程2p13p27p313p429p559p6=93的01解得(p1,p2,p3,p4,p5,p6)=(1,1,0,0,1,1)，故P=(110011)2=51。232'