《初等數(shù)論》版習(xí)題解答

1、第一章整數(shù)的可除性§整除的概念帶余除法1 證明定理3定理3 若ai, a2,川，an都是m得倍數(shù)，q, q?,川，qn是任意n個整數(shù)，則 5印 +q282+11( + qnan是 m 得倍數(shù).證明： ai,aH, an都是m的倍數(shù)。二 存在 n 個整數(shù) Pi, P 2, i 11 Pn 使 ai = Pim, a2 = P2m, HI , an = Pnm又qi,q2,川，qn是任意n個整數(shù)二 qiai 中 q2al(=qiPim 壯2P2m +i|+qnp.m= (Pi q +q2P2 +川 + qn Pn)m即qiai +q2a2十川+qnan是m的整數(shù)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)是連續(xù)的三個整數(shù)故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是任意整數(shù)，a, b是兩不全為零的整數(shù)）的數(shù)中最小 整數(shù)，則(axo +by0) |(ax +by).證：7a,b不全為0i / 77二在整數(shù)集合S =ax+by |x,y

3、亡Z中存在正整數(shù)，因而有形如 ax+by的最小整數(shù) axo +byoVx, y 迂 Z，由帶余除法有 ax+by =(ax0+by0)q+r,0 < r cax0+by0=(x X0q)a+(y-y0q)b 亡 S，由 ax +byo是 S 中的最小整數(shù)知 r=0二 axo+by0 | ax +by/. axo+byo |ax +by ( x, y 為任意整數(shù))二 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是任意二整數(shù)，且bHO，證明：存在兩個整

4、數(shù) S, t使得a =bs +t,|t I蘭羅成立，并且當(dāng)b是奇數(shù)時，s, t是唯一存在的.當(dāng)b是偶數(shù)時結(jié)果如何?證：作序列III,-23忖b|,冬凹b|,塑,I i I則a必在此序列的某兩項之間即存在一個整數(shù)q，使q2號b，則有(i) 當(dāng)q為偶數(shù)時，若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)當(dāng)q為奇數(shù)時，若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當(dāng)b為奇數(shù)時，設(shè)當(dāng)b為偶數(shù)時，s,t不唯一，舉例如下：此時而矛盾故 s = s,t =ti3 b=b 1 +b =b ”2 + (-b),ti =2 2 2§最大公因數(shù)與輾轉(zhuǎn)相除法1. 證明推論4.1推論4.1 a, b的公因數(shù)與(a,b)的因數(shù)相同.證：設(shè)d '是a, b的任一公因數(shù),由帶余除法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)的因數(shù)。b一一<t=a-bs=a-213 / 77反過來（a,b）|a且（a,b）|b，若d”|（a,b）,則d”|a,d”|b，所以（a,b）的因數(shù)都是a,b的公因 數(shù)，從而a,b的公因數(shù)與（a,b）的因數(shù)相同。2. 證明：見本書 P2, P3第3題證明。3. 應(yīng)用§習(xí)題4證明任意兩整數(shù)的最大公因數(shù)存在，并說明其求法，試用你的所說的求 法及輾轉(zhuǎn)相

7、除法實際算出（76501, 9719）.文檔來自于網(wǎng)絡(luò)搜索解：有§習(xí)題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是一個有限數(shù)，”.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 .證明本節(jié)（1）式中的n log blog 2證：由P3§1習(xí)題4知在（1）式中有0 =rn+ <rn <匕2丄 <號<H）蘭守:王蘭2n，而rn>"蘭X*2 b， I引0gb=罟2即Jogb"log 2§整除的進(jìn)一步性質(zhì)及最小公倍數(shù)1.證明兩整數(shù)a，b互質(zhì)的充分與必要條件是：存在兩個整數(shù)S, t滿足條件ax +

