《初等数论》版习题解答

1、第一章整数的可除性§整除的概念带余除法1 证明定理3定理3 若ai, a2,川，an都是m得倍数，q, q?,川，qn是任意n个整数，则 5印 +q282+11( + qnan是 m 得倍数.证明： ai,aH, an都是m的倍数。二 存在 n 个整数 Pi, P 2, i 11 Pn 使 ai = Pim, a2 = P2m, HI , an = Pnm又qi,q2,川，qn是任意n个整数二 qiai 中 q2al(=qiPim 壮2P2m +i|+qnp.m= (Pi q +q2P2 +川 + qn Pn)m即qiai +q2a2十川+qnan是m的整数2证明 3| n(n +i

2、)(2n +i)证明 Tn(n +1 )( 2+ I今 n n：+ IrH +2i -=n( n +1 ) (n + 2n( n) n(+又、:n(n +i)(n +2), (n i)n(n +2)是连续的三个整数故3| n(n +i)(n+ 2), 3| (ni)n(n+i)二 3| n(n +i)(n +2) +(ni)n(n +i)从而可知3| n(n+1)(2n+i)3.若axo+ byo是形如ax+by （x, y是任意整数，a, b是两不全为零的整数）的数中最小 整数，则(axo +by0) |(ax +by).证：7a,b不全为0i / 77二在整数集合S =ax+by |x,y

3、亡Z中存在正整数，因而有形如 ax+by的最小整数 axo +byoVx, y 迂 Z，由带余除法有 ax+by =(ax0+by0)q+r,0 < r cax0+by0=(x X0q)a+(y-y0q)b 亡 S，由 ax +byo是 S 中的最小整数知 r=0二 axo+by0 | ax +by/. axo+byo |ax +by ( x, y 为任意整数)二 axo +byo |a,axo + byo | b+ byo|(a,b).又有(a,b)|a(a,b)|b(a,b) |axo+byo 故 ax。+byo = (a, b)4.若a, b是任意二整数，且bHO，证明：存在两个整

4、数 S, t使得a =bs +t,|t I兰罗成立，并且当b是奇数时，s, t是唯一存在的.当b是偶数时结果如何?证：作序列III,-23忖b|,冬凹b|,塑,I i I则a必在此序列的某两项之间即存在一个整数q，使q2号b，则有(i) 当q为偶数时，若b >0.则令s =9 ,t = a -bs = a -2, q ,bb V = b 1t < qq0 兰a bs =t=ab=a 22若b<o则令s 蛙-一心*咿，则同样有q +1(ii)当q为奇数时，若b0则令s =2q +12 b，则有2 / 77q+1q+1b =a 2 2bb c0”.t < 2若b<0，

5、则令s竽,，宁b，则同样有t <2 综上所述，存在性2 ,得证.下证唯一性=bs +t =bs, +1 贝y t -t,=b(s -s)| >|b|bbt < , 1 <”".t t<t +t1 <b当b为奇数时，设当b为偶数时，s,t不唯一，举例如下：此时而矛盾故 s = s,t =ti3 b=b 1 +b =b ”2 + (-b),ti =2 2 2§最大公因数与辗转相除法1. 证明推论4.1推论4.1 a, b的公因数与(a,b)的因数相同.证：设d '是a, b的任一公因数,由带余除法a =bq +ri，b+2,川,站Zn

6、 +站4rn qn 十，0 = rn+<rn crn4 vHI <rb二(a,b) =rn二 d '|a -bq, =ri, d'|b -32,d'g=rn4qn +rn即d '是(a,b)的因数。b一一<t=a-bs=a-213 / 77反过来（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. 应用§习题4证明任意两整数的最大公因数存在，并说明其求法，试用你的所说的求 法及辗转相

7、除法实际算出（76501, 9719）.文档来自于网络搜索解：有§习题4知:bVa,b 亡 Z,b H0, 3s,t 亡 Z,使 a =bs+t,|t |兰一。，2/.3 Si,t1，使 b =s1t +1,|1 |<山 <2,Hh如此类推知:222=tnSn +tn；sn 卅，tn 卅，tn A tnsn + 十人十;且|tn戶罗 罟胡卜岁 屛而b是一个有限数，”.3 n忘N ,使tn十=0(a, b) = (b,t ) = (t ,ti ) = (ti,t2)11 = (tn ,tn 十)=(tn,0) = tn，存在其求法为:(a,b) =(b,a -bs) =(a

8、 -bs,b -(a -bs)Si) =|(二(76501,9719)= (9719,765019719x7)= (8468,9719-8468)= (1251,8468-1251x6)-IN= (3,1)=14 .证明本节（1）式中的n log blog 2证：由P3§1习题4知在（1）式中有0 =rn+ <rn <匕2丄 <号<H）兰守:王兰2n，而rn>"兰X*2 b， I引0gb=罟2即Jogb"log 2§整除的进一步性质及最小公倍数1.证明两整数a，b互质的充分与必要条件是：存在两个整数S, t满足条件ax +

9、bt =1 .证明 必要性。若（a,b） =1,则由推论1.1知存在两个整数s,t 满足：as + bt = (a,b),”as + bt =1充分性。若存在整数 S, t使as+bt=1，则a, b不全为0。又因为 (a,b)|a,(a,b) |b，所以(a,b|as +bt) 即(a,b)|1。又(a,b) >0 , . (a,b) =12证明定理3定理 3 也 a211L an 】=a1 |,| a? 1111 ,| a* | 】证：设a1,a2,川，an =m1，则 a ImN =1,2,川，n)|ai |m1(i =1,2,川，n)又设| a11,| a2 |H,| an |

10、=m2则 m2 I m。反之若 I ai II m2，贝U ai |m2 , /. m1 | m2从而 g =m2，即a1,a2ll,an = | Q |,| a2 |ll,|an |23.设 anxan4.xn 1(+a1a0是一个整数系数多项式且 a。, an都不是零，则（1）的根只能是以a。的因数作分子以an为分母的既约分数，并由此推出 J2不是有理数.文档来自于网络搜索证：设（1）的任一有理根为 P,（P ,q）=1,q>1。则qn.n 丄 .ibj,n_1. n .（2）naoq,anP +an 丄 p q+m+ai pq "+aoq =0由（2） -anpn =an

11、jLpn丄q +ill +a1 pqn+所以q整除上式的右端，所以 q | anpn，又（p,q） =1,q :>1 ,所以（q, pn） =1,. q |an ;又由（2）有 anPn +anp2q +川+印pqn=aoq"因为P整除上式的右端，所以P |a0qn ,（P, q）=1,q:>1，所以（qn, p）=1,二p | an故（1）的有理根为P,且p | a0,q | an。q假设 逅为有理数，X =X2 -2 =0，次方程为整系数方程，则由上述结论，可知其有有理根只能是±1,垃，这与 运为其有理根矛盾。故 72为无理数。另证，设迈为有理数72= ,

12、（p,q） =1,q >1，则q22=.2q2 = p2.（p2,q2）=（2q2, p2）=q2 >1 q但由（P,q） =1,q A1知（p2,q2） =1，矛盾，故运不是有理数。§质数算术基本定理1.试造不超过100的质数表解：用Eratosthenes筛选法（1）算出 J106 =10a（2） 10内的质数为：2, 3, 5, 7(3)划掉2, 3, 5 , 7的倍数，剩下的是100内的素数将不超过100的正整数排列如下:J23-45-67-8-910111213141516174819202122232425262728293031323334353637383

13、94041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991002 .求 82798848 及 81057226635000 的标准式.解：因为 8|848，所以 8| A, A =82798848 =800349856 =23x B ,又 8|856,所以 8|B, B =81293732 =23xC ,又 4|32,所以 4|C, C =4咒 323433 =22 咒 D又 9| (3+2+3+4+3+3 )

14、,所以 9|D, D =9 35937 =32 x E ,又 9| (3+5+9+3+7),所以 9|E, E=9x3993又 3993 =31331 =3勺13所以 A =28 351 13;同理有 810572266350023 33 54 73 112 17 ”23 畅。3证明推论3.3并推广到n个正整数的情形.推论3.3设a, b是任意两个正整数，且ill 9綁,0 , i =12lll,k ,HI,Pi 30 , i =1,2,111, k ,则(a,b) = p/ 9$ 川 Tkk , a,b = pP 卩P 川 p?,其中 Yi =min(8, Pi) , 5mi"(用

15、),i =12H|,k证： Yj =min(的，Pi)，二 0 <社 <%,0 <耳 < PiPih Pi3 p/| pP(i =1,2H|k)r；Pilp，口 P5P.i 1推广502打 11 Pkk |(a,b),Pi P2 川 Pkk =(a,b),又显然(a,b) | p/p22川 Pk；同理可得 pPpP川 pP =a,b , i =maxai,Pi设a1pPhi pF ,a2 = pFppill pk2k JH,a pF1 ppill pN（其中Pj为质数j =12川，k,ai为任意n个正整数i=12ill,n,Pij >0）,p/p 111 Pk&q

16、uot; =(a1, a?, 111, an), Yj = mn Pj, j =1,211*P?P$ Hip衷=a,a2,ill,an, 6j maxij, j =1,2,M,k4 .应用推论3.3证明§3的定理4 （ii）证：设 a-pUpfillpJ, b = p1yi)|pkB ,其中P1, P2,，Pk是互不相同的素数，8, Pi (1 <i <k)都是非负整数，有(a,b) = pApf山 pE,=mi门6,人, 1 2 兰k,a,b = JpF山 pF,气-maxSA, 1Wi<k。Pk ,由此知（a, b）a, b =n p严=n卩罟厲用怖心，直i#i

17、 zt=n p=ab；从而有a,b=ab-V(a,b)5 .若2“ +1是质数（n>1）,则n是2的方幂.证：（反证法）设n =2k|（|为奇数），EH,c2k 卜，,"c2k、l,八 rc2k (I 4)则 2 +1=2+1=(2 ) +1=(2+1)21_222)+|H+12k2k ln1 <2 设n是任一正整数，a是实数，证明: +1 <(22 y +1 =2n +1 ,- 2n+1为合数矛盾，故n定为2的方幂.§5函数x,x及其在数论中的一个应用 1 .求30 !的标准分解式.解：30 内的素数为 2，3，5，7，11，13，17，19，23，29

18、27 / 77+川«2 =15 + 4+3+1+0 =23口3 =+汕( =10+3+1+0=14+111 =6+1+0 =7閉+冏+川十“4,%卡卜辞卜川=2+0=2罟惰M=2+O=2 ,%3鴉H計川=2+0 = 2or a Ct Ct 1 叫一519 -“23 529 一 I2314542230! =235 7 11 13 17 19 23 29(i)证:如+卜+¥卜+卜+凹(i)设a = m.则由性质 II 知 m<acm+1.所以所以nm <not cnm + n，所以mc m +1，又在m与m + 1之间只有唯一整数m, n所以LU =m =a.nkk

19、 +1(ii)证法一设兰2 < ,k =0,1,2,川,n-1 ,nnn "1勻十；贝y k < na c k +1,”订 not = na + k 当 i +k <n 1时,a +L£k+2:f (G +)a +niT 中| n当i +k >n时,2 >a +丄 n5 切,a+丄=a+1;n1n 1B +o +川+«+nnn1 n A-kjn+ -n=£ a + = S a+- + £ aiTni _0n izB_k=(n- k)B+k(G+1)=n a +kn -1/. Z a +丄=2i =0n证法二n A.

20、令 f (0)二艺G +丄-na,i zQn山2 +1三 f (Ct)n12；f (G + ) =2； ani z0+-na +1三 f (a) n1二f(a)是以丄为周期的函数。n又当 a <0,1)时，f(a) =0-0=0,.a< R, f )三0 ,即 Fa +1 =na。ix n评注:证一充分体现了 常规方法的特点，而证二则表现了较高的技巧。3.设a, P是任意二实数，证明:(i) a - P =a - P或a -P中1(ii) 2a +2 P >a +a + P + P证明：（i）由高斯函数 凶的定义有a =a +r, P = P +s,0 <r <1

21、;0 <sc1。贝Ua P 斗 ot P十 s ,-s<1当 r -S>0时,a -P =a-P当 r -s<0时,P -P=aP1故a -P =a P或aP+ 1=aP(ii )设 a =a +x, P =P + y,0 <x, y c 1,则有0 <x +y = + P <2F面分两个区间讨论:若0<x +y <1，则x+ y=0,所以俾+ P二匕+P，所以2a +2 P =2a +2x +2 P +2y = 2a +2P +2(x +y) >2ot +2P= a + P + P +a = a +a + P + P 若 1<

22、x+y 2，则x+y=1，所以口 + P =a+P+i。所以2a+2P =2W+2x +2P+2y= 2a+2P+2(x +y)二 2a+2P+2(x+1-x) a亠二切+P +P +引+2 +2(x +-X) >2a+2P +1=a +a + P +P(ii)(证法2)由于a, P对称，不妨设a3P2W+2P =2(x+a) +2( P +P)= 2a+2P +2a + 2 PX2a+2P+a + P=+P+(+ P +a+ P)=a+P+a+a +P+ P=a +a + P + P4. (i)设函数f(X)在闭区间Q <x<R上是连续的，并且非负，证明：和式工rw5。胡表

23、示平面区域Q<x<R , 0<:y<f(x)内的整点(整数坐标的点)的个数(ii)设P, q是两个互质的单正整数，证明:pl q-1亠/ 0<y4(iii)设r>0, T是区域x+y<r内的整点数，证明:r = 1 + 4r + 8 J 护一蚪(iv)设tt>0, T是区域工>，y>fl，xySn内的整点数，证明：文档来自于网络搜索22 L0<x<%nn_ X *证明：（略）5.设n正任一正整数，且n = Go + flip + a2j/ + -*, p是质数，0旳P，证明：在!的标准分解式中，质因数 P的指数是文档来自于

24、网络搜索h=p 1其中必二口0 +的+ a 2+证明：在n!的标准分解式中，质因数 P的指数有限，即« =尙 + flM?+ fl2p + + flfP 0 < 旳 <p所以71+护+-71h=-二 1 +fl却+、 + a#7)+ 2 + 口3啓 + 应Pg)+ 就二的+如®+1) +的肝+ P + D +如曰+ pL2 +1)n-S 1=-ai(p - Q + a 血;-1) +_ + F + ajy -1) P 1 P 1二血+的©+1) +対矽+ P + 1) +卯曰+ pL2 + +D几P=1第二章不定方程 §2.1习题1、解下列不

25、定方程a)15<+ 25 1 0 0b)306x360y =630解：a）原方程等价于:3x +5y =20显然它有一个整数解X0 =10, y。= -2 ，故一般解为x = 1 0- 5 fy 2+3t(t =0土 1, 12,)b）原方程等价于:17x -20y =35显然它有一个整数解x0 = -7 X 35, y0 = 6 X 35故一般解为IX = 7 X 3 5 20y=-6沢35=0±吐図,2、把100分成两份，使一份可被 7整除，一份可被11整除。解：依题意 即求7x+11y=100的正整数解，解得沧=8, y0=4lx =8 -11t一般解是：" ”

26、（t=0,±1川）y=4 +7t但除t =0外无其他正整数解，故有且只有100 = 56+443、证明：二元一次不定方程ax+ b尸 N a-0 , b0, （ a炉的非负整数解为证明：当N<0时,原方程没有整数解，而N'l + 1<0故命题正确Lab J因为=0时,原方程有且只有一个非负整数解（0,0）而Jj=0卜1=1LabLab(a,b)=1 所以原方程有整数解(X0,y0 ), y。=(-1)2福1,川,qN,X0 =(T)nq2,|l|,qjN44川Lqn ，由于 a >b >0，故 X0,y0 中一正一负，可设 x >0, y <

27、;0原方程的一般解是：-bt（t =0,±1川）.y = y。+at要求 X0 -bt >0,y0+at >0= x0>t >-血，ba仅当-沁是整数时，才能取t =-血,否则t>-必aLaLa故这个不等式的整数解个数 T是：当是整数时T =当1°不是整数时Ta+1所以申(m)中1i+1卡卅+1因而厝卜因而I x x bt证明2:二元一次不定方程ax +by = N的一切整数解为4 - 0 ，Z，于但区间卜血，直的长度是A，故此区间内的L a baby = yo +at是由x > 0，y > 0得一兰仝0a b整数个数为或 + 1。

28、文档来自于网络搜索ab ab4、证明：二元一次不定方程ax+by = N,(a,b) =1,a ：>1,b >1，当 N>ab a-b时有非负整数解， N =ab=a=b则不然。证明：先证后一点，当N =ab-a-b时，原方程有非负整数解(x0,y0)则 d =(mi, m2).=b x0 +1,a y0 +1二 x0 +1 =bk, y0 +1 =ah,k >1,h >1=ab(k+h ) = ab, k+h 2，这是不可能的。次证，当N>ab-a-b时，因(a,b)=1，故原方程有整数解(x0 ,y0)，般解是:二二(t = 0, ±1川)要求

29、X 0 -bt 30，y 0 -at > 0 =-直兰t < 会证明存在满足这个不等式的整数t = t0可取使a bxo =bt0 +r(0 <r cb)于是对于这个to有：文档来自于网络搜索X bt0 =r <b 1 二 t0 r b +1 ba111y0 +at0 > y0 +-(x0 b +1)(by。+ax0 -ab +a) = (N -ab + a) > (ab - a - b -ab + a) = 1 bbbb/. y。+at0 >0= t。> 匹a这就证明了当N Aab-a-b时，原方程有非负整数解.1 证明定理2推论。推论 单位圆

30、周上座标都是有理数的点（称为有理点），可以写成（+J2aL 十土）或（+士 +3）2斗2 7 - 2斗2丿人2小2，- 2小2丿a +ba +ba +b a +b的形式,其中a与b是不全为零的整数。于是得设有理数,y=- ( mH 0 )满足方程x2+y2 = 1 , mml = ±2abd , n = ±(a2 b2)d , m = ±(a2 + b2)d 或 l = ±(a2 -即 I2 + n2m2,b2)d , m = ±2abd ,2ab»。反之，2 2 2 2m = ±(af b'M，由此得(x, y)

31、=(土朮-霁討或(±0+代入方程X2 + y2 = 1即知这样的点在单位圆周上。文档来自于网络搜索2.求出不定方程X2 +3y2 =z2,（x, y） =1,x >0, y >0, z >0的一切正整数解的公式。解：设不定方程X2 +3y2 =z2 ,（x, y） =1有解则2 2 2(1) 3/z-x 或 3/z+x 因为 3y2 =z2 X2 =(z-x)(z + x)=3/(z-x)(z+x)= 3/z-x或 3/z+x2 2 2 2x +3y =z = y得3/ z +x或3/ z-x=4 fz-X)或者 v2=(z+x)q3y3以下不妨设3/z+x2 2

32、2(X,z) = 1 ,设(x,z 冷则，d/x手 d/zy 吆3 x,2 2 2若,3/d,= 9/ X ,9/z = 9/3y = 3/y = 3/ (x,y 卢(x, y ) = 1 矛盾!、 2 2 2这样(3,d ) = 1= d / y = d /yC>'d /3y )而 d/x= d/(x, y 戶 d =1 (z +x,z -X )=1 或2 , 设t =(z + x,z-x 戶 t / (z + x) -(z-x) =2x ,t/(z+x)+(z-x) =2z= t/(2x.2z ) = 2 即 t =1 或t =2 若(z+x, z-x) = 1,贝 1 _

33、,z x ' = 1,V 3丿2 2 z + X从而 3y =(z+x X z-X 戸 y = (z-x)3由引理可设Z +X22,=a, z-x=b,y=ab2229 / 77从而三，为证得x,z为整数，（x,z） = 1,必须有a ,2 2b均为奇数，且3a >b若(z+x,z-x) = 2 =i+x z-x=1J从而 3y =(z+x)(z-x 戶=、八 z +x 2 z -X 2 y 北 设r,二bFb,即 z + x) = d ,易知 d = 1 y = dab 或 z - x = db2,2 2 - -=3a "b ,y =2ab,z =3a 中b，其中a,

34、b为一奇一偶，且有（a,b） = 14 .解不定方程：X2 + 3y2z2,y > 0 , z > 0 , (X, y ) = 1 。文档来自于网络设(z -=db2,z - x = 3 da2,b > 0 , (a, b )2。由(z -x)(z + x) = 3 y2 得2x = 3 da , y = dab , a > 0 ,y=ab,z=S> 0 , (a, b )=lb , a,b同为奇数；（ii ）2 2d = 2 : x = | b - 3a |,y = 2 ab ,a > 0, b > 0 , （a, b ） = 1 , 3 .|b,

35、a, b 一奇一偶。反之，易验证（i ）或（ii ）是原 不定方程的解，且X > 0 , y > 0 , z > 0 , （X, y） = 1 。文档来自于网络搜索2243.证明不等式方程 X +y =z ,（x, y ）=1,x >0, y>0,z/x的一切正整数解.可以写成公式：X =4ab(a2-b2), y = I ab6a2b21，2 2z = a +b其中 a AO,b AO,(a,b )=1,a, b一单一双2 2 2证明：由定理1知道原方程的解是x=2cd,y=c -d ,z=C +d c>d :>0,(c,d ) = 1 ,且 c,

36、d 为一奇一偶,其中，C = 2ab, d =a2b2,a >b >0,(a,b )=1 ,且a, b为一奇一偶.所以X_ _ _ _ 2 2=4ab(a "b ), y = I a +b 'a b i， z = a +b是原方程的正整数解2 2(X >0, y aO,z aO,(x, y )=1,2/X,且a b 是奇数，原方程正整数的解有：2222442222(o,0,0)(0, ±a,±a)，(±a,0,±a)(±4ab(a-b)(a*b 一6ab )(a b)，44222222(±(a +b

37、 "6ab)，±4ab(a b)，±(a +b)，6 .求方程 X2 +y2 = z4 的满足(X, y ) = 1 , 2 |x的正整数解。解：设 X, y, z 是 X2 + y2 = z4 的满足(x, y) = 1 y =a2-b2, z2 = a2 + b2, a > b > 0 , (a, b) = 1,2 Ix的正整数解，贝y X = 2 ab ,a, b 一奇一偶， 再由z2 = a2 +b2 得 a = 2 uv , b = u2 - v2,z = u2 + v2 或 a2 2 2 2u - V , b = 2 uv , z = u

38、+ v,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。文档来自于网络搜索其中正负号可任意选取. 第三章同余即同余的概念及其基本性质37 / 77Gk1，证明(i)若 Sok 三 B如4 (modm)xi =y i (modm)、i=1 ,

39、 2,、，k则 S ActigX尸川 x。三 2 Bgg yO 川 yP (modm)aiii，a特别地，若 ai 三bi (modm), i=0, 1, |,n 则anXn +an丄xn-+ 朴怕0 三bnXn +bnxnd+朴(+bo(modm)a.b (modm), b d d(ii) 若 a 三b(modm), k >0,LI ak 三bk(mod mk),(iii )若a三b(modm), d是a, b及m的任一正公因数，则(iv)若 a 三b(modm), d/m,d>0.贝U a三b(modd).证明：(i)据性质戊，由Xj三yj (mod m), i = 1,2，川

40、，k.得 x"三 yy(mod m),i =1,2，川，k,进一步，则“I凜xf lilx,三 B%|qy：|y：(mod m)最后据性质丁，可得:无直叫惟X。川三W BMqydlHy：(modm)amok(ii)据定理 1，a 三b(modm)= m/a-b,W >0/. mk/k(a-b) =ka-kb又据定理1，即得ka三kb(mod mk).(iii) 据定理 1， a 三b(modm) = m/a-b,即 a-b=ms(s亡 z)Td/a,b,m,d>0,口s，即卫 s,d dd d d仍据定理1，立得一三一(mod ),b d d(iv) 据定理 1， a 三

41、b(modm)= a-a = ms,(s z),又m =dt,t 乙 故 a -b =ms =d(st), st 亡乙”a 三 b(mod d).2、设正整数 a =an10n +an_Ll02+川 ao,O <a clOni试证11整除的充分且必要条件是11整除2 (1)4.y证明：'：1O三-1(mod11),”.由上题(i)的特殊情形立得a =an1On +anjLlo2 +川ao 三 an(1)n +an(1)2 中川 ao(mod11)na 三£ (-1)iai(mod11),i £11/a u 11 卜(一1) ai3. 找出整数能被37, 101

42、整除有判別条件来。解：；1000 三 1(mod37)故正整数 a =ak1000k +ak10002+iHa0,0 <冃 <1000立得37/au 3卜ai.',100 三1(mod101).故设正整数 a =bs100s +bs(00s° +川b0,0 <b <100',立得 101/au 101/2 (-1)七./ i出4、证明 641 I 232 +1证明： 2* 三256(mod641 )16 2二 2 三 256 = 65536 三 154( mod641 )322二 2 三 154 =23716 三1(mod641)即 641 I

43、 232 +15、若a是任一单数，则a2 三 1(mod2n ), (n >1)证明：(数学归纳法)设a =2 m+1(1) n =1 时，a2 =(2m +1)=4m(m +1 )+1 三 1(mod8 ), 结论成立。(2 )设门=k时，结论成立，即：(2m+1 ) 1 三0(mod2宀片(2m+1 ) -1 =21 , (t 亡 z)okoko kcko k而 a 1 =(a -Ha +1 ) = (a -Ha 一1一2)= (2kt )2 +2 *2心 t=t2 22 + *t 2k+ 3=t 2k(t ”2宀+1 )三0( m odk23 )故门=k +1时，结论也成立； n&

44、gt;1时，结论也成立。证明：若2 la n是正整数，则a2n三1 (mod 2n + 2)。设a = 2k + 1,当n = 1时，有a2 = (2k + 1)2 = 4k(k + 1) + 1 三 1 (mod 23),即式(4)成立。设式(4)对于n = k成立，则有kk2_.-k + 2一2 彳亠 ck + 2a = 1 (mod 2) = a = 1 +q2其中q忘乙所以a2k+=(1 +q2k+2)2 = 1 +q 2k + 3 三 1 (mod 2k + 3),其中q是某个整数。这说明式(4)当n = k+ 1也成立。 由归纳法知式(4)对所有正整数n成立。(i 1535625;

45、(ii 1158066解:34(i 1535625=3 5 G13;(ii )1158066 = 2咒 32 72"3x101§2剩余类及完全剩余系1、证明x=u+p r , u =0,1,2,川，pt,t<s是模ps的一个完全剩余类。证明：显然对U,v的不同取值，X共有ps丄-pt =ps个值，故只需证这样的ps个值，关于模ps的两两互不同余。若 5 + p'弋勺三 U2 + ps±V2 (mod ps )=5 -U2 三-V2 Xmod ps )=ps± I U1 -U2，即 5 三 u2 (mod ps丄戶 u u2=P S 弋r 三

46、 pS 丄V2 (mod P Sr w 三 V2 (mod p t M v, = v?二 Ui =U2 或 Vi "时,丄s_tU1 + pVUptfvnod )jp .结论成立。2、若m1,m2 J11 ,mk是k个两两互质的正整数，x1, x2（ ,xk分别通过模m1,m2（ ,mk的完全剩余类，则MiXi + M x 2川 + MkXk通过模m1m2|l|mm的完全剩余系，其中 mmMi, i=12HI,k证明:（1）(2)（数学归纳法）根据本节定理3,知k =2时，结论成立。设对整数k -1 ，结论成立，即若mj, m川km两两互质，令s=M 1 X 1+M X2中山中M k

47、_Xk_ 1当X1,X2, iljx kJ分别通过模g, m2l( ,mk斗的完全剩余系时，s'必过模m =m1m2.mk4 的完全剩余系，其中miiMi = m (i = 12.k T)。现增加 mk，使(mjmQI (i =1,.k -1)，令 M i =M kmk(1,.k -1)， m= M k = mim2.mk，m = mkMm1m2.mk则易知(m,m2,.,mk) =(mk,Mk) =1 , 再令 X = MkXk +mkS ,Xk过模mk的完全剩余系，s过模Mk的完全剩余系时，据本节定理3 , X必过模= mkM k =0口2. mk的完全剩余系，即对 k结论成立。3

48、13、(i)证明整数-H ,.-1,-0,1,., H (H =)中每一个整数有而且只有一种方法表示成313 Xn +3 XnjL +.3X + x0的形状，其中Xj = 1,0,1(i =0,1,.n);反之， 中每一数都 -H且 H ,。(ii)说明应用n+1个特别的砝码，在天平上可以量出1到H中的任意一个斤数。证明：(i)当Xi =1,0,1(i =0,1,. n)时，过模2H +1=3n*的绝对最小完全剩余系，也就是表示-H,H 中的2H +1个整数，事实上，当Xi = -1,0,1时，共有3心个值，且两两互不相等，否则文档来自于网络搜索-n ' , nd'丄 '

49、;丄' n. n，-,3 Xn +3 Xn+.3X, +x0 =3 Xn +3XnJ +.3x1 +x0二 3n(Xn' -Xn) +3n(Xn-人)+.3(% -Xj =Xo -XoII=3| Xo -Xo = Xo =Xo.此即3n4(Xn' Xn) +3X4 -Xn4)+.(X - X)= 0=3| Xj 为=Xj = Xj = .= Xn =焉3n _ 1又的最大值是3n +32 + .3+1 = =H31最小值是33-.-31=H所以，结论成立。fa、(ii)特制n+1个砝码分别重1,3,32,.,3n斤，把要称的物体 2半(dj ) = 2 及取-17y(d

50、i 丿的砝码放在天平的右盘，X取1的砝码放在左盘，则从(i)的结论知，当Xi取适当的值时,可使T =3nXn + 3n-Xnj +.3X +X0.之值等于你所要称的物体的斤数 (<H卜文档来自于网络搜索4、若m1,m2,.,mk是K个两两互质的正整数，x-i ,x2,.xk分别过模m1,m2,.,mk的完全剩余系,Xi +m1xmi ,m2X3 +.mi, m2,., mkxk通过模mi, m2,., mk的完全剩余系。证明：(数学归纳法)(1) K =2时，x-i, x2分别过模mm?的完全剩余系时,为 +0X2共有 m-m?个值，且若Xi +m 1X2 三 x； +mix2(mod

51、mim2)= mi(X2 -x2)三 Xi'-Xi(mod mim2)=m, x/-x1，且 X2 -x：三(mod m2)mi=X； = xi， X2 = X；，即k = 2时结论成立;(2)设当X2l(,Xk分别过模m2l(,mk的完全剩余系时,X2 + m2X3 +川+ m2m3l(|mkxXk过模 m2H( mk 的完全剩余系。因为(m1,m2 IHmk1，由本节定理2得, 0(X2 +m2X3 +川+小2川mk4Xk)亦过模m2H( mk的完全剩余系。当xx?，川,Xk 4, Xk分别过模mi,m2,川，m, mk的完全剩余系时,2有mim2 IHmk个值，且据归纳假设,三X

52、； +miX； + (11 + m, IHmkjX；斗 +mi IHmk4X；(mod mjll mQ若 X, + 0X2 +川+叶 Hlmk；Xk4 + mHImkXk# / 77Xi= Xi'(mod m); X2 +m2X3 +川 +口2川叫二兀=x2 +m2x3 十II +ml km kXmod (临 小Xi= x/(modm), X2=x2(modm2), ，x xk(mod mk)Xi=Xi ,x = x2 ,，Xk = Xk。所以 xm1x 1(+m1mJ|mk_iXk 过模 m1m2ili mk 的完全剩余系。3.简化剩余系与欧拉函数1.证明定理2：若ai,a2,川，aQm)是*(m)与m互质的整数,并且两S对模m不同余，则a1,a2(,a)(m)是模m的一个简化剩余系。证明:ai,a2ya軸)两&对模m不同余，所以它们分别取自模 m的不同剩余类,又；a1,a2,，am)恰是*(m)个与m互质的整数，即它们恰取自与模 m互质的全部剩余类。2 .若m是大于1的正整数，a是整数，(a,m)=1，匕通过m的简化剩余系,I a買 彳饰广詐m)，其中Zg