《初等数论(闵嗣鹤、严士健)》习题解答2012完整版

1、初等数论习题解答第一章整数的可除性§1整除的概念带余除法1.证明定理3定理3 若5 2,都是加得倍数，CIV绻，绻是任总：”个整数则qa + q2a2 + Qnan是 川得倍数.证明:a 4,an都是m的倍数。 存在H个整数PP2、Pn使ax = PImy a2 = p2m,，an = Pnm又qWMn是任总"个整数也+也+恥“=q PiIn + q2 PIm + + % Pnm= (Pls+的/勺+乞几)加即qial + q2a2 + qnan是In的整数2.证明 3ln(n + l)(2 + l)证明. nn +1)(2 +1) = n(n + l)( + 2 + -l

2、)=n(n + I)(W + 2) + (n l)n(n +1)又. n(n +1)( + 2), (n-l>( + 2)是连续的三个整数故 31 (n +1)( + 2), 31 (H- l)(n +1). 31 H(H + l)(z + 2) + (n - 1)(h +1)从而可知31 n(n +1)(2? +1)3若ax0 +是形如Q + by (x, y是任意整数.a. b是两不全为零的整数的数中最小整数，则(ax0+by0)(ax + by).证：Y a,b不全为O在整数集合S = ax+by IX,y Z中存在正整数因而有形如Q + by的最小整数ax0 + hy02/51初

3、等数论习题解答 Vx, y eZ ,由带余除法有ax + by = (v0 + by0)q + ryOr < CIXQ + by0则r = (x- XOq)a + (y - y0q)b e S ,由ax+by是S中的最小整数知厂=O：.UXi)+by0 ax + by. UX+ byI ax + by ( , y 为任总整数). ax + by0 I a,cx + byI b：.aXQ+byQ (a.b).又有(a,b)a(a9b) Ib(a, b) I v0 + by0 故 v0 + by0 = (, b)4.若a b是任总二整数，且b0.证明：存在两个整数s(使得, I川1a =bs

4、 + t, Ir l 2成立，并且肖b是奇数时，s t是唯一存在的、"Ib是偶数时结果如何？证：作序列,一出,一冏,一也,o,也，|M，出则"必在此序列的某两项之间2 1 1 2 2 1 1 2即存在一个整数g,使b a<(i)当q为偶数时，若b>Q.则令S = -J = a-bs = a-b 9则有2 20a-bs = t若b<0.则令$=若b<0 则令S = -t=a-bs = a + h,则同样有r<y(ii) >,zq为奇数时.若方>0则令S =父二!，/= ZW = -纟二!，则有 2 2综上所述，存在性得证.t = Cl

5、-bs = a+ b .则同样有 Iy2 2 2下证唯一性当b 为奇数时,设a=bs+t = bs、+11 则-r1 = b(sl -5)| >b而kyy,k-rk+kH 矛盾故S=S=Fb为偶数时.SJ不唯一举例如下：此时匕为整数2c b b , b、 Z?./?3-=l + -=2 + (-)1 =-,h-§2最大公因数与辗转相除法1.证明推论4.1推论4.1心b的公因数与(a, b)的因数相同.证：设d'是a b的任一公因数 .d'a 6zb由帶余除法a = bq、+f,b= %÷<-2=也绻+八，汕= <1r=÷<-

6、<<<.(a.b) = rn.-.dta-bq = , df b-rq2= r1. d9 rn=rnqn+rn=ayb)即/是(Ge)的因数。反过來(b)且(b)l?,若b),则l,l"所以(")的I対数都是d"的公因数，从而CI, b的公因数与("上)的因数相同。2证明：见本书P2, P3第3题证明。3应用§1习题4证明任意两整数的辰大公因数存在并说明其求法，试用你的所说的求法及枫转相除法实际算出(765OL 9719).解：有§1习题4知：Vd,/? wZ,Z?HOVsJ uZ,使a = bs + t.t-Q.2

