初等数论闵嗣鹤第三版答案

1、第一章的可除性§1整除的概念带余除法1. 证实定理3也定理3 假设劣,q,都是,得倍数,即的,是任意个整数,那么 qa +q血+4" +4A是川得倍数.证实：、叫,七,q,都是为的倍数. 存在个整数p"孕外使% = pg a2 = pk.an pjm乂 名,/,是任意个整数=0 Pi m + q? m+十 G 0由= 3"q 奶*+q,jE即q.i + q2a2十+ qnan是川的整数2. 证实 31(+1)(2 + 1)证实；(g I )( B+ H n 冷 翌 +2?=zr( /I I I ) fI I 2)耳 b) zi(l乂,】( +1)(/1

2、+ 2), (/? 一 1) + 2)是连续的三个整数故 31( +1)(+ 2), 31 (n-l)n(n+l)31 n(n +1)(n + 2)+(« -1 )n(n +1)从而可知SI /»(/» +1)(2/? +1)3. 假设ar"如.是形如cLx + by (x, y是任意整数,a. b是两不全为零的麴数)的数中最小 整数,那么(a + by0)l(ar+by).if： 不全为 0在整数集合S = a.K + byx,yeZ存在上整数,I大I而有形如心+»的最小整数V.v, jeZ .由带余除法有 ax + by = (axif +