9、bt =1 .證明 必要性。若（a,b） =1,則由推論1.1知存在兩個整數(shù)s,t 滿足：as + bt = (a,b),”as + bt =1充分性。若存在整數(shù) 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* | 】證：設(shè)a1,a2,川，an =m1，則 a ImN =1,2,川，n)|ai |m1(i =1,2,川，n)又設(shè)| 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.設(shè) anxan4.xn 1(+a1a0是一個整數(shù)系數(shù)多項式且 a。, an都不是零，則（1）的根只能是以a。的因數(shù)作分子以an為分母的既約分?jǐn)?shù)，并由此推出 J2不是有理數(shù).文檔來自于網(wǎng)絡(luò)搜索證：設(shè)（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假設(shè) 逅為有理數(shù)，X =X2 -2 =0，次方程為整系數(shù)方程，則由上述結(jié)論，可知其有有理根只能是±1,垃，這與 運(yùn)為其有理根矛盾。故 72為無理數(shù)。另證，設(shè)邁為有理數(shù)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，矛盾，故運(yùn)不是有理數(shù)。§質(zhì)數(shù)算術(shù)基本定理1.試造不超過100的質(zhì)數(shù)表解：用Eratosthenes篩選法（1）算出 J106 =10a（2） 10內(nèi)的質(zhì)數(shù)為：2, 3, 5, 7(3)劃掉2, 3, 5 , 7的倍數(shù)，剩下的是100內(nèi)的素數(shù)將不超過100的正整數(shù)排列如下:J23-45-67-8-910111213141516174819202122232425262728293031323334353637383

13、94041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991002 .求 82798848 及 81057226635000 的標(biāo)準(zhǔn)式.解：因為 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個正整數(shù)的情形.推論3.3設(shè)a, b是任意兩個正整數(shù)，且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設(shè)a1pPhi pF ,a2 = pFppill pk2k JH,a pF1 ppill pN（其中Pj為質(zhì)數(shù)j =12川，k,ai為任意n個正整數(shù)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 .應(yīng)用推論3.3證明§3的定理4 （ii）證：設(shè) a-pUpfillpJ, b = p1yi)|pkB ,其中P1, P2,，Pk是互不相同的素數(shù)，8, Pi (1 <i <k)都是非負(fù)整數(shù)，有(a,b) = pApf山 pE,=mi門6,人, 1 2 蘭k,a,b = JpF山 pF,氣-maxSA, 1Wi<k。Pk ,由此知（a, b）a, b =n p嚴(yán)=n卩罟厲用怖心，直i#i

17、 zt=n p=ab；從而有a,b=ab-V(a,b)5 .若2“ +1是質(zhì)數(shù)（n>1）,則n是2的方冪.證：（反證法）設(shè)n =2k|（|為奇數(shù)），EH,c2k 卜，,"c2k、l,八 rc2k (I 4)則 2 +1=2+1=(2 ) +1=(2+1)21_222)+|H+12k2k ln1 <2 設(shè)n是任一正整數(shù)，a是實數(shù)，證明: +1 <(22 y +1 =2n +1 ,- 2n+1為合數(shù)矛盾，故n定為2的方冪.§5函數(shù)x,x及其在數(shù)論中的一個應(yīng)用 1 .求30 !的標(biāo)準(zhǔn)分解式.解：30 內(nèi)的素數(shù)為 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)設(shè)a = m.則由性質(zhì) II 知 m<acm+1.所以所以nm <not cnm + n，所以mc m +1，又在m與m + 1之間只有唯一整數(shù)m, n所以LU =m =a.nkk

19、 +1(ii)證法一設(shè)蘭2 < ,k =0,1,2,川,n-1 ,nnn "1勻十；貝y k < na c k +1,”訂 not = na + k 當(dāng) i +k <n 1時,a +L£k+2:f (G +)a +niT 中| n當(dāng)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)是以丄為周期的函數(shù)。n又當(dāng) a <0,1)時，f(a) =0-0=0,.a< R, f )三0 ,即 Fa +1 =na。ix n評注:證一充分體現(xiàn)了 常規(guī)方法的特點，而證二則表現(xiàn)了較高的技巧。3.設(shè)a, P是任意二實數(shù)，證明:(i) a - P =a - P或a -P中1(ii) 2a +2 P >a +a + P + P證明：（i）由高斯函數(shù) 兇的定義有a =a +r, P = P +s,0 <r <1

21、;0 <sc1。貝Ua P 斗 ot P十 s ,-s<1當(dāng) r -S>0時,a -P =a-P當(dāng) r -s<0時,P -P=aP1故a -P =a P或aP+ 1=aP(ii )設(shè) a =a +x, P =P + y,0 <x, y c 1,則有0 <x +y = + P <2F面分兩個區(qū)間討論:若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對稱，不妨設(shè)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)設(shè)函數(shù)f(X)在閉區(qū)間Q <x<R上是連續(xù)的，并且非負(fù)，證明：和式工rw5。胡表

