初等数论 1 习题参考答案

附录1习题参考答案第一章习题一(ⅰ)由ab知b=于是b=(b=及 b(即ab及a 。反之，由 ab及 a b也可得a(ⅱ)由ab，bc知b=aq，c=bq，于是c=q)，1 2 12即a(ⅲ)由ba知a=bq，于是ax ax

ax=xi i i

11 2

kk 11qx qx)，即bax ax ax；(ⅳ)由ba知a=22 kk 11 22 kkacbcbaa=再由a 0得1，从而|a| 后半结论由前半结论可得。由恒等式mq np=(mn (m 及条件m ppq可知m pmq 。在给定的连续39个自然数的前20个数中，存在两个自然数，它们的位数字是0，其中必有一个的十位数字不是9，记这个数为它的数字和为则a 1, ,a 9,a 19的数字和为s 1, ,s 9,s10，其中必有一个能被11整除。

=nn

p，n

npn

，即p 3n，矛盾。

1 23 2 3 23存在无穷多个正整数，使得2k 1是合数，对于这样的，k 1)22

p的形式，事实上，若k

=2

则(k 1 k1 =得k 1 a=1，k 1 a=即p=2k 1，与p为素数矛盾。第一章习题二1.验证当n=0,1，2，…,11时，12|f(n)。2.写a

r，b=

r，r,

=0,13

2=1 1 2 2 1 23Q r2 r2rr=03a3。1 2 1 23.记=1=0,1,…,9)k+k被10k+kk-1)被10除的余数相同。对r=0,1,…,9进行验证即可。4.，

n

=

2的左边被4除的余数为1，而右边被4除的余数为2或3，故它不可能成立。5

2

9=

a 3)(

a=2 3a 3=1，4 32 9=2 3a 3=7，13，4 32 9是素数；当a 3时，2是合数。

a 3>，2

a 3>，4

2 96.设给定的n个整数为a,a, ,a，作1 2 ns=a，s=a a，，s=a a a，1 1 2 1 2 n 1 2 nsns，s，i<ssinns

i j i jsa a。j i i+1 j第一章习题三(ⅰ)因为da和d是等价的，所以a,a, ,a的公约数的1 2 k集合与|a|,|a|, ,|a|的公约数的集合相同，所以它们的最大公约数相等；1 2 k(ⅱ)，(ⅲ)显然；(ⅳ)设()=dp，ddpd=1d1p。(ⅰ)由da推出dy=(a,a, ,a)；(ⅱ)分别以y和Yi 0 1 2 k 0 0k kAy；y=ax，xZ，ii ii1

i k

={=max，iii1xZ， i k}中的最小正整数，显然有Yi

|m|y；(ⅲ)在推论20中取m= ，并

a a a1,2,,ka,a,

,a即可。 1 2 k3.p1，从而由

ab推出pb；(ⅱ)在(ⅰ)中取a=b可得；(ⅲ) (a,bbb)=bb)= =b)=1。12 n 2 n n4.由恒等式9(2x 2(9x =17y及17 2x 3y得172(9x又(17,2)=1，故17 9x 。5.设,)=，则a=da，b=db，(a,b)=，由2 c得a2 b2，1 1 1 1 1 1a2 ca=1，a=aba。1 1 16.设(1,C3,,C2n1)d，由1C3C2n122n1知d22n1，设2n 2n

2n 2n 2n2n2n2k12k+||12n

及2k1|Ci 2n

Ci1i 2n1

，i=3,5, ,2n1，得d=2k+1。第一章习题四1.(ⅰ)，(ⅱ)显然；(ⅲ)设m=[a,a, ,a]，m=[|a|,|a|,1 1 2 k 2 1 2|a|

m推出|a|m

mmmmm；(ⅳ)k i 1

I 1 2 1

1 2 1 2显然a|b|，b又若am，bm，m >则m，故有b]=|b|。设m是a,a, ,a的任一个公倍数由am知[a,a]=m1 2 n 1 2 1 2 2由m

m知[mam

m，，由m

m，a

m知[m

,a]=mm，2 3 2 3 3

n 1 n

n 1 n n即[a,a, ,a]。1 2 nab只须证(ab)

ab(ab)

，即只须证a =(a,b)，此式显然。

(a,b) (b,ab)4.由a b=120及ab==24 144=解得a=b=72或a=72，b=48。a2b2c2 a2b2c25.因为[a,b,c]2

(ab,bc,ca)2

，[a,b][b,c][c,a]

(a,b)(b,c)(c,a)

，故只须证明(36.设s=

2s

8k)

及2s1

0k)=9q2得10 2s和9于是有90从而1 2 9=45s。第一章习题五1.(ⅰ)abbabab)1 1a(1,b(2a,2b)1 1 1=2(2 a,b)；(ⅲ)由性质=1 =c)得(a,b)=1 1(a,2b)=b)；(ⅳ)由性质=及=11 1(a,bc)=(a,c)得(a,b)=(|ab|,b)。22.作辗转相除：1387=(162)(8) 91，162=91(2) 20，91=204 =111 =91 =24 =12n=1

= 8，q2

= 2，q3

=4，q4

=1，q5

=1，q6

=4，x=(1)nQn

==(1)nPn

=625，又(1387,162)=rn

=1，故138773162625=1=(1387,162)。3. (27090,21672,11352)=(4386,10320,11352)=(4386,1548,2580)=(1290,1548,1032)=(258,516,1032)=(258,0,0)=258。

,F)=

F ,F)=

,F)= =(F,F)=1。n+1

n n 1

n 1 n 1 2d4582 2836=1746，d5164 4582=582，d6522 5164=1358d(1746,582,1358)=d==23d==作辗转相除：a=bq

r， 0<

<|b|，1b=rq

1 r，0<r

<r，12 2 2 1r =r q r，0<r<r ，n 2 n 1r =rq