7、初等数论习题解答使j = 51r+r1J l-sm类推知:2 22/51而b是一个有限数,.3we使Y*= O(Q上)=(伉r)=(切)=(2)=n÷l) = ，°) = CJ 存在其求法为(仏 b) = (b、a _ bs) = (a-bs,b- (a _ bs)s) = -A (76501,9719)=(9719,76501-9719×7)= (846& 9719 8468)= (125h8468-1251×6)= (3,1)=14.证明木节(1)式中的i log 2证:由P3§1习题4知在(1)式中有 = <- 而恋IbIl

8、og/?IogZ?2® log 2log 2§3整除的进一步性质及最小公倍数1.证明两整数a b互质的充分与必要条件是：存在两个整数s 1满足条件ax + bt = .as+bt = 证明 必要性。若(") = l则由推论1知存在两个整数s I满足：as + bt = (a,b)9 充分性。若存在整数s, I使as+bt=L则a, b不全为0。又因为 a.b)aa,b)b.所以(a,bas+bt) 即("")11。又(a,b) > O . (a.b) = 12.证明定理3定理3 qa心=q , H证：设al,a2,-9afj = fnl.

9、则y I “(, = 1,2,，).ly Il 叫(i = l,2,")又设Iq 1,1绥 ,%1 =加2则 m21 加o 反之若 I ai Il m2,则 Ui I InI, . m1 I n2从而“ =n2,即p2s=l1 IJa2 I*Jj, l23设anx11 + anxn + < + 1x + 0(I)是一个整数系数女项式且®r都不是零，则(1)的根只能是以“°的因数作分子以G7为分母的既约分数. 并由此推出血不是有埋数.证：设(1)的任一有理根为上，(",g) = l,g> 1。贝IJqan (),' + an- () ,

10、1 + + q L + 4()= 0q qq4” + % PZq + + q PCrl + a0qn =0(2)由(2) - (IIl Pn = pnxq + + «, Pqn-X + a0qn,所以q整除上式的右端，所以qanp又(阳)= hg>l所以(,) = 1,<Izi:又由 有(Inp,' + alpn-iq + + «,pq"i = -aQqn因为P整除上式的右端,所以PI aQqn (阳) = l,q>l,所以(/丿)= 1,：.PI an故(I)的有理根为上且paqan.q假设血为有理数.x = 2,.X2-2 = 0.次

11、方程为整系数方程则由上述结论可知其有有理根只能是±1,±2,这与血为其有理根矛盾C故J亍为无理数。另证.设为有理数迈=匕、（Pm = Xq>则 q22 = '. 2g- = p-、. （PJ、q） = （2g, /广）=cf >但由（p,g） = l,q>l知（/凡丁）= 1矛盾.故J不是有理数。§4质数算术基本定理1.试造不超过IOO的质数表解：用EralOStheneS筛选法（1）算出 100 = 10a（2）10内的质数为：2 3 5, 7（3）划掉2. 3. 5, 7的倍数，剩下的是100内的素数将不超过100的正整数排列如下：-

12、423-45鼻74011U134445U171920U2223242427293Q3112总3740414243U4647辿50斗525356575960616226466676U為71727374%n79SO飽災83陽89如Ul023£14.£15.9697IIKIm2.求 82798848 及 81057226635000 的标准式.解：閃为81848,所以81 A, A = 82798848 = 8x10349856 = 23×B,又 81856,所以 8B, B = 8x 1293732 = 2xC 又 432所以 4G C = 4x323433 = 2?

13、 X D又 91 (3+2+3+4+3+3)所以 9D D = 9× 35937 = 32 × E .又 91(3+5+9+3+7),所以 9IE E = 9x3993又 3993 = 3x1331 = 3x11'所以 A = 2835l I3：同理有81057226635000 = 23 3354 73 Il2 172337 »3. 证明推论3.3并推广到n个正整数的情形.推论3.3设a b是任总:两个正整数且a = Prl PlIPna y0 / = 1,2, .b = pH於,A0 i = X2,，k,则(a,b) = p$ P2 p? , a.b

14、= Pb Pfp?,其中i =min(.,71),= min(p7f), = 1,2,证：.升= min(y,A) 二 0齐 Saj,OS% “ Pi' I Pr，Pi' I pf, Q = I, 2 幻 ri* M, , ri,/-1J-IZ-Jr-1p?p$p I(a,b),又显然(a,b)lp$p?.p?. p?於p? =(a,b),同理可得 Pjp PY = ,b, i =maxai,i 推广设 4 =於 P伊Pkl，偽=P巴 Pin pj,Qn=Pi2 P 卜(其中",为质数j = 12,k,q为任意n个正整数i = l,2,",0j 20),则P

15、FPF Pp =(12s),y =nin., j = 2,kPW'P? =U，偽,心, =max.), j = 2kJ <i<n J4. 应用推论3.3证明§3的定理4 (ii)证：设a = pjpjp?, b = pp?P* ,初等数论习题解答 其中pg 小是互不相同的素数，, A (IGS)都是非负整数有(a、b) = PCPI 於， =mina门0 lGha,b = PrPt p?, , = maxq,闭,<i<koAkkIlb由此知(I)HWjpy =口譽也"35如=口严7 MJ从而有Ub =上/-r-1/-(“ 上)5若2n+1是质

16、数(n>l),则n是2的方幕证：(反证法)设n = 2kl(l为奇数)则 2,+l = 22</ +1 = (22k)y+l = (22A + i)22t U-I)- 22<(/_2> +l1<2? +1<(22A )z+l=2"÷l. 2“+ 1为合数矛盾，故n定为2的方拆.§5函数x,x及其在数论中的一个应用1.求30!的标准分解式解：30 内的素数为 2. 3, 5, 7 11, 13, 17 19 23, 293030303030T+F +F+F+F= 15+4+3+1+0 = 23y+y+y+，*,=6+1+0=7=

17、10+3 + 1+0 = 14+307QrU =+-=2+0=2弧30301130T?Ir301?30! = 2233,455.74 ll2132171923292/51初等数论习题解答2.设n是任一正整数 是实数证明:,ja .÷1+ +=W2/51证：设 = ？ 则由性质Ii知m <a<m + .所以Hmna<nm+n.所以HInna<nn + n .所以In H1 <m + 9又在m与m+1之间只有唯一整数m所以U & + 1(ii)证法一设一S a <、k =O,l,27-1,UU则 k na<k + ,.na = na +

18、k当i+kn-1 时. + -< + 1 + z ta + - = a； n Hn当 i+kn.2>a + - l,+丄= +1 ；H Hn.a + a + - + + & + - nn-liz-I-:W-I:= + -l=工a + -+ 工a + - (-011r-0,t-n= (n-k)a + k(a+l)= na + kr i驴+厂回 证法二L i令 <6z) = +-l-b1 + 1 /(Q + _)=工Q + 一,a + 1 f(a)Ufi1怛/+ fa + _)=工 + 一-na + 1 fa)()是以丄为周期的函数。H又、”I a 0,1)时 J() =