23、示平面區(qū)域Q<x<R , 0<:y<f(x)內(nèi)的整點(整數(shù)坐標(biāo)的點)的個數(shù)(ii)設(shè)P, q是兩個互質(zhì)的單正整數(shù)，證明:pl q-1亠/ 0<y4(iii)設(shè)r>0, T是區(qū)域x+y<r內(nèi)的整點數(shù)，證明:r = 1 + 4r + 8 J 護(hù)一蚪(iv)設(shè)tt>0, T是區(qū)域工>，y>fl，xySn內(nèi)的整點數(shù)，證明：文檔來自于網(wǎng)絡(luò)搜索22 L0<x<%nn_ X *證明：（略）5.設(shè)n正任一正整數(shù)，且n = Go + flip + a2j/ + -*, p是質(zhì)數(shù)，0旳P，證明：在!的標(biāo)準(zhǔn)分解式中，質(zhì)因數(shù) P的指數(shù)是文檔來自于

24、網(wǎng)絡(luò)搜索h=p 1其中必二口0 +的+ a 2+證明：在n!的標(biāo)準(zhǔn)分解式中，質(zhì)因數(shù) P的指數(shù)有限，即« =尙 + flM?+ fl2p + + flfP 0 < 旳 <p所以71+護(hù)+-71h=-二 1 +fl卻+、 + a#7)+ 2 + 口3啓 + 應(yīng)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習(xí)題1、解下列不

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

26、（t=0,±1川）y=4 +7t但除t =0外無其他正整數(shù)解，故有且只有100 = 56+443、證明：二元一次不定方程ax+ b尸 N a-0 , b0, （ a爐的非負(fù)整數(shù)解為證明：當(dāng)N<0時,原方程沒有整數(shù)解，而N'l + 1<0故命題正確Lab J因為=0時,原方程有且只有一個非負(fù)整數(shù)解（0,0）而Jj=0卜1=1LabLab(a,b)=1 所以原方程有整數(shù)解(X0,y0 ), y。=(-1)2福1,川,qN,X0 =(T)nq2,|l|,qjN44川Lqn ，由于 a >b >0，故 X0,y0 中一正一負(fù)，可設(shè) x >0, y <

27、;0原方程的一般解是：-bt（t =0,±1川）.y = y。+at要求 X0 -bt >0,y0+at >0= x0>t >-血，ba僅當(dāng)-沁是整數(shù)時，才能取t =-血,否則t>-必aLaLa故這個不等式的整數(shù)解個數(shù) T是：當(dāng)是整數(shù)時T =當(dāng)1°不是整數(shù)時Ta+1所以申(m)中1i+1卡卅+1因而厝卜因而I x x bt證明2:二元一次不定方程ax +by = N的一切整數(shù)解為4 - 0 ，Z，于但區(qū)間卜血，直的長度是A，故此區(qū)間內(nèi)的L a baby = yo +at是由x > 0，y > 0得一蘭仝0a b整數(shù)個數(shù)為或 + 1。