3、 hyo)</+r,0<r <av(, + by.那么r = (x .qqX + (y为q)bwS,由心为是S中的最小整数知r = 0 axbyolaby'：凤)+皈贝+如(x.y 为任煎整数)avM + by I+ by Ib:.abyQ(a,b).又有(",b)l,(aj)b:.(a.b)ax0 + byQ 故axbyQ =(fl>b>4. 假设如b是任意二整教.旦方工0.证实：存在两个整数s.使得a =bs-i-t, lr l<成立,并且当b是奇数时f 缨唯 存在的.当b是偶数时结果如何ues作序列",军T4,生.耳M平,、

4、 ,那么必在此序列的某两项之间即存在一个整数"使：网我,<普叫成立(i)当q为偶数时,Yi/?> 0.那么令s =F,f =" 一5 二 “一§.那么有0<ai)s =t = a-b = a-l)<b a|/|假设b<0那么令s = - 土j = Q-bs = a*上b,那么同祥有p|<§(/>当q为奇数时,假设,A 0那么令s = "F=a-bs =叫一色?/?,那么有一也 堂=?一久=“ 一 =白一0|<0.|心也222 1 1 n 2假设be 那么令$=-牛!,'= 一庭=44岑那么

5、同样有综上所述,存在性得四巧下证唯-性当b 为奇教时.设at =bs+/=bS+h 贝'Jp-rj = h(s 5i| >|/?| 而k罔圳+宙1功I矛盾故$=“=匕 当b为偶数时,s,f不成-.举例如下：此时?为整数3 = 1+ = /? 2 + (X/j = ,k I 222 * 21" 2§2量大公因散与根转相除法I. 证实推论4.1推沦4.1 sb的公因数与(a, b)的因数相同.i£：设d'是a, b的任一公因数二/la, d' lb山冷余除法费a=bqrb=札十J二叩相,二(a,b) = rn.d'Eb%=&quo

6、t;'0性=上,"二 lrn-2=rn-,rn反过来(右?)1.且S,b)lb ,假设那么d'lqdrb.所以(仞的因数都%b的公因数.从而为的公因数与()的因数相同.2. 证实：见木书P2.P3第3题证实.3. 应用§1习题4让明任总两整数的最大公因数存在：,并说明其求法,试用你的所说的求 法及提转相除法实际“也(76501, 9719?解：有§1习题4知：V«, Z.Z># 0,35/ Z.= 0s + f,lf l?g.,.士",使 /> = yiZ+Z|,UI l<y如此类推知：3$,匕,.-2 =匕

7、= Sz +匕.|；"yj,哭乌2222" 2而b是一个有限数./. N,使tntl = 0.*.(«j,6) = 0,r)=(u)=(4,)= ,=(4,°)=.,存在其求法为：(,b)=(., 一知> =(口 _ 皈 b (一 bs )q)=/. (76501,9719)= (9719,76501-9719x7)= (468,9719-8468)= (1251,8468-1251x6) = (3,1)=14. 证实本节式中的"蚣log 2i£： rtlP3§l习趣4知在1式中有Of V号窗夕.哆玲,而鬲/,I ,.

8、-.2 白, .,1.8.=蛭,叩,蜒2"loglog 2§3整除的进一步性质及最小公倍败I-证实两整数a, b互质的充分与必要条件是：存在两个整数s, t满足条件火+初=1.证实 必要性.假设0,. = 1,那么由推论1,1知存在两个整数S,【满足；0十仞=.力,:.as-bt = I充分性.假设存在整数s, t使as+bl= I,那么a, b不全为0°又由于所以aMas+bt 即心II.又力0,“,£ = 12. 证实定理3定理3 "广,qj = "i L0 1''证；校."切皿="斗,那么q

9、l"hi= 1,2,Mlq 叫11,2,又设1. LI% I,1% 1 = "“那么叫 I in.« 反之假设 I at II nu 那么 a. I /«, nt I ni,从而L = m21 HP%矽,妇=1%1,1%1,01匕3. 设+"/ + %1是个整数系数多项我旦,右都不是零,那么I的机只陇是以的因数作分子以为分母的既约分数.井市此推出J5不是有理教.证：设1的任-有理根为巧=1.01.那么q%rn l +十% *+%=. q q q,以'+q网z +如"=02rfl 2-atlfjn =%/ W+ 40"

10、盘 +%矿,所以q整除上式的右端,所以glqp",乂.g= l.g> 1所以/"= 1,二0 1% :又由2有anpn 4-pn'qpqn i =由于P整除上式的右端,所以Pacfp,0= l,q>l,所以,',=1, :-pan放1的有理根为且paqan. q假设很为有理数,.i=>/5,./-2 = 次方程为祭系数方程.那么由.述结论,可知其有有理根只能是±1,±2,这与为共有理根矛而故为无理数.另证,设为有理数JI = 2,p,q= ,q>i,那么 q = 4 =p. p/ = 2g, / => 1q-

11、但由p,g = l,g> I知/= 1,矛盾,故不是有理数.§4质敷算术根本定理1. 试造不超过100的质数表解；用Eratostlwnes筛选法|> 算出 vnx=ia<2> 10内的质数为：2, 3, 5. 73划抑2.3. 5. 7的倍数.剩下的是100内的素数将不超过100的正整数押列如下：-4442424454647484947捋次抨说斜祁娥 773-777-7 1234367-0693 3 3 3g2 3 4 5 &* 约第珀辎6970湖994WT 11 24- 31 41 5+ 61 71 诳2. 求 82798848 及 8105722

12、6635000 的标淮式.解：由于 81848,所以81 A, A = 82798848 = 8x10349856 = 23 xZ?,又 81856,所以 8IB, Z? =8x 1293732 = 2SC.乂4132,所以4IC. C =4x 323433 = 22xD又 91 (3+2+344+3+3),所以 9ID. D = 9x35937 =32 x E ,X9I (3+5+9+3+7X 所以 9IE. E = 9x3993乂 3993 = 3x1331 = 3x11所以人=方11同理有 81057226635000 = 2 3 5, 7 1 F 17 23 37 3. 证实推论3.3

13、井推广到n个正整数的情形.推论3.3设ab是仟意两个正禁数,H.a = pf',p：r a( >0, i = 1,2,b = pS p?p.,剧 Z0, i = L2,上那么 3b) = /1 - p： - ,-Pt,加=p：冲,其中a = min(a,/,), / = 1,2,-,*ii： v/.<az,0</f </?： P? I E气 W I A (i = l,2幻 rip； M,ri/v hp?,盘 l-lJ-l f-l' pf'ppPt* I(,6),又显然(a9b)Ipf'pf Pl.p； =(g同理可得 pjp?p： =M,

14、b| *=max%,0推广设q = pF pF - pf,皿=pF pF座,气=pF就*(其中为质数J = 12*q为任意n个正整数,"2,020),®Pi1 时'riA = (%的,练)g = rnin(h j = l2,k?"P?夕? =0,%, "希=max即,) = 1,2,&4. 应用推论3.3证朗§3的定埋4(ii)iiE：没“ =“机/#,b = pf pf P.,其中5是耳不相同的素数,A (IGd)都是非负整数,有(0) = pjp； ；,A, = mina./J,b 1 我Wk,la.b = ppp?,p(

15、= max0QJ, 1?i?hA土AJ由此知QM)SM|=HpfE =Hp件n片心可灰从而有皿句=_i-J(-1i-l("力)5. 假设2+1是质数(n>D,那么n&2的方彩设：(反证法)设/? = 24/(/为奇数),那么 2 +1 = 2土 +1 = (2勺'+1 = (2? +1)22< ° -尸心)+ +11<2? +1<(2/ + 1=2W + L二2+1为介数矛盾.故n 定为2的方朝.§5函ftfxlJx及其在数论中的一个应用I. 求30!的标沌分解式.解；30 内的素数为 2, 3, 5, 7, lb 13,

16、17,30 53()3()3() = 1544 + 34-1 + 0=23%普卜部囹普a、二r籽囹307+=6+ 1 + 0= 7«?=3()T3()72十=4+0 = 4.部部+ =2 + 0=2,al =3.n M3017+ = 1 + 0= I» G|q =cr = ai3 =a- = 24-0 = 2+= 2 + 0=2,=1A 3.!=2土多 宁7'1已13：171923292. 设n/任-正整数,ci是实数让明,(ii) a4- a + -+ = ita证：i设同那么由性质H知w + l,所以所以nmna</imn .所以w<t?< m

17、 + l 乂在m与m+ 1之间只有唯-整数m. n所以哽= ", = .tibta-l(ii)证法i殳一a<,Ar =., 1,2,m-L,nn那么 k,na) <k + 9:. na = na + k当j+X一|时G.0+牛“: n itn当2>a| + -S ha+i =« + !；n nnr . r 1、 r 一 k.*. « -f a + J + - + a +1nnIji-1ty= £【a + -= £ a + -+ £ a + - n tn M n= (-k)a + 4(a + l)=na + kU i

18、,.YS+T = Sq|令g专心We«-i； 11,. /g+-)= y+T,心=Il .-0 JI； i I丁 /(“+)=£i“+-|"却=：/()ii to 】i/(")足以上为周期的函数.n乂当 a =0-0 = 0,-. o /?,/(«) = 0,即 Vfa + 1 = wa| oTo 评注：|证一充分表达."法的特点,而证二那么表现了较高的技巧.3. 设.,0也任意二实数,证实,可同=.0或(ii) 2«+2切20+.+切+ilffl： (i)由高期函数E的定义有口 =a+r,= /?+$,<)Mrvl;

19、0Msvlv 那么a- /3=(4 -/?* 井匚 r当r-sNO时,0-刈=皿仞当,7<.时,0-. = 0-|仞-1故a" = a"或la* + l ="-/(ii) KI a = cz+a, /? = /? 4- >,0 x,y < »那么 W0Sx+j=a + ()<2下血分西个区间i寸论：(D()<x+j<I.那么|_t+y = O,所以|«4/7 = a)+l/J,所以M+20=2如+2方+2刊+2y = 2a+20+2(xHy冷 20+2切=(« + / + /】+a = a &quo

20、t;a + P *假设l?x + yv2,那么口+> = 1.所以a + = a+闰+L所以2. + 2 切=2幻 + 2幻42仞+2y= 2a + 2(/?42(M4v)2 2闭+ 29+2(罚却-邛< f r >= « H十同十同 + 2+2(口十r )NM + M+1= a""同(ii)(证法2)由J a ,尸对称,不妨设“*盆+2问-2(心+ 我)+2(/7 + 夕)= 2aj42l/?j42«)J + 2(Z?>2laJ + 2l/?J-FQ + (/7)=口+址+ (IS+ 川 + H. + 仞)可+0+回+心+皿+伊

21、=a+a+"R04. 设函数r(x)在闭区间QWxWR上是连续的,并fl非负.证实:和式 fWQFR表小平面区域内的整点?祭数坐标的点)的个数.(ii) 设,4是两个互质的单正整数,证实:以汁I 1=号号0<x<|0<5<(iii) 阪>0,是区域N + yZ式尸2内的整点数,证实；r = 1 4- 4r + 8 , /户一砰-4 *0<x<-=(iv) 加>0.是区域XA. y >0> xyun内的整点数.证实:T = 2 2囹- 0<x<Vn证实：(略)5. 设n是任一正整数,旦二队+印尸+叫好+,P是质数,

22、Oat<p,证实：在E的标准分解式中,质因数p的指数是、nSn h =,P-1其中 Z = a0 + at + a2 + .证堪：在n!的标准分解式中,质因数p的指数臼限,即n = a0 + atp + a2p2 + + arprf 0 S at < p所以T书卜书=(Q + Q?P + + (.2 + 3P 十+ QtP'2)+ 十 at=Q + 2(P + 1) + QgCp,+ p + 1) + + GfCpf"1 + pr"2 + 1)而n $1+ = (ax(p - 1) + Q2(P2 1)+ a3(p3 - 1) + * + af(pe -

23、 1)p 1 p 1=flj + OjQ + 1) + QCp 4- p + 1) + + P-Z + + 1)u nS a h =p- 1第二章不定方程§2. 1习题L解以下不定方程 ")15+ 2> 1Zz)3O6a36O»=63O解：a)原方程等价干：3,v+5y=2() 显然它有一个给数解 孔=1(),%=-2 ,x = 1 0- fi_(/= 0i E 2,y = -2 + 3t幻原方程等价于,17,t-20y = 35显然它有一个整数解 心=-7乂35以=-6乂35x = -7x 3； 20-故L般解为(f= 0± 五-2v = -6x

24、 3S V7 2、把100分成两份使-份可被7蔡除.份可被11整除.解,依题意即求7x + l ly = 100的正整数解.解得与= 8,% =4般解足,x = 8-ll/.U = Q 士 1)V = 4 + 7f但除1=0外无其他正整数解.故有旦只有100 = 56 + 44故这个不等式的整数解个数丁是:因而N当也不是整数时 aI火I而±L + A所以pni)证实2：二元一次不定方程+是rtlxNO. y20 得< 9 a b整数个数为业或史_+ i.ab abx = "b,. /GZ * 7T y = y""f但区间-也,迪的长度是£

25、故此区间内的a babby = N的一切整散解为<气+并囹冬卜4、证实：二元一次不定方程 ax+by = Na.b) = .a >!,/>>!当 N >ab-a-b时有非负整数解,N = ub = a = b那么不然.证实：先让后一点,当N = uMKL原方程有非负整数解(心,为)那么 d=(mxjn2).nb棚 + L«|y0 +1 n 林 +1 =bk,y.+1 = uh.k > 1,/】> 1=ub(k + h) = “b.k + h Z 2 ,这是不可能的.次证,当N>ab-a-b时.因(a,b)=l.故原方程有整数解('

26、;.与.),一殷解是二：二(F = 0,±1 .)要求Xo.bt2O, yG-«/>O=>-<r<会证实存在满足这个不等式的整数 f可取使 a b=b/o + r(O<r<b)于班对于这个站有:.-f、X1Kx-b =尸 Wb-1 =>r0 2 血b为-?叫 2 y()+ - b + (bv + axQ - ab a) - -(N - ab+a) > - ab - a -b - ab + a) -bbbb/.y0 + «zo>O=>ro>- a这就证实了当N>ub-a-b时,原方程有非负整数解

27、.1. 证实定理2推论-推论 单位圆周上座标都是有理数的点(称为有理点),可以写成+W +3或+亡M ,W<r+Zr 以 +.-ar+Zr的形式.其中.膈是不全为零的中数.证实,设有理数x = 4, y = - m * 0满足方程a2 + y2 = I 即尸+并=己 tn m于 是很 / = ±2abdt n = ±a2 - b'd, ni = ±o2 + b'd 或 I = ±a2 一 b'd, m = ±2abd9m = ±a2 + bd 由此得(x,y)=(±*F,士乒g)或(士条g,土弋

28、¥).反之代入方程/ + =I即知这样的点在单位网周上.2. 求出不定方程+3y: = z(x.y) = Lx>O,y>0,乙0的一切止璐数解的公式.解,设不定方程r+3/=z2 ,Uy)= l有解那么(1) 3/zx 或 3/z+x tM为=z2-x2 =(z-xXz + a)=> 3/(z-x)(z+x)n3/ z-.v 或 3/z+xf+3y' = /ny' =号 t-x)或者 y 项"*)于得 3/ z + x 或 3/ z-x以卜不妨设3/n + x (,r,z) = I. 设(X ,z=) M. d/xd/zy'哒：J假