19、 O-O = 0,a 已 R、f(a) 0 ,H-I即工+ = ，KZ1。评注：证一充分体现了常规方法的特点，而证二则表现了较高的技巧。3设Q 0是任意二实数，证明：(i) lct-=ct-或-0 +1(ii) 2a+2j3a+a + j3+j3证明:(!)由高斯函数X的定义有a=a + r, = J3 + s,0 r <0s < 贝 IJa_P = -0 + -s,r-s < 1当 r-sia- = a-当 r-5< 0 时,- = a-故a-a-a-/3+ = a-(ii)设 a = a + x, = + y,0x, y < 1则有 OSX + y = + 0

20、 V 2下而分两个区间讨论： 若 OSx+y<l,则x + y = 0,所以 + 0 = + 0，所以2+2 = 2 + 2x+27÷2y= 2 + 2÷2(x+y) 2 + 2/? =«+0+ = M+ + /?+ 若 lx+yv2,则x + y = l.所以 + 0 = + 0 + l°所以2a+2 = 2a + 2x+2? + 2y= 2 + 20 + 2(x + y)2 + 27 + 2(x + l-x)=M + 0 + B + Ml + 2 + 2(x + )2+20+l=M+ + 0+0(ii) <证法2)由于, 0对称，不妨设a

21、2+20 = 2(+ )+2(0 + 0)= 2+20+2+202+2戸+ + 0= + 0 + ( + 0 + + 0)= +S+0 + 0= + + 0 + 04.(!)设函数f(%)在闭区间QxR上是连续的，并且非负，证明:和式J只切QCxR表示平而区域Qx?, 0<y /(x)内的整点(整数坐标的点)的个数.(ii)设p g是两个互质的单正整数，证明：(iii) Yir > Q. 是区域* + y2 r2 = 1 + 4r +8 工内的整点数.证明:(iv)设n > O. T是区域 > 0. y > 0, Xy n内的整点数，证明:=2 总卜而2O CX&