28、文檔來自于網(wǎng)絡(luò)搜索ab ab4、證明：二元一次不定方程ax+by = N,(a,b) =1,a ：>1,b >1，當(dāng) N>ab a-b時有非負(fù)整數(shù)解， N =ab=a=b則不然。證明：先證后一點，當(dāng)N =ab-a-b時，原方程有非負(fù)整數(shù)解(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，這是不可能的。次證，當(dāng)N>ab-a-b時，因(a,b)=1，故原方程有整數(shù)解(x0 ,y0)，般解是:二二(t = 0, ±1川)要求

29、X 0 -bt 30，y 0 -at > 0 =-直蘭t < 會證明存在滿足這個不等式的整數(shù)t = t0可取使a bxo =bt0 +r(0 <r cb)于是對于這個to有：文檔來自于網(wǎng)絡(luò)搜索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這就證明了當(dāng)N Aab-a-b時，原方程有非負(fù)整數(shù)解.1 證明定理2推論。推論 單位圓

30、周上座標(biāo)都是有理數(shù)的點（稱為有理點），可以寫成（+J2aL 十土）或（+士 +3）2斗2 7 - 2斗2丿人2小2，- 2小2丿a +ba +ba +b a +b的形式,其中a與b是不全為零的整數(shù)。于是得設(shè)有理數(shù),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即知這樣的點在單位圓周上。文檔來自于網(wǎng)絡(luò)搜索2.求出不定方程X2 +3y2 =z2,（x, y） =1,x >0, y >0, z >0的一切正整數(shù)解的公式。解：設(shè)不定方程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以下不妨設(shè)3/z+x2 2

32、2(X,z) = 1 ,設(shè)(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 , 設(shè)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由引理可設(shè)Z +X22,=a, z-x=b,y=ab2229 / 77從而三，為證得x,z為整數(shù)，（x,z） = 1,必須有a ,2 2b均為奇數(shù)，且3a >b若(z+x,z-x) = 2 =i+x z-x=1J從而 3y =(z+x)(z-x 戶=、八 z +x 2 z -X 2 y 北 設(shè)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 。文檔來自于網(wǎng)絡(luò)設(shè)(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同為奇數(shù)；（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 。文檔來自于網(wǎng)絡(luò)搜索2243.證明不等式方程 X +y =z ,（x, y ）=1,x >0, y>0,z/x的一切正整數(shù)解.可以寫成公式：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是原方程的正整數(shù)解2 2(X >0, y aO,z aO,(x, y )=1,2/X,且a b 是奇數(shù)，原方程正整數(shù)的解有：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的正整數(shù)解。解：設(shè) X, y, z 是 X2 + y2 = z4 的滿足(x, y) = 1 y =a2-b2, z2 = a2 + b2, a > b > 0 , (a, b) = 1,2 Ix的正整數(shù)解，貝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 一奇一偶。反之，易驗證它是原不定方 程的整數(shù)解，且X > 0 , y > 0 , z > 0 , （X, y） = 1 , 2丨x。文檔來自于網(wǎng)絡(luò)搜索其中正負(fù)號可任意選取. 第三章同余即同余的概念及其基本性質(zhì)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的任一正公因數(shù)，則(iv)若 a 三b(modm), d/m,d>0.貝U a三b(modd).證明：(i)據(jù)性質(zhì)戊，由Xj三yj (mod m), i = 1,2，川

40、，k.得 x"三 yy(mod m),i =1,2，川，k,進(jìn)一步，則“I凜xf lilx,三 B%|qy：|y：(mod m)最后據(jù)性質(zhì)丁，可得:無直叫惟X。川三W BMqydlHy：(modm)amok(ii)據(jù)定理 1，a 三b(modm)= m/a-b,W >0/. mk/k(a-b) =ka-kb又據(jù)定理1，即得ka三kb(mod mk).(iii) 據(jù)定理 1， a 三b(modm) = m/a-b,即 a-b=ms(s亡 z)Td/a,b,m,d>0,口s，即衛(wèi) s,d dd d d仍據(jù)定理1，立得一三一(mod ),b d d(iv) 據(jù)定理 1， a 三

41、b(modm)= a-a = ms,(s z),又m =dt,t 乙 故 a -b =ms =d(st), st 亡乙”a 三 b(mod d).2、設(shè)正整數(shù) 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. 找出整數(shù)能被37, 101

42、整除有判別條件來。解：；1000 三 1(mod37)故正整數(shù) a =ak1000k +ak10002+iHa0,0 <冃 <1000立得37/au 3卜ai.',100 三1(mod101).故設(shè)正整數(shù) 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是任一單數(shù)，則a2 三 1(mod2n ), (n >1)證明：(數(shù)學(xué)歸納法)設(shè)a =2 m+1(1) n =1 時，a2 =(2m +1)=4m(m +1 )+1 三 1(mod8 ), 結(jié)論成立。(2 )設(shè)門=k時，結(jié)論成立，即：(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時，結(jié)論也成立； n&

44、gt;1時，結(jié)論也成立。證明：若2 la n是正整數(shù)，則a2n三1 (mod 2n + 2)。設(shè)a = 2k + 1,當(dāng)n = 1時，有a2 = (2k + 1)2 = 4k(k + 1) + 1 三 1 (mod 23),即式(4)成立。設(shè)式(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是某個整數(shù)。這說明式(4)當(dāng)n = k+ 1也成立。 由歸納法知式(4)對所有正整數(shù)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個值，關(guān)于模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 .結(jié)論成立。2、若m1,m2 J11 ,mk是k個兩兩互質(zhì)的正整數(shù)，x1, x2（ ,xk分別通過模m1,m2（ ,mk的完全剩余類，則MiXi + M x 2川 + MkXk通過模m1m2|l|mm的完全剩余系，其中 mmMi, i=12HI,k證明:（1）(2)（數(shù)學(xué)歸納法）根據(jù)本節(jié)定理3,知k =2時，結(jié)論成立。設(shè)對整數(shù)k -1 ，結(jié)論成立，即若mj, m川km兩兩互質(zhì)，令s=M 1 X 1+M X2中山中M k

47、_Xk_ 1當(dāng)X1,X2, iljx kJ分別通過模g, m2l( ,mk斗的完全剩余系時，s'必過模m =m1m2.mk4 的完全剩余系，其中miiMi = m (i = 12.k T)?，F(xiàn)增加 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的完全剩余系時，據(jù)本節(jié)定理3 , X必過模= mkM k =0口2. mk的完全剩余系，即對 k結(jié)論成立。3

48、13、(i)證明整數(shù)-H ,.-1,-0,1,., H (H =)中每一個整數(shù)有而且只有一種方法表示成313 Xn +3 XnjL +.3X + x0的形狀，其中Xj = 1,0,1(i =0,1,.n);反之， 中每一數(shù)都 -H且 H ,。(ii)說明應(yīng)用n+1個特別的砝碼，在天平上可以量出1到H中的任意一個斤數(shù)。證明：(i)當(dāng)Xi =1,0,1(i =0,1,. n)時，過模2H +1=3n*的絕對最小完全剩余系，也就是表示-H,H 中的2H +1個整數(shù)，事實上，當(dāng)Xi = -1,0,1時，共有3心個值，且兩兩互不相等，否則文檔來自于網(wǎng)絡(luò)搜索-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所以，結(jié)論成立。fa、(ii)特制n+1個砝碼分別重1,3,32,.,3n斤，把要稱的物體 2半(dj ) = 2 及取-17y(d

50、i 丿的砝碼放在天平的右盤，X取1的砝碼放在左盤，則從(i)的結(jié)論知，當(dāng)Xi取適當(dāng)?shù)闹禃r,可使T =3nXn + 3n-Xnj +.3X +X0.之值等于你所要稱的物體的斤數(shù) (<H卜文檔來自于網(wǎng)絡(luò)搜索4、若m1,m2,.,mk是K個兩兩互質(zhì)的正整數(shù)，x-i ,x2,.xk分別過模m1,m2,.,mk的完全剩余系,Xi +m1xmi ,m2X3 +.mi, m2,., mkxk通過模mi, m2,., mk的完全剩余系。證明：(數(shù)學(xué)歸納法)(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時結(jié)論成立;(2)設(shè)當(dāng)X2l(,Xk分別過模m2l(,mk的完全剩余系時,X2 + m2X3 +川+ m2m3l(|mkxXk過模 m2H( mk 的完全剩余系。因為(m1,m2 IHmk1，由本節(jié)定理2得, 0(X2 +m2X3 +川+小2川mk4Xk)亦過模m2H( mk的完全剩余系。當(dāng)xx?，川,Xk 4, Xk分別過模mi,m2,川，m, mk的完全剩余系時,2有mim2 IHmk個值，且據(jù)歸納假設(shè),三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.簡化剩余系與歐拉函數(shù)1.證明定理2：若ai,a2,川，aQm)是*(m)與m互質(zhì)的整數(shù),并且兩S對模m不同余，則a1,a2(,a)(m)是模m的一個簡化剩余系。證明:ai,a2ya軸)兩&對模m不同余，所以它們分別取自模 m的不同剩余類,又；a1,a2,，am)恰是*(m)個與m互質(zhì)的整數(shù)，即它們恰取自與模 m互質(zhì)的全部剩余類。2 .若m是大于1的正整數(shù)，a是整數(shù)，(a,m)=1，匕通過m的簡化剩余系,I a買 彳飾廣詐m)，其中Zg