29、设.3/d,n9/x,9/ z' => 9/3y =>3/ y n 3/(a,»)与(a,y) = 1 矛盾这样(3,d) = ln(y-n4/y(. d'/3y-)imd/An"/(x, y)nd = (z + u-.t) = 1 或2,设/ = (z + a,z- a) =>r/(z +.v)-(<- a) = 2x,(二+、)十(z-x) = 2zn(2i.2z) = 2 即 r = IsJu = 2 假设("X,hX)= l,那么从而= (z+】)(z-x)=> y =(z-jc)市引理= i 项,尸曲从而三为

30、it徊sz为整数,(.x,z)=L必须有a, b均为奇数,且3q'a/J醐(z + x.zr) = 2n号.号)=ln(亍)fI从而顼= G + .r)(£-x)n(£)手设 守=疽,27 =人萼=""即'=32-/,),= 2“欢=3/4/, O2L其中0劣为一奇一偶,旦有(,b)=l4解不定方程：x1 + 3y2 = z2 x a 0> y >.,z >(x, y ) = Io解:设(z - x, z + x) = d,易知 d = 1 或 2.fh (z - x)(z + x) = 3y2 得 z - x = 3d

31、a Z + x = db , y = dab 或 z - x = db, z + x = 3dn y = dab, " > 0, b > 0. (" b )I 22 |22=1 ( i ) 当 d = I ： x =, y = ab. z = a > 0 .> 0> (,/>)=221 * 3ID.,人同为奇数：(ii) 当 J = 2： x = IZ>2 - 3<rL y = 2ab9 z = b2a > 09 b > 09 (./>) = 1.3/.,Q. b 一奇一偶.反之,易验证(i)或(订)是原 不