n r ，r

n 1=。由第一式得

n 1 nn 1

n 1 n 12a 1=2bq11[(2b)q1(2b1

，即M MQb

M，(M,Ma

)(M,M

)。类似可得(MMb

)(M,M

)等，于是(MMa

)(M,Mb

)(Mrn

,M

)Mrn

M 。(a,b)第一章习题六1.(ⅰ)显然d=p1p2pk（0

，1 i n的1 2 k i i正因数。反之，设dndnp，d的标准分解i式中p的指数都不超过n的标准分解式中pdp1p2pki i 1 2 k（0 ，1 i 的形式；(ⅱ)类似于(ⅰ)可证得。i i2.

=min{ i i

}，1 i k，ip1pk|a，p1pk|b，而且若d 则d的标准分解式中p1 k 1 k iabp的指数，即d

p1pk，这就证i 1 k明了(a,b)=p1pk，

=min{ ,

}，1 i ；(ⅱ)类似于(ⅰ)1 k即可证得。3. =24 35

i i i747 283。4.写i=，2，i=1,2, ,

为1,2, ,中的奇i i i数，即

只能取n个数值，在n 1个这样的数中，必存在 =i i

（i ，jij成倍数关系。5.写i=2i，2，i=1,2, ,令 =max{, , ,}i i 1 2 n= ，显然 1，且由第一节例5知使 =k

的k 是唯一k的，取 T= 2

1 ，若1 2 n

S是整数，则 STT 21 T 21=T

12

中除

12 n项外都是整数，矛盾。2 2kk

n 2kk6.设ap2pk，bp1p2pk，令1 2 k 1 2 kapp

p

max{,}，i

aa，2 112

k ik i

i i其它， 1 a2bpp

p，

i

bb，2 112

k ik i ，

i i i其它， 1 b2a，a，b，ba=aa，b=bb，(a,b)=1，并且[ab。1 2 1 2 12 12 2 2 22第一章习题七1.(ⅰ)，(ⅱ)，(ⅲ)显然；(ⅳ)由[x ==[{x} {y}]即可证得； (ⅴ)由[=[{x})]= [{x}]即可证得；(ⅵ)由{={{x})}={{x}}即可证得。2.[12347][12347][12347] =1763 251 35 52054。7 72 733.由例4得[x1]=[2x] 于是2[n2r1]

[

1]

n][n])=[n]=n。r2r r

2r 2

r

2r1 2r4．设x=a ，a=1,2,…,n-1，0 <。代入原方程得到[2a]=2a,a

,,2a1 a xn知2 Z，的可能取值是

2a 2a

，即有2

个解。由于=也是解，因此，共有2n1个解。5.设x=n，nZ，1<1，则f(x)=[x][2x][][3][24][2]=n2n2nnnn[2][2][3][4][5 63nf(x)63n137153163n57，另一方面，12345为63k 60型，故12345。6.设n=a

22a

=0或1，则0 1 2 s ih=[n][n][n]2 22 23=

a

sa) a a

s2a)1 2 3as

s 2 3 s=(2 1)a1

(22

1)a2

(2s

1)as=(a

22a

2sa) (a a a

a)=0 1 2n k。

s 0 1 2 s第一章习题八n，2n22m1(22m

122m

1<1 1 12n 1，表明2n 1是合数，矛盾。2.设不然，则n=nn，1<n<n，则2n1121=2n1n21(2n112n11<2n

12n

1是合数，矛盾。若6n 5型的素数只有有限个，记为p,p, ,p，作A=6ppp1 2 k1，

12 k显然A>是奇数，且A是6n 5型的整数，故A必存在一个6n 5型的素因数，从而p=p（1 i ，由p，pppp推出p，矛盾。i 12 k设p，p=d p，p=2d p，首先p 2且d是偶数，于是31 2 1 3 1 1，p，p3p，p，p有且只1 2 3 1 2 33p，p，p最多只有一组。1 2 35.显然下面n个正整数(n 1)! 2，(n 1)! ，(n 1)!(n 1)满足要求。6.设不然，则存在，使得

1Q=p

p，考虑1 nN，

nk1pn 2

12 k显然它们都不能被p,p, ,p整除，即1 nQ的标准分解式中的素数都只1 2 k能在p,p, 中，从而对于任意的r 1，有k+1

k+2

r 1 1 1 ( )n( )n，n11n1

n1mk1

pm n12

11nQ

11nQ是一个发散级数，矛盾。

n1

n1第二章习题一定理1的证明：如果(ⅰ)成立，ma b==b 知(ⅱ)成立；如果(ⅱ)成立，写a=qm r,b=qm r，0 r,r1 1 2 2 1 2m 则qm r=qm r 由此得r=r，知(ⅲ)成立；如果(ⅲ)1 1 2 2 1 2成立，a=qm b=qm r m 则a b=q)，1 2 1 2ma 2理1及a c(mod可知存在整数q，q，使得a=b q=c1 2 1q因此a=c (q q推出a c(mod。定理2得证。2 1 2由x y(mod得

(modai

b(modai i

bi(mod

axii

byi(modii0 i0(ⅰ)由a b(mod得ma 又d故da 即ab(modd)；(ⅱ)由a b(mod得ma 故kmka 即akbk(mod(ⅲ)由a b(modm)得ma 故[m,m, ,m]ai i 1 2 k即a b(mod,m, ,m])； (ⅳ)由a b(mod得a=mq1 2 k故=(ⅴ)由ac bc(mod得mac bc=又=1，故ma 即a b(mod。

1(mod1381234

(

1 12(mo对任意的整数，x r(mod，1 r ，于是() )0(mod，从而0，所以方程=0没有整数解。6.由99|9|11|。从9|62427得 =6或 =15，从11|62427得 = 2或 =9，于是关于， 的方程组6 6 15 152 或9 或2 或9得 =2， =。第二章习题二若A是模m的完全剩余系显然(ⅰ)与(ⅱ)成立反之满足(ⅰ)与(ⅱ)的一组数必分别来自于模m的每一个不同的剩余类，即A是模m的完全剩余系。2.由威尔逊定理知 1 ()!=!(p 1)(2) (1)(!)(mod2p 1!)2

( 1)p

0(mod2p 1)。3.由(p 1)! p 1(modp)，(p 1)! p 1(modp 1)以及p 1)=1得(p 1)! p 1(mod又2N=，故(p 1)! p 1(mod。4.设不然，n=nn，1<n<由(n 1)! 1(modn)得0 112 1 1(modn)，矛盾。1设4如果{ab,ab, ,ab}是模m的完全剩余系，则其中的奇11 22 mm数与偶数各半，又{a,a, ,a}与{b,b, ,b}也是模m的两个完全剩余系，1 2 m 1 2 maba，bab2(mod44mm的ii i i ii完全剩余系是不可能的。(ⅰ)由b通过m个数可知b b

b mmmmi i 1 1个数；(ⅱ)如果b b1 1 2 2

2 2 n nb bn n 1 1

12 nb2 2b (modbn n 1

b1 2

b bn n 1 1b b (modm即b b (modm=b 。2 2 n n

i i i

i i i故b b

b m=mm

m的完全剩余系。1 1 2 2 n n 12 n第二章习题三Ammm互素的剩余类，即m的简化剩余系。nn=23n时成立，即x=Mx Mx

Mxm=mm

m的简化剩余系，则

1 1 2 2 n n

12 nmx mmmxn+1=m

12 nn 1x mM

M

mmmxn+11 1=Mx M

n+12 2Mx

n+1n M x

12 nn 111 2

n n+

n+1通过模mmmm 的简化剩余系，由归纳原理知命题对一切n 2成立。12 nn+1写ax=mq r，0 r<由x通过模m的简化剩余系知r通过i i i i i im1(m)ax (m)

r (m)mm

1(m) 1 1{ i}

{q

i}

i

m(m) (m)。i1

ii1

i1m

mi1

2m 24.mpkm，np1pknpm，pn(mn)1，则1 k

1 k 1 i 1

1 1 1(mn)(p

mn)p

p

k1

1)(m)(n)，11 1

kk k 1

11

k kpk 1 1pi1 i((m,n))(pmin{,}pmin{

,})(m,n

1)，i1 11 k k i

i1 p由此得(mn)

((,))=(,)ppk11(m)p

pk11(n)p11 kkpii

1 1

kpk 1pii=(m,n)(m)(n)。5. apkm，bp1pknpm，pn(mn)11 k

1 k 1 i 1

1 1 1mp

p

n2mk，n

(m)m2nk，(k,a)=(k,b)=1，则可得

b，1 k1 k 1 1

11 kk 11

(n) a即ab6.(ⅰ)当n=1时显然；当n=2时，(2)=2

1>1 （21npp为奇素数时，

(p)=p p

1>（

1；现在设 npk ， 则(n)(2)(p11

)(k

1 k)1 2

p11

pkk

1 nn是合数，2p为n的最小素因数，则p n，于是0 0n1)1)1)n n。0p|n p p n0第二章习题四53得1978103 19783 0(mod553得1978103 19783 0(mod5，故1978103197830(mod102.31159=5159=(6)253 53=255 456(mod7)。3.因561=311 17，对于一切整数561)=1，有(a,3)=1，(,11)=，(,17)=560=)2801(mod3，560=

19783

0(mod2

1(mod(1)56

1(mod

=(1)35

1(mod17560

1(mod561)。由费马定理

1(mod

1(modq)，pq

qp 11(mod1

1

1(mod故1

1

1(modpq)。5.

1=

1)(

1)(

1)=543 73146657，对于4665，它的素因数必为12k 1型，经检验的46657=1337 9，故6121=57133137 43 97。6.p

1，

1(mod

1(modp)，由例5得下面两种情形之一成立：(ⅰ)p12nd<2n成立；(ⅱ)p 1(mod第二章习题五np1p2pkndp1p2pk（01 2 k 1 2 k i，1 i (1

1=(1

)(1

)(1 )。i 1 2 kd|n i10ii由上式立知是积性函数，但=3 4=故不是完全积性函数。=1且f(p2pk)f(pf(p)2fp

)k。反之，若整数m，n中有一个等1 2 k 1 2 k1mp1pk，np1pk，则f(mn)f(p11pkk)

1 k 1 k1 kf(p1f(

)kkf(p)1f(p)kf(p)1f(p

)k1 f(m)f(m)。

1 k 1 k3. 1

1n

1 (n)d 。d|nd nd|nd nd|n n4.(ⅰ)当n=11npk，1 k(df(d(1pfppifpifp；(ⅱ)i i i i id|n pi|n pi|n当n=1时，右边的连乘理解为1npk1 k2(df(d(12pfp2pifpifp。

，则有i i i i id|n

pi|n pi|n5.n=1(d=1，npk，则1 kd|n(d) (d)1

(d)kd|n

d1|p1 dk1|pk1 k(p(1)](p(pkpk1)]1 1 1 k k kp1pkn。1 k第三章习题一对于任意的正实数，写 =[] {}，则由定理1，定理2可知[]与{

}可分别唯一地表示为kabi与abi形式，故

可以唯一的表示为ii0

ii1=abi（0 a b ，且对于任何正整数，都存在n>，使得a <i i ni1b 1）的形式。2.789=(01)2

=(11124)。53. 821

=0.809。n

aa

=a7k

a7 a a

a a(mod得

k 107 k

1 0 k 1 02n=(a

aa) 2

a a。k若m=(0aan 1

107ak

kb

1

1 0abk22

a)，kn，故nb的因素数。反之，若n的每个素因数都是b的素因数，则必存在k，使得nbk，即bk1 1 m

=nn，1 mn (ablaba)故 的b进制小数(0aa

)为有bk 1限小数。

bk l

1 0 n

1 2 3 b第三章习题二1.显然p=1|1.显然p=1|a|=1a，p1 2=a111a=aa1，当k3时，有a1100a 1001a2101a00pa 01a0=app，k k3kk1kk2121120000000 a00此与定理1中p的递推式一致；k

ak20显然q1

=1，p2

1 0=a0 a 22

3时，有10001000a0001a101a002 2qa0 1 a 0

=aq q ，k k 3 0 0 0

ak

0 0 a k20 0 0 1

kk 1 kk 2此与定理1中q的递推式一致。kk=2a 1a

1 a

1 a p p1

1

12 11 01 0 a2知k=2时成立，归纳假定

1 q2

q1a 1a

1

1 p p 1 2

k1k kk k

1 01 0 1 0 q q a 1

1

1a 11

k1 01 0 1 01 0p p

1

pp

p pk

k

k

k1k

k

k

k

k，q q

1

0 a q

q qk k

k1ka 1a

k11

k kk1 p p q由归纳原理知对一切k 2有1q

2

k

k

k1。k1 01 0 1 0 k

k1a1

=1，a2

=2，a3

=3p1

=1，p2

=3，p3

=10，q1

=1，q2

=2，q=7，3故连分数 1,2,3,4,5, 的前三个渐近分数为p p 3 p 1012 ，3 。qq2 2 3 7q14.设x= 2,3,2,3, ，则x=2 13x

，由此解得x3 15。37 1 15.易知9

17

11 32

= 0,1,3,2，p1

=0，p2

=1，p3

=3，q=1，q1

=1，q=4，于是74=4，于是7493=(1)4=1，7x9y=4有12，原方程的一切整数解为x=16 9t，y=12 x0tZ。

=16，y=0第三章习题三1.(ⅰ)记

= a,

, ,a ， =

, , ,k k+

k+2 n

k+1

k+2，由

=a知a

]=[

1ba

1b 推出m 0 0 b 1 0

0 1 1 1 11 1= a=[]=[]=bn=b1 1 1 1 1 i i（1 i ；ⅱ)由ⅰ知a可唯一地表示为 a,a, ,a ，a>b 1 2 n n1，又易知 a,a, ,a 还可以另写成简单连分数 a,a, ,a

1,11 2 n 1 2 n，但仅此而已，故有理数a仅有此两种表示成简单连分数的方法。b132. = 3,1,1,1,1,6,1,1,1,1,6,1,1, 。133.经计算2 3= 3,1,2,1,2, ，由此得p1

=3，p2

==311，p4

=15，p5

=41，p6

=56，p7

=153，p8

=209，p9

=10

==112131， ，q1

=1，q2

=1，q3

=3，q4

=4，q5

=11，q6

=15，q7

=41，q8

=56，q=

=

=571， ，于是|2 3780| 1

1 780 9 10 11

209 209571 105

209即为所求。4.sin18 =

51= 0,3,4,4,4,4,

=0，p

=1，p=4，p3

=17，p5

4=72，p6

=305，q1

=1，q2

=3，q3

1=13，q4

2=55，q=5233，q=987，于是|sin1872| 1 1，故

即为所求。6 233 233987

2333 22 333 355 103993 1043085. 的前几个渐近分数为， ， ， ， ， ，，1 17 106 113 33102 33215355 10993其中 和113

分别满足误差满足 10

6和 10

9的要求。6.1 5= 1,1,1,1,1, pp

p =F2 k k 1 k 2 kp FF =

，q=q

q =F

F =F

k k1。k 1 k+1 k k

k 2 k

k 2 k q Fk k第三章习题四1.1,1,1,4,

2x 2=0。

713

= 0,1,1,4,1,1,1,4,2.

, =

12 12

，解得x 151。21 13. a21a(a21a)a,,。

a21

a

= =2a(a21a)4.若da,,a，则1 2 n 1

(a d)ppda,,d

a,

,,a,

d

n n1，1 2 n

1 2 n

(a d)q1

qn1得(dq ap

) p p

p)ddp=n 1n n1 1n n1 n naq q

ap p

=aq

，dq=ap p ，1n n1则

n 1n n1

n 1n n1 n 1n n 1(a)pp=a,,aa,

,,a,a

n n1，1 2 n 1

1 2 n

(a)q1

qn1得满足方程q

2 q q

p) p

p)=0，即

2=d，=d。n 1n n1 n 1n n=d。5.由第4题可得到。第四章习题一1.设17xyz，即35x =因(35,21)=105 3 5 715)=17，故有解。分别解5x ==17得x= t3u，y=2t 5u，uZ，t=11 15v，z= 4 Ztx= 11 15v 3u，y=22 30v 5u，z= 4 7v，u，vZuv的值，都给出一种表示法。x1

2x=3x2

=41x1

=t 2

=u，uZ，t=41 3v，x3

=Ztx1

=41 3v 2u，x2

=u，x3

=v，u，vZ。由此得原方程的全部正整数解为(x,x,x)=(41 3v u>0，v>0，41 3v 2u>0。

1 2 3消去x得9x 14x=3，解得x= 9

= 6 Z，1 2 3 2 3从而得不定方程组的解为x1

=43 55t，x2

= 9 14t，x3

= 6 tZ，设甲、乙班的学生每人分别得支铅笔，则7x 11y=解个不定方程得x=8，y=4。xx二元一次不定方程ax by=n的一切整数解为

bt，tZ，y x y

yy at0n于是由x 0，y 0得 0 t 0，但区间[0,0]的长度是 ，故此a b a b ab区间内的整数个数为

或

] 。ab ab因为0,1,2, ,ab a b中共有(a 1)(b 1)个数，故只须证明n与g =ab a 有且只有一个能表示成ax 0，y 0）的形式。如果n与g n都能表示成ax 0，y 的形式，即ax by=（x 0，y 0，ax by =g （x0，y 0，则(x x) y y)=，这是不可能的；如果n不能表示成ax 0，y 0）的形式，则因为二元一次不定方程ax x=n的一切整数解为 0

bt，tZ，所以当t使0 x b 1时，必有y at0y 1，于是1 1 =g 即g n能表成ax 0，y 0）的形式。第四章习题二

n，y （m ）满足方程2 2=，即2 2m=，于是得l= ab，n= 2

)，m= (2

)d或l= 22d，m= abd，m= (2 d，由此得(,)(2ab a2 b2)(a2 b2 2ab)= , 或a2 b2 a2 b2

,a2 b2 a2

。反之，代入方程2 2=1即b2知这样的点在单位圆周上。由2=(z )(z 及x是素数得z y=，z y=1，于是2z 1=，2(x y 1)=(x 1)2都是平方数。设x y=，y z=，x z=，则2 2=，由此得x222，y2)2t422，z，tZ。设(zzd=1。由(z)(z)=2zx=d，zxd，ydabzxd，zx=d，y=dab，a>0，b>0b)=1。(ⅰ)当d=1：3a2|x ，

ab，

b2

，a>>b)=b2 2d=：x=2

，y=a，z=2

，a>，b>0，(a,b)=1，3b一奇一偶。反之，易验证(ⅰ)或(ⅱ)是原不定方程的解，且x>0，y>0，z>0，(x,y)=1。，，z

2

2，y同为奇2

2 2

，3(mod4，2

1(mod4)，此不可能；如果x，y一奇一偶，则2 2 2 ，2(mod4，2 0(mod4，此也不能。所以同为偶数，z也是偶数，令x=2x，y=2y，z=2z，代入原方1 1 1程得x2 y2 z2=xy，反复以上的推理可得，，z能被2的任意次乘1 1 1 1 1幂整除，只能x=y=z=0。(ⅱ)类似于(ⅰ)可证。设，，z是2 2=4的满足,)=，2x的正整数解，则x=2a，y=2

，2

=2

，ab>，()=，b

=2

2a=u，b2

，z=2

2或a2

，b=2u，z2 ，uv>，()=，vx=u(2，y=

4 62，z=

，u>v>，,)=，,v一奇一偶。反之，易验证它是原不定方程的整数解，且x>0，y>0，z>0，(x,y)=1，2x。第四章习题三1.由=6得=(1,5)，(1, 5)，(2,1)，(2, 1)，(3, 1)，(3,1)，(6, 5)，(6,5)。2.由第一个方程得z= (x 代入第二个方程经化简得xyz= 由此得=(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是不可能的，故原方程的正整数解只有(x,y)=(2,1)。

1(mod8)，这显然x>>令x=z =z N，代入原方2ss，t2，zabdN)=，由此得x=abd 2，y=abd ，z=ab，反之，将上式代入原方程知它们是原方程的正整数解。不妨设x 当p=2时，(x,=(2,2)。下设p是奇素数，令2xp ，2y=p ，，tZ，s 2=s，由此得s=1，t=2或s=p，t=p或s= 2，t= 1，即,)p1,pp1))pp)p,p1。2 2 2 2设为任意的有理数，容易证明：若a,a, ,a

具有性质P，1 2 2n+1则(ⅰ),Ma, ,Ma 也具有性质(ⅱ)a a

b, ,1 2 2n+1 1 2a b也具有性质。由此我们可假定a,a, ,a 都是整数，且

=0。2n+1 1 2 2n+1 1a a Pa都是偶数，于是由(ⅰ)知1,2,,2n1a a i 2 2 2ka a k们都是整数，且1=0。反复以上推理可知对于任意的正整数，1,

2,,2n1a2 2k 2k 2kaa=a1 1

= =a2n+1

=0。第五章习题一(ⅰ)若) 0(mod则) ) )(mod成0 0 0 0立，反之，若) ) b(x)(mod则) 0(mod成立；(ⅱ)0 0 0 0若) 0(mod则) 0(mod成立，反之，若) 0(mod0 0 0则由=1得) 0(mod成立；(ⅲ)若g(x) 0(mod0 0 0则由m是素数得) 0(mod或) 0(mod。0 02.(ⅰ)x4(mod17)；(ⅱ)x1，48，95，142，189(mod235)。y8x41(mod47)，x11(mod47)，代入原方程组y1(mod47x11(mod47)，y147)。(p1)(p2)(pa1)首先易知b(1)a1 是整数，又由=1知a!(p1)(p2)(pa1)方程ax b(mod解唯一，故只须将xb(1)a1 (moda!代入ax b(mod验证它是同余方程的解即可。n12n=k时结论已真，考虑ax ax

ax ax

b(modm)，令(a,11 22

kk k+1k+1 1a, ,a,=d，(d,a

)=，因为同余方程ax

b(modd)有2 k 1

1 k+1

k+

k+1 1d，moddm=dmdm，modx1，由归纳假定知ax ax

11 1ax b a x

k(modm)有解，其+1 11 22

kk k+1k+1解数为dk，mod，从而ax ax

ax ax

b(modm)1 11 22

kk k+1k+1有解，其解数为dm1

dmk11

=d。由归纳原理知命题对于一切n 1成立。6.因为(2,12)=，(2,7)=1，故同余方程有解，其解数为1122 1=12，mod12。先解同余方程7y 5(mod2)，得y 1(mod2)，写成y1 (mod=0,1,2, ,5，对于固定的解同余方程2x 57(1 2 (mod得x 1 t(mod写成x 1t6s(mod12)，s=0,1，故原方程组的解为x1t6s(mod12)，y1 2t(mod12)，s=0,1，t=0,1,2,,5。第五章习题二1.m=56711=2310；M1

=6711=462，M2

=5711=385，M=5611=3

=567=210；由462M1

1(mod得M =13，385M2

1(mod6)得M2

=1，330M3

1(mod7)得M3

=1，210M4

1(mod5)得M4

=。所以原同余方程组的解为x 3 462b11 385b2

1 330b3

1210b4

(mod2310)。2.因为(15,8)=18 25)=58 25)=1513，故原同余方程组有解，解数唯一，mod[15,8,25]=600。将第一个同余方程的解x=815t，tZ，代入第二个同余方程得t 3(mod8)，即t=3 8t，tZ，1 1 1 1 2 2x=53 120tt

3(mod5

=3 5t，2 2 2 3tZ，x=413 600t，所以原同余方程组的解为x 413(mod600)。3 3注：此处所使用的解法思路简单，但比较繁。设士兵有x人，由题意得x 1(mod3)，x 2(mod5)，x 3(mod11)，由孙子定理得x 58(mod165)，故x=58人。1(mod2)，0(mod3)，0(mod5)；1(mod2)，0(mod3)，0(mod5)；0(mod2)，1(mod3)，0(mod5)；0(mod2)，0(mod3)，1(mod5)，由孙子定理得15(mod30)，10(mod30)，6(mod30)，故n=。5.作同余方程组：x 0(modp)，x 1(modp)，…，xn11(modp1满足要求。21，…，xnn6.因105=35，同余方程32 11x 20 0(mod3)的解为x1(mod3，同余方程2 1x 38 0(mod5的解为x ，3(mod5，同余方程32 11x 20 0(mod7的解为x 2，6(mod7，故原同余方程有4解，mod。作同余方程组：x b1

(modb2

(mod5)，xb(mod7)，b3

=1，b2

=0，3，b3

=2，6，由孙子定理得原同余方程的解为x 13，55，58，100(mod105)。第五章习题三(ⅰ)由定理知存在整数x=a pt，tZ，使得x

(mod)2 1 1 2是同余方程) 0(mod)的解，x2

a(modp)。再由定理知存在整数x3=x+2t，tZ，使得x

(mod3是同余方程) 0(mod3的解，2 2 2 3x x a(modxx3 2 1

p 1t，t Z，使得x x(modp)是同余方程0(modp)的解，x1 1x x a(mod(ⅱ)由条件知同余方程f0(mod1 2的每一个解x x1

(mod都不是f) 0(mod的解，即f(x)01(mod于是由(ⅰ)知可导出0(modp)的解x x(modp)，且由(ⅰ)的证明过程知只能导出唯一的解x x(modp)。对x 2(mod5，令x=2 t代入同余方程22 1x 340(mod52得t 0(mod5，于是x=2 5(5t)=2 25t，代入同余方1 1340(mod即x 2(mod程2340(mod即x 2(mod

得到t 0(mod5，于是x=2 25(t)2=2 125t，2

5是同余方程22 1x 34 0(mod3)的一个解。x0

=4，则由(4 7x1

7x22

2(mod2x1

5(mod7)，x=。再由(4 7 5 7x)2 2(mod得x

4(mod7)，x

=4，1 2 2 2这样，求得原同余方程的一个解是x 4 7 5 72 4=235(mod73)4.54=232解。

1(mod32

(mod因75=35，先解() 0(mod3)，用逐一代入法得解x 0(mod3)；再解) 0(mod5，用逐一代入法得) 0(mod5的解为x (mod对于x 0(mod令x=5t代入0(mod得t (mod5)，于是x=5(2 5t)=10 25t，即x 10(mod25)是2 20(mod的一个解，对于x 2(mod令x=2 代入0(mod25)得t 4(mod于是x=2 5(4 )=22 25t，即x 22(mod2 225)是0(mod的一个解；最后构造同余方程组x b1

(mod3)，xb(mod2

=0，b2

=由孙子定理得0(mod的两个解x 10，72(mod75)。令m=ppp，p是不同的奇素数，由2 1(modp的解数

=2，12 k i i iTTTT=k2k。12 k第五章习题四1.

4

2

1 0(modx=0， ，，3代入知后者无解；ⅱ)原同余方程等价于24 23 x2 0(mod将x=1，2代入，知后者有解x 1(mod。2.ⅰ) 3

x 1 0(mod5

2

30(mod5

x=

2

x

x 5)+(212x 15，其中()=62 1x 15的系数不都是5的倍数，故原方程没有三个解；(ⅱ)因为这是对模5的同余方程，故原方程不可能有六个解。x1

a(modyx0

x(modm)1有解再由k0

)k0

xk a(mod1

1(modm)，即x可以表示成x yx(mod其中y满足同余方程1(mod反之，1 0易知如此形式的x是a(mod的解。由kp 1知同余方程1(mod恰有k个解，又由kn知这k个解也是同余方程1(mod的解。下证同余方程1(mod的解

1(modxn0

1(modksnt(p 。若s><则xk xt(p 1)=xk1)=xsn n)s0 0 0 0 0 01(modp)；若s<0，t>0，则可类似证明。5.(ⅰ)1故对于一切整数

1 0(mod有解x ，p 1(mod1 1)2)(x p 1)(mod(ⅱ)在(ⅰ)中令x=p。2)(x p1)=1=122)(x p1)=1=12(p1)

a 2

a2ax aa

p 2=p(p

2p的倍数，1 0 p 2 2考虑同余方程0(mod=xp 1

a 3p 3

a22ax a，显然它有解x ，p 1(mod故x=1 0(中的余式()= a p 2 a3 a2 (a

1)x的系数p 3p的倍数。

2 1 0第五章习题五1311.因112 13)无解。

=123

3 12 1(mod132

11(mod2.模23的所有的二次剩余为x 1,2,3,4,6,8,9,12,13,16,18(mod二次非剩余为x 5,7,10,11,14,15,17,19,20,21,2223)。p1设为模p的二次剩余，有(ab)2

p1p12b2 11 1(modp1 p1 p1再设为模p的二次非剩余，有(cd)2 c2d2 (1)(p)，以及

1(modp1(ac)2

p1p1a2c2 1 (1)p1

1(modp)知结论成立。p1n2 n(modx

n得(n4p1n4(mod

n(modp)，由此知

n(modp)有解x x0

(modpx0

n(mod)，故n)=p1，反之，若(n)=2p

n(mod有解x x0

(modp2x，故0有解。

n(modp的一个解x x(modp，即2 n(modp)设x,x, ,x为模p的所有二次剩余，则1 2

p1

p1

p1xxx 122 ( )2(

2(p1)!)2 (mod12 k 2第五章习题六1.(ⅰ)因(1742)(204)(

4)(

3)(17

)(1)(4)1，原同余方程769 769 769 769 769 3 17有解；(ⅱ) (1503)(490)

2

5

49)(1013)(3)1，原1013 1013 1013 1013 1013 5 5同余方程有解。(11)

(1)p1(p)12.由 推p

2 ，由此得11(1)

p12 1或

(1)

p12 1，p p( )1 ( )111即

11p4) p4)p

或 ，p1,3,4,5,9(mod11)解之得p 1，5，7，9，19(mod44)。3.由 23推得(2)1，(3)1，即p p1)p

1( )1p21，或(2)1。)p3p)

p3(p)1解之得p 1，或11(mod24)。p2(3y2

2

(mod)=1(3,p)=1，于是

)( )1，由此得p的一般形式为12k 1型。p p若8k 5型的素数只有有限个，记为p,p,,p，作A=(2ppp)21 2 k 12 k1，A>，Ap，即(2ppp2

1(modp)，12 k(1)1，由此得p的一般形式为8k 1或8k 5型，由A 5(mod8)知pA的素因数p中至少有一个是k 5型的，对这个，有p=p（1 i ，ippppp1，矛盾。12 k当p=k 1时，同余方程2 1(mod有解x n(mod，p2

p2

1)2

2)2

；当p=3时，同1)(2

2)(2

2(mod有解x n(mod，即p22；当p=8k 7时，同余方程2

2，p22(modxn(mod，即p2 2，从而p2 1)(2 2)(2 2。第五章习题七1.(ⅱ)显然；(ⅲ)设m=ppp，则12 k( ) ( )( ) ( aaa aaa aaa aa( ) ( )( ) ( 12 t 12 t 12 t 12 tm p p paaa1 2 kaaaaaaatt(1)(t)(1)(a)(1)(aaaaatt

)(1)(2)(t。p p p p p1 1 2 2

p m m mk(ⅳ)(a2b)(a)(a)(b)(b)。m m m m m2.因(

)

2 )(

)27)

3(11，原同余3019 3019 3019 187 187 3方程无解。d 1 2d 2d3.设d= 2d，d为正奇数，( )( )(

(1)(

(1)，当 >01 1 p p p p p p2 d p 1时，p=8n 1型，( )=1，当d>1时，(1)( )( )=1，所以p 1d 2d

p d d1 1( )(

(1)=1。p p p由p=q 4a知同为4k 1或同为4k 3，当p，q同为4k1a4ap4aqpq4a4aa同p p p p q q q q为 4k 3 时 ， 有(a)(4a)(p4a)(q)(p)(q4a)(4a)(a)。p p p p q q q q当a 0(mod时，则2a b b(mod令a=2a，a为奇1 1数 ， 于 是 有a 2 a 2

a a( )( )( 1 )(

( 1 若a( 1 )(1)，若a>2ab 2ab 2ab b 2ab 1 2ab b 1a b1 b a

a 2a a 1，( 1 )

2 2( (1故得(

)(

(1)( )；当a 12ab

a b 2ab b b b1(mod4)时，若a=1，( a

)(a若a( a

)(b)(a)，故有2ab b 2ab a b( a )(a)；类似地，当a 2(mod4)时，令a=2a

为奇数，于是2ab b 1 1a2( a ) (2a2( a ) (2)( a ) (2)(a)(a1 1 12ab2ab2abb2abbbb

)；当a 3(mod4)a 2ab1

2a

2ab1b a a时，( )2

( )

2 ( )( ( )。2ab

a为奇数，有(

)

a( a14acb1b( 2 2

b

b( a1b1b( 2 2

(a)，4acb

a a b若a为偶数，于是4ac b与b同为8k 1或同为8k 3，即(

2 )(2)，4acb ba 2 a 2 a设a=2a

(

)( )( 1 )( )( 1 )=1 1 4acb 4acb 4acb b 4acb2 14acb1

b 2

1b1 b

2a a( )2 2

( )(

2 2( )(

(1)( )。a b1

a b b b1第六章习题一设，，c是不定方程2 2=2的正整数解，则易知x=an，y=bn，z=2是不定方程2 2=n的正整数解。对于每一个<i<令i满足ii 1(mod<i <(iik))(iik))(i2iik))1(1ik))11。i0

i1

i1

i0 p

p 1 (mod 4) 知 (1)p

， 于 是S(k)(ii2k))(ii2k))i0 p i1 pp1 p1

p12(i(i2k))

((pi)[(pi)2k])2

i(i2k)

S(k)；又对于任i1 p

i1 p

i1 p何整数，若t 0(mod，则S(kt2)2(i)(t)S(k)0，若t0(mod)，i0 p pp1i(i2kt2) p1it[(it)2kt2] t3p1i(i2k) t则S(kt2)( )( )( )( )( )S(k)。i0

i0

p pi0 p p4.m12m22,m(

p

)2,n12,n22,,n( )2中共有p 1个pp数又易知mi2mi2(modnj2nj2(mod若m2 n2(mod

1 2 1 2(mn这是一个矛盾；最后易知(mp

2n)=。p的一个简系。p1

p1

p12

p12 p15.23

S2(m) S2(n)S2(mt2)S2(nt2)S2(k)2 2t1 t1 k111(iji2k)(j2k))11(iji2k)(j2k))。k1i0j0 p i0j0kp22(mod2k，则(2)(2k)=z[z22)，2,)=，有(iji2k)(j2k))(ij)[1((i2k)(j2k))]k1

p p k0 p

(ij)[1(z(zi2j2))]2(ij)；p k0 p p2(mod(iji2k)(j2k))(ij)1(i2k)2(p2(ij)。k1故

p pk0 p pp1

p

p1

p1

ij p1 pij2 S2(m) S2(n) 2

[2( )] (p2)( )i1

jp ijpi2j2(monp) i2j2(monp)21(ij)p

1(ij)2(i)(j)1(ij)11(ij)ijp ij

i1p

j1p

i1j1p

ijpi2j2(monp)1 02p(p1)2p(p1)1 由此得p( S(m))2( S(n))2。2 2

ji

jpi6.取m=，n=2，则)=，()= ，由此得13=32 2。第六章习题二设2

2=2成立，若，y都是奇数，则2

2 2或3(mod4，此不可能；若，y一奇一偶，则2 2 2 1或2(mod4)，z1设2 2 2=，，，z>，若k ，可得，，z都是偶数，于是令x=x，y=y，z=z，代入得x2 y2 z2=k 2，若k1 1 1 1 1 12 2x，y，zx2x，y2y，1 1 1 1 2 1 2z=2z，代入得x2 y2 z2=2k ， ，最后推出，存在，，c>，1 2 2 2 22 2 2=202，显然这是不可能的。3(x 1)3 3

n 0(mod6。

n=n3

x 134.若16k15=x4x4x401(mod12145.16k

31=x4 x4

x4

01(modxx,1,x

2=2x

15=2x

，

=2x

1 2，代入得15

1,1

2,1

15 15,116k 1 31=x4 x

x，31

1,14

2,1x4

15,1x311,k

2,k

15,k为15个四次方数的和，故16k 31不能表示为15个四次方数的和。第七章习题一

(1)=11

(2)=11

(3)=11

(4)=11

(5)11=5，11)11)

(6)=10，11

(7)=10，11

(8)=10，11

(9)=5，11

(10)=2，列11a12345678910(a11055510101052x 3，5(mod1414

(m)因1,, ,g构成模m的简化剩余系，由d

(g)m

(,(m))得(,(m))(m)(mt，则d(,(m))=(m)d

d，1 (m) (t,=1，1 t 故恰有个使得=从而知故恰有个 ，使得特别地，取d= 知模m的简化剩余系中恰有(个原根

(g)=d。mⅰ)因1,2, ,g(为模m的简化剩余系，设同余方程2 1(mod的解为x g

(modg

=g2r

1(modm)，由此得2r 0(mod又由m 3知是偶数得(m)|(m)或。2 2另一方面，同余方程2 1(mod至少有解x ，1(mod，由(m)

(m)1(mod推出g2 1(mod。ⅱ)因1,2, ,化剩余系，故(m)((m)1) (m)(m)(m) (m)

m的简xxx12 (m)

12 g() g 2 g2 g2 g2 1(modp

p2

2n1p的简化剩余p1系中有(= (2n)=2n1个原根，又设g是模p原根，则g2gp的二次非剩余。

1(mod6.(ⅰ)由2p

1(mod

(2)p，于是q

(2)=1或p，但易知q(2)q

1，故

(2)=q

(2) =q 1知q 1=其q中t必为偶数故q为2pk 1型；(ⅱ)由22n22n1q)知 (2)2n+，于是q

(2)=2r，0 r n 又由1(modq知 (2) 2r，0 r 故q

(2)=2n+1，再由q

(2)q

=q 1知q 1=2n+，故q为2pk 1型。第七章习题二1.因(29)=28=2 ，(29)

(29)2 2

(mod29，27

(mod29)知2是模29的最小正原根。2.由2是模29的原根及229

=

=2281(mod292223的原229322+2932293的原根。3.易得3是模17的原根，3i（i=0,1,2, ,15）构成模17的简化余系，列表为i012345673i(mod17)139101351511i891011121314153i(mod17)1614874122638

16(mod设x 5

(mod则12y 8(mod由此解得y1

2，y2

6，y3

10，y4

14(modx1

9，x215，x3

8，x4

2(mod17)。4.

(2) 4pq

(2)，，，，2pq

1(modq24

1=15=35q=35，这是不可能的，故

(2) q(2)qq1

2， (2) 4，q是8k+52q的二次非剩余，即q22 22p1(mod

(2) q

(2) q

(2)=4p= (q)，q+15.(mod存在一个m)，+15.(mod存在一个m)，，(,(m))=1，使得g2g1(modgg12g1又由m3知(m)是偶数，是奇数，1是偶数，(1,(m))1，故g=ggm的原根。6.当p12当p 1n时，则1n 1ngp1n(p2n1)np(p11)n(mod(1(22n(p1)n]gn(modp)，得[1n1n2n2n(p(p1)n](11)ngn)0(mod0(modp)。p)，由(1)0(mod第八章习题一考虑函数n

n(xj))，

m (xij)与

(xi)。mmi1j1 i1j1 i1j1 j设 是代数数，则bn

b n 1n 1

b b=1 0b都是整数，b

两边乘以bn 1得(b)n

b (b

)n 1 bni2bb

n) bn

n0b

n n 1 n n是代数整数。1 n n 0 n有理数r是方程x r=0，若r是代数整数，则方程的系数r是整数，rr是代数整数。第八章习题二1.(ⅰ)令1