22、lt;n在n!的标准分解证明:（略）5设 Ii 是任一正整数，Kn = 0 +÷ -> P 是质数 OQi<P证明:式中.质因数"的指数是In _ SZlh =，卫-1其中 Sn = a0 + Qi + a2 + 证明：在n!的标准分解式中，质因数P的指数有限即n = 0 + QlP 十 a2p2 HF CltPt- 0 ai<p所以=(a1 + a2 + + QrPLl) + (q2 + a3p 4F QeL2) at=Ql 十 a2(p 十 1)十 a(p2 十 P 十 I)十1- at(f"1 + p?"2 十十 1)而7l =I

23、al(P -1)+ az(P2 _ 1) + 3 _ 1) + + at(pt -1)P 1 P-I=Qi + a2( 十 1)十 a3(p2 十 P 十 1)十十 at(r1 + pt2 + 十 1) h - nsP-I第二章不定方程§21习题IX 解下列不定方程 a)15x + 25y = 100b)306x 36Oy = 630解：a)原方程等价于：3x + 5y = 20 显然它有一个整数解Xo = Io,凡=一2 ,X = IO 5/E 为 一 + /®*)原方程等价于：17x-20y = 35显然它有一个整数解x0 =-7×35,y0 =-6x35X

24、= -7×35 + 20/故一般解为，(r = 0,±h±2)y = -6x35 + 17/2、把100分成两份.使一份可被7整除，一份可被11整除。解：依題总即求7x +Ily = IOO的正整数解.解得Xo= & V0 =4x = 8-ll一般解是：(Z = 0,±l,)y = 4 + 7但除/=0外无其他正整数解，故有且只有IOO = 56+443、证明：二元一次不定方程 t + by = M>0">0,b) = l证明:的非负整数解为或Ml N < 0时，原方程没有整数解，而+ l0故命题正确UN = 0时.原

25、方程有且只有一个非负整数解(0,0)而因为仏巧=1所以原方程有整数解(Xo,y0),yQ = (-l)nl g,g,LiM无=(T)"的，-IN其中："=切，？2,93,，9J 由于d>">0,故,y0中一正一负，可设X>0,y0X = X(I-bt Z、原方程的一般解是：(/ = 0.±l,)y=y0+at要求 XO-btO,yo+atO>-t 一山 ba仅十一巴是整数时，才能収t =否则t> 2kaa _a -故这个不等式的整数解个数T是:A ÷a1所以m)X = Xn -bt证明2：二元一次不定方程U + b