32、定方程的解,fix.,y>.,e>0,O.y=lc3. 还明不等式方程A2 + y2 = z.r,y = Lx > 0. y >Q,zfx的一切止整数解.可以写成公式：工=4湖c一方,y = I a"+b ci b ' *乙=a + b其中“>0,b>0,",3= 1,",/r 单 i双讪明;由定理I知道原方程的解是x = 8/,y =建一d',z = c、/,c>d>O.c,d = L flc. d 为一奇一偶,其中,c = 2ub,d =疽-b>人 >认心»二I,目ab为一奇

33、-偶.所以k=4ubef - b",y = I疽+b ci h ' * zcihx是原方程的正整教解a > 0, j > 0,z >0,a, = 1,2/x, I* + jy 数,原方程jF整数的解苗：0,0,0,0,±a2,±fl , ±a；o,±d ±4彼疽'.±/功七6.7/,±成+/ ±.七片-6.7/,±4"/>41/,土.+/?,6.求方程/ +=/的满足x,y=l2|x的F整数解.解8设.r> Z x2 + y2 = z4的满

34、足(“)=1, 2 | x的正整数解,那么x = 2ab.y = a1 - b19 z2 = a1 + Z> a > Z> > 0» (a. />)=!, * b 奇一偶. 再由亍='+ 必得 =2“v,力="'一 V. z = w2 + v2 或 a = v2. b = 2e/v> z = "： + v2 m > r > 0» (ir, v) = I » v 一 奇一偶,于是得 x = 4wv(w2 一 v2) y = hi4 + v4 -z - ir v2, w > v

35、> 0. (w, v) = I . ,丫 一奇一偶.反之,切验证它是原不定方 程的整数解,H x a 0, y > 0. z > 0» (x.y)=l, 2|x.共中正负号可任怠选取.第三章同余£1同余的概念及其根本性质I、证实 Ti a. ,a< = %,(modm)=y,(modm), i=l, 2、,k那么 E= £ %".码W.时(亦册)特别地,假设可m bj (modm), i=0,1,那么U * “I-L +三bHi广十也(modm(ii) 假设 a 三 lx mod m) k > Oak =依(mod nik

36、),(iii) 假设 amb(modm), d 是 a, b 及 m 的任一止公|火|数,01 = (modk b cl (1«v)假设 amb(modni). dtn、d > 0.那么 aMb(modd).证实:(i)据性质戊,由苴M(mod,)J = 1,2,A.街 # m 了广(inod P") J = 1. 2. 盘,进-步,那么A«,句玲F =气%评片(mod时最后据性质丁.可得?Z#三£机.乂并漂Sodm) . %.中(ii)据定理 11 asb(modni> =>/w/a-b.: A >0,/.nik/k(a-b)=

37、灿kb乂据定理1,即得如三炒(modm"(iii)据定理 1. a = h(mndm) nwi/dB,即 a-h=mR(SZ>.9 a-b fn . H1 a b tny dja,如m、d >0,.= s,即=$,d d d (f d仍据定理1,立得兰三£(n】od竺),b (/ cl(iv) 据定理 1. a=b(modm)=>u-a = iris.(s s z),又、dmm = dtj 6 z,故 a-b = ms = d(stst e 乙:.a 三/Xmodd).2, 校正整数 = () IAyWIOnFlI f试证ii整除的充分旦必要条件是ii第除

38、£(-1)勺M证实:vlO = -l(modllK/.由上题的特殊情形立得u = a“l(T +«_,! 0"-1 +角=/(-!)" +«_)(-!)0-1 +“"mod 11)it 三 £(-l )0 (mod 11),i=O.一 ii/心 i/£(T)q.3. 找出整数能to 37. 101整除有判别条件米-解：.,1000l(mod37)Afc正能数“二?1000" +4.100()1 + ,05q < 1000立司37ja g 3?.l(K)s -l(nK»dl01).故设正整数

39、“ =/7j(xr +妇100孔"瓦,< 100立得 101 归=10|/£<-1)'功.4、证实641 I 2"+1证实：IP"三 256(m(xl641)二 2" = 2562 =65536= 154(rn<>dMl). 2"三 154? = 23716三一l(mod641)即 641 I 2-2 + 15、假设是任单数那么三l(mod2m)("2 1)证»y： <数学归纳法)ilt/=2rri+l(1) = 1 时,a1 =(2m4-l)： =4/n(w + l)+l三l

40、(imd8), 结论成立.(2) 设 =A时.结论成立,W =(2 + 1/ 一 0(mod2A+2)=>(2/«4 1/ -l-2*+2/. (tez)而cT -I =一 1)(/ 4-lj =一 1)(/ I一2)=(2'勺'十225/=2“牝2、=/.2心(>27 + 1)三0( til °dP)故n=Jt +1时.结论也成立；二21时,结论也成立.征明：假设 2)(i, 是E整数.那么 a2 = I (inod 2* 2)o(4)设.=2上十1,当=1时,有a = (2k + I)' = 4灯+ 1) 4- I = 1 (mod

41、2), 即式(4)成立.设式(4>对于n = k成立,那么有a2 I (mod 2*":) => u: = 1 4- </2* * 2» 其中g?乙所以=(1 + 02山)2= 11 (niod 2t+?).其中/是某个维数.这说明穴)当,r = &+ 1也成立.由归纳法知式(4)对所有止整数r,成立.(?) 1535625：(h) 1158066解：(/)I535625 = 3x54x7xI3；()1158066 = 2x37x13x101§2剩余类及完全剩余系I、让明.(=十/广«=0,1,2,f/s是模p的一个完全剩余类.

42、证实：显然对的不同取伉,.(共有p f = p个th,故只需证这样的p个位,关于投p 的两两互不同余.假设“I 4- I" M "2 +2(mod p')=>W,-M, S p'-,(V1-V2)(ITKxip')n P,I 即的 m/(modp« r)n. =/n p' ', = p'(mod p' )=> vt = v, (m<xi p1)=马=v2:.W| = U2 或 Vj * v2 时,Ui营 侦1 o d “ 结论成立.2、者吗,叫,吗是*个两两互.所的止:整数,玉,.小,.分别

43、通过横叫,吗,的完:全剩 余类,那么Mlxl+M x 寸+通过模,“匕=,的完全剩余系,其中m = mlMl, i = 1,2.,A证实,数学归纳法1根据本节定理3.知&=2时,结论成立.2设对整数k-l ,结论成立,即假设/«, /«<, 两两互质,令s -MXX十M心+3 +材卜,.,当为人2"*卜分别通过模,马的完全剩余系时.S必过模m =的完全剩余系其中 m.Af= m z = 1,2.k 1 现增加,使,上=1 i = 1,M-1,令 Mt = M/煤I,A -I m = Mk = nm2.jnk b1 > m = mtMk = ni

44、xnu.jnk那么易知叫匕=nik, M* = 1 .再令 x = Mkxk +mks 当山过极4的完全剩余系,$过模/虬 的完全剩余系时,据本节定理3, x必过模m = nmk的完全剩余系,即对k姑论成立.3俨| _ 13、i证实整数-中每一个整数有而且只有一种方法表示成3-13" x. + 3"-' a;., +.3x+心的形状,其中x,=-1.0J/ = 0J.jj；反之,中每一数都ii说明应用+ 1个特别的破码,在天平上可以量出I到H中的任意一个斤数,证实：i当a; =-1,0,如= 0,1,.时.过模2/ + 1=3的绝对最小完全剩余系.也就是表示一.中的

45、2H + I个整数,事实上.当咒=一1,0,1时,共有3'个伉,旦两两互不相 等否那么3" x/ + 3"_, .J + .3.r, + .q = 3匚+ 3"-1 兀.+ .3为 + xn=3"工；一5+ 3 '玉'-xn l+.3.r1=>31吒一乩=>七=七.此即3'上 一土+ 3" 2urn_ 1 -|> + .- - f =>3lj：| _丹=> X| = A| =>.=>.£ =4V 1又的最大值是3+3卜'+.3十1 =二 = 3-1最小值

46、是3" 3"3 1 -H所以,结论成立.ii特制+ 1个眩码分别梨1,3,3?,.3斤.把要称的物体£.0 = £及取"的破码放在天平的右盘,x,lU 1的秩吗放在左我.那么从i的结论知,当儿取适当的值时, 可使7* = 31 +3-、1 +“3、+心.之值等于你所要称的物体的斤数?.4、假设是K个两两互质的正整数,XpX,.分别过模,*,nt的完全剩余系, 那么Xj +,?|X? +mpm2.v3 +.+,?!,& ,料通过模,i,mt的完全剩余系.证实：数学归纳法< 1K-2时,XpXj分别过模my,m2的完全剩余系时,xt

47、+ mxx2共有mm2个值.J1假设% + "%毛 s x； + 4工；mod "I/% => n x, -x；三.?-.q modmn.fwi K"xi 旦尤,_又；三 mod,%,叫nX=Yx2 = x.即R = 2时结论成立:fn"A IX再旦Xy 一K s (mod/n>) "hn x = *：,xt = x； k = 2 时结论成立:2设留神,&分别过模皿,叫的完全剩余系时,土 +叫七十十叫叫'妃冉过模,厂* , "k的完全剩余系o由于Qq,m, mt ) = 1.由本为定理2得.4(毛十匕.G十

48、十匕H)亦过模俱', mk的完全剩余系.当k, W ,弓十玉分别过模"4,件,'气外十叫 的完全剩余系时,2右明m,花个伯,II据归纳假设,假设而 + "4也+. +,% .,/ 2心.-.V+ 4.YWA_2-VI-1 + nll * * ,匕_M；(】KX1 4 , . lllk )=(mod/zi1) ； x2 十v, “小=x2 +nu - +;nr tCun od -m A.=尤 =A：；(mod4) . x2 =a(tncxlm2), .» xk = x(mod/r)所以再十"LX?十十外叫, . "上M 过模m,n

49、2 ' 九的完全剩余系.3. 简化剩余系与欧拉函数I 证实定理2：假设,的,血侦质的整数,并且两矿秒模m不同余,那么?,纯,%点是模m的一个简化剩余系.决明:两&对模四不同余,所以它们分别取自模m的不同刹余类,又LF血,"s恰是汽时个与m以质的整数,即它们恰】IUI与模m 4质的全部剩余类'2. 假设川是大于1的止整数.是给数.(劣小)=1.：通过m的简化剩余系,调=加,)其中表示展布在g所通过的-切值上的和t证实：由定理3知.&通过】的简化剩余系:四,g ,其中0<q vm且(峰榆=1 .|fu J -L = -Lm(j = 1.2.0(/H)

50、 i假设m >2t那么.(i)必是啊数,乂由(%,“【)=1,得1, H易见m-q尹故m-utn所以辨卜卧印囹左也每一-J页*都存在另-倾使得卜里 = 1,右边共有("1)对.此即=?如1).911特别地.当m=2时,吹2) = 1,£竺)=土.23. 证实知)十以)十十次")=", p质数&(ii)证实£©(") = .其中£ 展布在a的一切正整数上的和式.Aftidfa逐明,(i)由于ap') = p*pi,(人= 1.2q)所以*1)+.)+侦P勺 + (p_DH,7-p) + .+(P

51、«-paT)=p(ii)设 =心气广是a的标准分解我,那么£d = (1 + Pl + + /V )(1 + P? +, +)(1 + Pt +,+ P：').*、放(d) =(l + a(pJ+-+ 衣p )(! +(pt)+A-(p/*)=P1 P2 " =a4. 假设吧四网是k个两两互质的正餐数,gq点 分别通过模吧,叫,m的简化剩 余系,那么通过模mni2-'-mt =m的简化剩余系,其中m = m,Mlti = 1,2,A °证实：(数学归纳法)(1)由定理4知k=2时,结论成立：<2) 设 k-l 时结沦成立,即m =

52、- mt_)= /?i,A/, (/ = I,- ,A: -1).?g,K分别过模,叫t时,=心+心+过小'模的简化剩余系.皇见(injnk ) = 1.那么乂由定理4知,ig + M&通过模|',外的简化剩余系,注意到：999削 = (,M 垮 +(f、)g+ +(f"i 拷3= M&+MK,+ + MKz所以.机§+Mg+虬虽通过模m的简化剩余系.§4.欧拉定理费马定理及其对循环小数的应用1、如果今天是星期一问从今天起再过10俨天是星期几解:假设10'°" +1被7除的非负最小剩余是广,那么这一天就是

53、星期(当r*0时是星期日).,.(1(冷7) = I,由费马定理篇10“三1 (mod7).乂 10 三一2 (itkx17)=> 10*° =(-2),n =45 = 4 (m<xJ6)10"=6?+4 (KeZ).10i 俨 +1= 10"" + 1 三 10' + 1 三 3' + 1 三 3 (mod7) 叩这一天是星期五.2、求(1237俨+ 34)"被111除的余数.解：-.111 = 37x3.二0(111) = (37)(3) = 36x2 = 72.12371三1 (mod 37)据欧拉定理,易知&

54、#39;nl237产三1 (modi 11)1237p = (l2371f =1 (mod 3).12371"三 1237产(modi 11)( 1)乂 12371 = 1 II2+50 .-.12371=50 (mod 111)故/ 1237I2s502 5一53 (mod 11 l)=>vl23714 三532 三34 (modi 11)=>12371" s46 (iiK)d 111) => 1237 F 6 三 7 (nKKj HI)那么 1237120=34x7 = 16 (nnxilll). (tl ( 1)即1237156 = 16 (nuxl

55、lll). 1237 H + 34 三 50 (mod 111) = (12371% 34)"三 50" (modlll).由以上计算.知 502" m 16 (modlll* 50g=46 (modlll).( 12371*+ 34)鸠三 50 三 |6x46 = 7o (modlll).3、证实以下事实但不许用定理1推论：假设是质数.九,虹九是整数.那么(/i, +A2+-Aa f e/i f+/i 2+,e r ( mo).祈由i证实定理1推论.然后再由定理1推论证实定理1 ° 证实(i)对0应用数学归纳法:(1) 当“ =2时.按二项式展开即徊(

56、4 + W w K' + 与(mod p)(2) 没a = k时,结论成立,即(4 + 但 + &)蚌 土峙 + h： (lIKXl p)当m时,(4 +用十九+妃)"=(%十也+IhV +站.|三 h + /if' + 始?*. (mod p)结论成立(ii)在(I)的结论中,令4 = %= ,=如=1.即得:a,r = ii (mod/?)即定理1推论成立.进一步,设m=夕p,那么.(冲口侦,-I).*?同对任-整数,假设(",)=1.那么由上述己证性质得：upl = 1 ( iikxI p)存任 k rz,使 a"-' = 1

57、 + kp故(I) = (1+ 加)" = 1 + C；知 +. + (Ap)"=l+ (/GZ)-,y = l(rTKKl p,)依此类推可得'三 l(modp.),即/“)M l(modp").假设 (",j)=l, 那么(n,/7) = l,(j = l,、s).三l(modpL)=> /初三 1(mod p： ),(,= 1,2,$)?/" . l(inod/n).定理或立.4, 证实：有理数；,03,(",b) = l表成纯循环小数的充分与必要条件是有一正数t使得同 余式戚三l(mod/?)服立,并旦使上式威立的最小止整数t就是循环节的长度.证实,(i)必要性,假设结论成立.那么由定理2知(b. 10)=1,令1=机力),那么据欧拉定理得10 - 1(mod/?)；后充分性.假设有正数【满足10 =l(HK)db)令为使上式成立的最小止整数,且10'=90十1n 10' =(,妁