26、y = N的一切整数解为f, z,干是由X 0> VVo2 0 得-d4Clb勺或沪y = y0+at但区间的长度是,故此区间内的整数个数为 a bUb4、证明：二元一次不定方程 cx+by = Na,b) = 1 > 1,Z?> 1.当 N>ab-a-b时有非负整数解，N = ab = a = b则不然C证明：先证后一点肖N = ab-a-b时，原方程有非负整数解(勺,XJ则 = (m1,m2).=>?IXO + Iyo +1 => x0 +1 = bky yQ +1 = ah. k,h aab(k+h) = abk + h2 ,这是不可能的。次证，、“I

27、 N>ab-a-b时，W(a. b)=L故原方程有整数解(x. y0). 一般解是：；(/ = °,±h)要求X Obt O , y Q-CIt O =>-Az±L会证明存在满足这个不等式的整数r = r0可取使 a b0 = bt0 + r(0<r< b)于是对于这个有:X_bq = rb-=>tfy x-b + y0 + at0 y0 + (XO- +1)-(VO +-Ub + U) = -(N -ab + a) > -(Ub-a-b-ab + a) = -1bbbb.yo+troO=>ro-这就证明ClN>ab

28、-a-h时.原方程有非负整数解.1.证明定理2推论。推论0位圆周上座标都是有理数的点（称为有理点），可以写成2abZ 乙UU Cr b"、Z _b2xb (±E'±E)或(±K'± 声)的形式，其中“与b是不全为零的整数。证明：设有理数X = -9 y = - (m 0 )满足方程X2 + V2 = 1.即/2 +八=宀 于是得/ =Inm±2uhd H = ±(a2 一 h2)d 9 m = ±( a2 + b2)d 或 / = ±( 一 h2)J 9 m = ±2abd 9

29、m = ±(a2 + b2)d,由此得(x, y)= (±-2t/Z- £、二b亍)或(± "、二,± _占小=)。反之，代入方程Z + ),2= 1即知 Cr + Ir Cr + ZrCr + IyCr + Ir这样的点在单位圆周上。2.求出不定方程X2 + 3y2 = z1.x.y) = l,x>0,y>0,z >0的一切正整数解的公式。 解：设不定方程x2+3y2 =z2 y) = 1有解则(1) 3/z-x 或 3/z+x 因为3y' = Z2 -X2 = (Z-X)(Z+ x)=> 3/(Z-

30、X)(Z+ x)=>3z-x或 3/Z+X2 + 3：222 Z + X / 十土 2 ( Z-X卩一Zdy- 3 ° H或者y (z+)- 3得 3/z + x 或 3/z-x以下不妨设3/z + x (x,z) = L 设(x,z) = d,则 dx,dz =>d3y2 = z2-Xy若,3",=>9,9z'=>93j=>3y =>3(x,j)与(x,y) = l 矛盾! 这样(3,d) = l =>d Jfndy(.d'3y j 而"x=>d(x,y)=>" = 1 (z+x,Z

31、-X) = I 或2,设=(z+x, Z-X)=>"(z+x)-(Z-X) = 2x,(乙+x)+(Z-X) = 2z=>"(2x.2z) = 2 即 / = 1或=2 若(z + ,z-X) = 1,则,Z-Xj = I, 从而 3jf = (z+)(z- X)=> y =苇丄(z_x)Z + X22由引理可设 =CI y Z-X = If.y = ab从而三，为证得X, z为整数 (XM) = 1,必须有a , b均为奇数.且36z2>72若(z + x,Z-X) = 2=>z + x Z-Xz + x Z-X=1Z + X Z-X6=3d

32、a2 9 z + X = db2,K ( i )当 J=I:J b同为奇数：(H)：1 3 / Z> u、b 一 奇> O. (., y) = 1。从而 3jf = (z + x)(z_x)=> = 2 >设= Ci =从占=ab>BPX = 3/-/?；y = 2ab、z3a2+h2.o22其中匕为一奇一偶，且有(a.b) = 4. 解不定方程：X2 + 3y2 = ZIf > 0» y > 0 z > O. (x, y ) = i o解：设(Z - Z ÷ x) = J9 易知 d = I 或 2。由(Z - X)(Z +

33、 ) = 3y2 得 Z-Xy = dab 或 Z-X = Jb29 z + x = 3da2 9 y = dub» </ > 0. ft > O» (, b )=b2-3a2I b2+3a2LX =, y = ab, Z = u > O, b > O9 (u")=, 3 J z>,2 2当 J = 2： JV = I/?2 一 3</2L y = 2"b z = Z>2 + 3/, “ >0, b > O. (u, b ) 一偶。反之，易验证(i )或(ii)是原不定方程的解.且X >

34、O, y > O. Z : 3.证明不等式方程+y1 =乙：(忑刃=1* > °，y > z/*的一切正整数解.可以写成公式：X=ab(ai) y= I a +b 6a b 1 = a +b其中 > O,/? > O,(,b) = 1卫,/? 一单一双证明:由定理1知道原方程的解是X = 2cJ, y = Z = c' + dc>d>O,(c,d) = 1 且c, d为一奇一偶，其中，C = 2ab. d = Cl l)> b> O,(d,b) = 1,且 a b 为一奇一偶.所以X=4ab("b)、y = &#

35、39; a"+/?"丨，Z = Cl +b是原方程的正整数解(x > 0, y > 0, Z > 0, (x, y) = l,2 Xy 且q2+/是奇数,原方程正整数的解有：(0,0,0), (,±,±) ' (±,0,±) (±4b(-b),±(°+/-60方)，±(/+閃) (±(+Z-6T)'±4"(c-/)'±( +b)6.求方程X2 ÷ y2 = Z4的满足(a-, y ) = 1 , 2 X的

36、正整数解。解:设, y, Z是Z +尸=卍的满足(, y) = 1 . 2 Ix的正整数解，则Y = lab. y =亦一辭， Z2 = a1 + b2 9 a > h > Of (a, />)=1» a, h 一 奇一偶，再由 Z2 = u2 + Z>2 得 “ =2“ 卩 b u1 - f2 9 Z = K2 + V2 或 a U2 - v2t b 2uV z = w2 + v2» m > “ > 0 (w, v) = 1 » w, V 一 奇一偶, 于是得 X = 4WV(Ul 一 V2), y = Im4 + v4 -

37、6w2v2l, z = w2 + v2, u > v > 0» (Mt V)=If u9 V 奇 一偶。反之，易验证它是原不定方程的整数解且X > 0. y > 0, Z > 0, (.y)=l, 2x° 其中正负号可任总选取.第三章同余1同余的概念及其基本性质1、证明若A闵.T Bg申(Hiodm)Xf y(InOdnI)X i=l, 2八、，k则 AarXr Ba* )* (modm) °鸟a,®特别地，若 Cli bj (InOdm)> i=0. L ,/?则anxn + W心 +fl0 bnxn + ,1x1

38、+ + (modm)(ii) 若 ab(modm), k > Oak bk(mod Hlk(iv)若 ab(modm), (Illn, d > 0则 ab(modd)证明:据性质戊由Xi yr(modm), = 1,2得Xj三淨(mod加),Z = 12北,进一步，则A1g<矿三 Baai.心)f 必(InOd m)最后据性质丁 可得： Aq皿片Xy三工B务兔* yj (Hiodm) (ii)据定理 1，a三b(modm)=> “幺一方，. k > 0,.InkIk(CI-b) = ka-kb又据定理1，即得ka A:/?(InOd 虫)(iii) 据定理 1&#

39、187; ab(modm) => nia b、HP a-b=ms(s Z)(iv) 据定理 H ab(modm) =>a-a = ms,(S z),又. dm, . m = dt, fez,故a-b = ms = d(st),st Zy. 三 b(mod )2、设正整数a = an0n+ 4-10"'1 +.o,0<10nr试证H整除的充分且必要条件是11整除丫(一1)务/-证明：1O三一l(modll),由上题的特殊愴形立得a+d-J。"" + °o 三 6(一1)" +卩一(一I)Z +0(mod 11) 6(-l

40、)r(modll),J-O 11/a o 13找岀整数能被37, 101整除有判別条件来。解：1000 三 l(mod37)故正整数 = 1000a+OOOZ +. °, 0 S Q < IOoo立得37/g ovl-l(modl01).故设正整数 a = bs100s+ bs_. 1 OoZ +.i0<100', 立得 101ol01f (1)色./ /-(>4、证明 641 I 2*2 +1证明：. 2s 256(mod641) 2,6 2562 =65536154(mod641)232 1542 =23716-l(mo<l641)即641 I 2

41、32 +l 5、若“是任一单数则 Cr l(mod2n+2). (h1)证明：(数学归纳法)设a = 2m + (1) H = I 时，a2 =(2m+l)" =4m(m+l) + l l(mod8),结论成立。(2) 设n = k时，结论成立，即：(2w + l -I(mod2*+2)=>(2w÷l)2, 一1 = 2“勺，(z) 而产,-1=( -I)(Z +1) = (Z -1)(-1-2)=(2A+2r)2+22A+2= r2.22*4+r2*+3= r2+3(r21+, + l)三 0(mod23)故II = k +1时.结论也成立:/. l,结论也成立。证

42、明：若2仏”是正整数则l(mod2f(4)设“ =2£+1,当”=1时，有Cr = (2Jt+ I)2 = 4k(k + 1)+ I 1 (mod2叽 即式(4)成立。设式(4)对于nk成立，则有Cr 1 (mod 2fc + 2) =>Cr = 1 +r2*2t 其中徑Z所以'" = (l +“2-2)2= 1 +/2“3 三 1 (mod 2* + 3). 其中/是某个整数。这说明式(4)n = ÷ 1也成立。由归纳法知式(4)对所有正整数n成立。(/)1535625：(/7)1158066解：(/)1535625 = 33×54

43、15;7×13:初等数论习题解答 (7)1158066 = 2×3272×13×101§2 剩余类及完全剩余系1、证明x = u +p5v. W = OJ,2-h ts是模的一个完全剩余类。证明：显然对",y的不同取值，X共有 / = P个值，故只需证这样的/才个值.关于模'的两两互不同若 UX + Ps U2 + /广”岭(mod PS)=>Ml -U2 PZ (气 一 v2)(mod PS)=> P T Ml _U2，即z1 U2 (mod P j => z1 = u2=> Pfl 7'v2

44、 (mod p')=> 片三 v2 (mod p:) => =匕. Ml = U2 或 VI V2 时,Wl + p'f U2 + P f 2 (mod /h )结论成立。2、若叫叫叫是R个两两互质的正整数,召旳入分别通过模Wrwl2.saMA的完全剩余类 KlJMlXi +M2x2 + + M內通过模"加2耳=m的完全剩余系其中Jn = IniMi. i = 1,2证明：(数学归纳法)(1) 根据木节定理3知R = 2时.结论成立。(2) 设对整数k-9结论成立，即若ph2.z1两两互质令5 = l + M2X2 + - + MXk .MlXPX2s-V

45、A-I分别通过模m1,m2,、叫J的完全剩余系时,d必过模m = mAml.nk 的完全剩余系，其中 miMi = m (/ = 1,2k 一 1)。现增加",使(X, Ink) = 1 (i = 1,比一1),令 MJ = MKmk (l,.k _ I), m = Mk = “-L-，m =叫MR = nxtn1.mk则易知(n1, nt2., mk) = (Jnk .Mk) = 1 2/51初等数论习题解答XX +mxx2 + m, n1x3 +. + rnx, n2. Inkxk通过模InXJrlI,mk的完全剩余系。证明：(数学归纳法)(1) K = I时，西,兀2分别过模m

46、,n的完全剩余系时,XI + “丫2共有tm2个值，且若Xl + /MrV2 x + InAX,1 (mod nxn1) => WZl (x2 一 x；)三 x； Xl (mod mm2)=>tnlx-xl,且x2-x,1 -_ (modm2)=> x= x 9 x2 = Xrl,即 k = 2 时结论成立：(2) 设¾x2,x分别过模m2,，f 的完全剩余系时PX2 + Ht2X3 + m2m3InkXk过模tn2Ink的完全剩余系。因为(h1 ,InlS) = 1 ,由木节定理2得，ml (XI + m2x3 + m2UIkXk)亦过模n2Ink的完全剩余系。、

47、”I xpx2,Xk分别过模InI,m2,，Ink,mk的完全剩氽系时.2有mg叫个值,且据归纳假设若召 +/W1X2 + + % "2-2耳-I +wi -lx + 片x； + + rnx InkiXfk + 1 InkXtk(modInA 叫)=> xl = x(mod m) S Xl + InlX3 + + n2 mkxk x； + n2xy + + m2 tnkxfk (mod n2 L)=> xl = x；(modm), x2 = x；(mod n2),，Xk = x (mod mk)=> x1 = Xj , XI = x ，Xk=X,f,o所以州+mlx

48、2 + + “加2 g-忑过模ItIXnII-nk的完全剩余系。3简化剩氽系与欧拉函数1. 证明定理2：若弘吆卫如）是砍?）与加互质的整数.并且两£对模川不同余，则p2.）是模加的一个简化剩余系。证明：5心，4如）两£对模加不同余所以它们分别取自模加的不同剩氽类，又弘，磧恰是0（加）个与加互质的整数，即它们恰取自与模川互质的全部剩余类。2. 若加是大于1的正整数，是整数，（么2）= 1，通过加的简化剩余系.= -（m）,其中表示展布在§所通过的一切值上的和式。2g证明：由定理3知，§通过川的简化剩余系：其中 O<g<m 且（气,加）=1 ,而

49、 * f = （, = 1,2,。（也）。ITnJ m若In >2,则（m）必是偶数，又由（q,?）= 1,得(m -ai.m) = 1,且易见HI -ai ai,左边每一项都存在另一项3(i)证明。(1) + 0(")+ 0(/尸)=/产，P质数。(ii)证明0 (CI) = a.其中艺 展布在a的一切正整数上的和式。 dad/a证明：(i)因为 0(/)= /一/"，伙= l,2,)所以。+ 0( p ) + + /(/)" + (" “ + ("/"+ + (/ "I)=Z(ii)设a = Pr 咱Pkak是a的

50、标准分解式，则 2 = (1 + 门 + + ?Ial)(1 + P? + + Py)(1 + 仇 + + Pkak) rf-工0(d) = (l + (p)+0(°f)(l + (pJ + +(0/) d/a= PFP严PkttI=a4.若“，*，"是k个两两互质的正整数 r,.分别通过模WPw22ha的简化剩氽系，则M+M22Mkk通过模7w1m2 njt =加的简化剩余系.其中加=叫MJ = I,2,k o证明：(数学归纳法)(1) 由定理4知k=2时，结论成立：(2) 设kl时结论成立，艮卩/ = ?". ="M,(j = 1,£一1)

51、 ,fes-分别过模加,L.时. = Mx +Af2 + + M- .过7'模的简化剩余系。显见(nmk) = 9则又由定理4知，Ink + Mkk通过模m,mk的简化剩余系，注总到:mk = (lnkMl )§ +mkM1 ) + + (叫M-I)乩= 2W1+22+ + 乩所以,MMl +M22 + + M应通过模m的简化剩余系。44.欧拉定理费马定理及其对循环小数的应用1、如果今天是星期一，问从今天起再过l""天是星期几？解：若IO1"" +1被7除的非负最小剩余是r,则这一天就是星期厂(MZlr0时是星期日).V(IO7) =

52、1.由费马定理得10°三1 (mod7).又.10-2( mod 7)=>101o(-2)'°=454( mod 6).JO K)=6K + 4 (KeZ) 10,1)Io +1 = 106+4 + l104 + l34 + l5 (mod 7)即这一天是星期五.2、求(1237156+34y被Ill除的余数。解：.lll=37x3.0(lll) = °(37)0(3) = 36x2 = 72,1237136 1 (mod 37)IA据欧拉定理.易知.1=> 1237136 l (mod 111)1237136= (12371)1 (mod3)J.1237156 123712° (mod 111)( 1 )又12371lll2+50 12371 50 (mod 111)故. 123712 502 -53 (mod Ill)=>. 123714 532 34(mod 111)n 1237ls46 (modIlI)=> 12371,6 7 (m