初等數(shù)論閔嗣鶴嚴(yán)士健版習(xí)題解答

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

2、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ù)的三個(gè)整數(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 / 78二在整數(shù)集合S =ax+by |x,y亡Z中存在正

3、整數(shù)，因而有形如 ax+by的最小整數(shù) axo +byoVx, y 迂 Z，由帶余除法有 ax+by =(ax0+by0)q+r,0 0.則令s =9 ,t = a -bs = a -2, q ,bb V = b 1t qq0 蘭a bs =t=ab=a 22若bo則令s 蛙-一心*咿，則同樣有q +1(ii)當(dāng)q為奇數(shù)時(shí)，若b0則令s =2q +12 b，則有2 / 78q+1q+1b =a 2 2bb c0”.t 2若b0，則令s竽,，寧b，則同樣有t |b|bbt , 1 ”.t tt +t1 b當(dāng)b為奇數(shù)時(shí)，設(shè)當(dāng)b為偶數(shù)時(shí)，s,t不唯一，舉例如下：此時(shí)而矛盾故 s = s,t =ti3

4、 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 +站4rn qn 十，0 = rn+rn crn4 vHI rb二(a,b) =rn二 d |a -bq, =ri, d|b -32,dg=rn4qn +rn即d 是(a,b)的因數(shù)。b一一t=a-bs=a-211 / 78反過(guò)來(lái)（a,b）|a且（a,b）|b，若d”|（a,b）,則d”|a,d”|b，所以（a,b）的因數(shù)都是a,b的公因 數(shù)，從而a,b的

5、公因數(shù)與（a,b）的因數(shù)相同。2. 證明：見(jiàn)本書(shū) P2, P3第3題證明。3. 應(yīng)用習(xí)題4證明任意兩整數(shù)的最大公因數(shù)存在，并說(shuō)明其求法，試用你的所說(shuō)的求 法及輾轉(zhuǎn)相除法實(shí)際算出（76501, 9719）.資料個(gè)人收集整理，勿做商業(yè)用途解：有習(xí)題4知:bVa,b 亡 Z,b H0, 3s,t 亡 Z,使 a =bs+t,|t |蘭一。，2/.3 Si,t1，使 b =s1t +1,|1 |山 2,Hh如此類(lèi)推知:222=tnSn +tn；sn 卅，tn 卅，tn A tnsn + 十人十;且|tn戶(hù)羅 罟胡卜歲 屛而b是一個(gè)有限數(shù)，”.3 n忘N ,使tn十=0(a, b) = (b,t ) =

6、 (t ,ti ) = (ti,t2)11 = (tn ,tn 十)=(tn,0) = tn，存在其求法為:(a,b) =(b,a -bs) =(a -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證：由P31習(xí)題4知在（1）式中有0 =rn+ rn 匕2丄 號(hào)蘭X*2 b， I引0gb=罟2即Jogblog 2整除的進(jìn)一步性質(zhì)及最小公倍數(shù)1.證明兩整數(shù)a，b互質(zhì)的充分與必要條件是：存在

7、兩個(gè)整數(shù)S, t滿(mǎn)足條件ax + bt =1 .證明 必要性。若（a,b） =1,則由推論1.1知存在兩個(gè)整數(shù)s,t 滿(mǎn)足：as + bt = (a,b),”as + bt =1充分性。若存在整數(shù) S, t使as+bt=1，則a, b不全為0。又因?yàn)?(a,b)|a,(a,b) |b，所以(a,b|as +bt) 即(a,b)|1。又(a,b) 0 , . (a,b) =12證明定理3定理 3a1,a2lll,an 】=a 1 Ia MllI an, |證：設(shè)a1,a2,川，an =m1，則 a ImN =1,2,川，n)|ai |m1(i =1,2,川，n)又設(shè)| a11,| a2 |H,|

8、 an | =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是一個(gè)整數(shù)系數(shù)多項(xiàng)式且 a。, an都不是零，則（1）的根只能是以a。的因數(shù)作分子以an為分母的既約分?jǐn)?shù)，并由此推出J2不是有理數(shù).資料個(gè)人收集整理，勿做商業(yè)用途證：設(shè)（1）的任一有理根為 P, （p ,q）=1,q1。則qn.n 丄 .ibj,n_1. n .（2）naoq,anP +an 丄 p q+m+ai pq +aoq =0由（2） -anpn =

9、anjLpn丄q +ill +a1 pqn+所以q整除上式的右端，所以 q | anpn，又（p,q） =1,q :1 ,所以（q, pn） =1,. q |an ;又由（2）有 anPn +anp2q +川+印pqn=aoq因?yàn)镻整除上式的右端，所以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為無(wú)理數(shù)。另證，設(shè)邁為有理數(shù)72= , （p,q） =1,q 1，則q22=

10、.2q2 = p2.（p2,q2）=（2q2, p2）=q2 1 q但由（P,q） =1,q A1知（p2,q2） =1，矛盾，故運(yùn)不是有理數(shù)。質(zhì)數(shù)算術(shù)基本定理1.試造不超過(guò)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)的素?cái)?shù)將不超過(guò)100的正整數(shù)排列如下:J23-45-67-8-91011121314151617481920212223242526272829303132333435363738394041424344454647484950515253545

11、556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991002 .求 82798848 及 81057226635000 的標(biāo)準(zhǔn)式.解：因?yà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 ),所以 9|D, D =9 35937 =32 x E ,又 9

12、| (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個(gè)正整數(shù)的情形.推論3.3設(shè)a, b是任意兩個(gè)正整數(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(用),i =12H|,k證： Yj =min(的，Pi)，二 0 社 %,0

13、耳 0）,p/p 111 Pk =(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是互不相同的素?cái)?shù)，8, Pi (1 i k)都是非負(fù)整數(shù)，有(a,b) = pApf山 pE,=mi門(mén)6,人, 1 2 蘭k,a,b = JpF山 pF,氣-maxSA, 1Wi1）,則n是2的方冪.證：（反證法）設(shè)n =2k|（|為奇數(shù)），EH,c2k 卜，,c2k

14、、l,八 rc2k (I 4)則 2 +1=2+1=(2 ) +1=(2+1)21_222)+|H+12k2k ln1 2 設(shè)n是任一正整數(shù)，a是實(shí)數(shù)，證明: +1 (22 y +1 =2n +1 ,- 2n+1為合數(shù)矛盾，故n定為2的方冪.5函數(shù)x,x及其在數(shù)論中的一個(gè)應(yīng)用1 .求30 !的標(biāo)準(zhǔn)分解式.解：30 內(nèi)的素?cái)?shù)為 2，3，5，7，11，13，17，19，23，2917 / 782 =+川=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計(jì)川=2+0 = 2or

15、 a Ct Ct 1 叫一519 -“23 529 一 I2314542230! =235 7 11 13 17 19 23 29(i)證:如+卜+卜+卜+凹(i)設(shè)a = m.則由性質(zhì) II 知 macm+1.所以所以nm not cnm + n，所以mc m +1，又在m與m + 1之間只有唯一整數(shù)m, n所以LU =m =a.nkk +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時(shí),2 a +丄 n5 切,a+丄=a+1;n1n 1B +o +川+nnn1 n A-kjn+ -n=

16、 a + = S a+- + aiTni _0n izB_k=(n- k)B+k(G+1)=n a +kn -1/. Z a +丄=2i =0n證法二n A.令 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)時(shí)，f(a) =0-0=0,.aa +a + P + P證明：（i）由高斯函數(shù) 兇的定義有a =a +r, P = P +s,0 r 1;0 sc1。貝Ua P 斗 a P十 s r 0時(shí),a -P =a-P當(dāng) r -s0時(shí),P -P=aP1

17、故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面分兩個(gè)區(qū)間討論:若0x +y 2ot +2P= a + P + P +a = a +a + P + P 若 12a+2P +1=a +a + P +P(ii) (證法2)由于a, P對(duì)稱(chēng)，不妨設(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 xR上是連續(xù)的，并且非負(fù)，證

18、明：和式工rw5。胡表示平面區(qū)域QxR , 0:yf(x)內(nèi)的整點(diǎn)(整數(shù)坐標(biāo)的點(diǎn))的個(gè)數(shù)(ii)設(shè)P, q是兩個(gè)互質(zhì)的單正整數(shù)，證明:pl q-1亠/ 00, T是區(qū)域x+y0, T是區(qū)域，yo,傾 內(nèi)的整點(diǎn)數(shù)，證明：資料個(gè)人收集整理，勿做商業(yè)用途T = 2oxcVHpI X1證明：（略）5.設(shè)n正任一正整數(shù)，且n = ao + flip+a2j/ + -, p是質(zhì)數(shù)，0Rjp,證明：在卅的 標(biāo)準(zhǔn)分解式中，質(zhì)因數(shù) P的指數(shù)是資料個(gè)人收集整理，勿做商業(yè)用途h=T p=i其中必二 00 + 0 +a 2+ .證明：在n!的標(biāo)準(zhǔn)分解式中，質(zhì)因數(shù) P的指數(shù)有限，即tt = ClD + fllP+如p2

19、 + +%pE, 0旳 P所以fnl+ +lip J.L二 1 + flzP +、 + 盤(pán)賽b-i) + 2 + 如卩 + + + at二 dl + 業(yè)+ D + 總3疔 + P + 1) + + %(pi + pL + +l)n-S 1、p =7 qi(p - !) + 如腫- +-+_ 1)P 1 P 1二叼 + 如+1) + 対矽 + ? + 1) + - + 卯曰 + pL2 + .+ l)第二章不定方程 2.1習(xí)題1、解下列不定方程a)15+ 2 滬 1 0 0b)306x-360y =63013 / 78解：a）原方程等價(jià)于:3x +5y =20顯然它有一個(gè)整數(shù)解X0 =10, y

20、。= -2 ，故一般解為x = 1 0- 5 fy 2+3t(t =0土 1, 12,)b）原方程等價(jià)于:17x -20y =35顯然它有一個(gè)整數(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一般解是： ”（t=0,1川）y=4 +7t但除t =0外無(wú)其他正整數(shù)解，故有且只有100 = 56+443、證明：二元一次不定方程ax+ b尸 N a-0 , b0, （ a爐的非負(fù)整數(shù)

21、解為證明：當(dāng)N0時(shí),原方程沒(méi)有整數(shù)解，而Nl + 1b 0，故 X0,y0 中一正一負(fù)，可設(shè) x 0, y 0,y0+at 0= x0t -血，ba僅當(dāng)-沁是整數(shù)時(shí)，才能取t =-血,否則t-必aLaLa23 / 78故這個(gè)不等式的整數(shù)解個(gè)數(shù) T是：當(dāng)是整數(shù)時(shí)T =當(dāng)1不是整數(shù)時(shí)Ta+1所以申(m)中1i+1卡卅+1因而厝卜因而I x x bt證明2:二元一次不定方程ax +by = N的一切整數(shù)解為4 - 0 ，Z，于但區(qū)間卜血，直的長(zhǎng)度是A，故此區(qū)間內(nèi)的L a baby = y。+at是由x 0，y 0得一蘭仝0a b整數(shù)個(gè)數(shù)為里或N+ 1 o資料個(gè)人收集整理，勿做商業(yè)用途ab ab4、證

22、明：二元一次不定方程ax+by = N,(a,b) =1,a ：1,b 1，當(dāng) Nab a-b時(shí)有非負(fù)整數(shù)解， N =ab=a=b則不然。證明：先證后一點(diǎn)，當(dāng)N =ab-a-b時(shí)，原方程有非負(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)Nab-a-b時(shí)，因(a,b)=1，故原方程有整數(shù)解(x0 ,0)，一般解是:二二(t = 0, 1川)要求X 0 -bt 30，y 0 -at 0 =-直蘭t 會(huì)證明存在滿(mǎn)足這個(gè)不等式的整數(shù)t = t

23、0可取使a bxo =bt0 + r(0 r cb)于是對(duì)于這個(gè)to有：資料個(gè)人收集整理，勿做商業(yè)用途X bt0 =r 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時(shí)，原方程有非負(fù)整數(shù)解.1 證明定理2推論。推論 單位圓周上座標(biāo)都是有理數(shù)的點(diǎn)（稱(chēng)為有理點(diǎn)），可以寫(xiě)成（+J2aL 十土）或（+士 +3）2丄r 7 - 2斗2丿人2小2，- 2小2丿a +ba +ba +b a +b的形式,其中a與b是不全為零的整數(shù)。于是得設(shè)有理

24、數(shù),y=- ( mH 0 )滿(mǎn)足方程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 bM，由此得(x, y) =(土朮-霽討或(0+代入方程x2+y2 = 1即知這樣的點(diǎn)在單位圓周上。資料個(gè)人收集整理，勿做商業(yè)用途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

25、 或 3/z+x 因?yàn)?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 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 /yCd /3y )而 d/x= d/(x, y 戶(hù) d =1 (z +x

26、,z -X )=1 或2 , 設(shè)t =(z + x,z-x 戶(hù) 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 _ ,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=ab2225 / 78從而三，為證得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 戶(hù)

27、=、八 z +x 2 z -X 2 y 北 設(shè)r,二bFb,即x2 2 - -=3a b ,y =2ab,z =3a 中b，其中a,b為一奇一偶，且有（a,b） = 14 .解不定方程：X2 + 3y2z2,y 0 , z 0 , (X, y ) = 1 。資料個(gè)人收集整理，勿做商業(yè)用途解：設(shè)(z z + x-x,=db2,z + x) = d ,易知 d = 1 y = dab 或 z - x = db2,2。由(z -x)(z + x) = 3 y2 得2x = 3 da , y = dab , a 0 ,z - x = 3 da2,b 0 , (a, b )y=ab,z=S 0 , (a

28、, b )=lb , a,b同為奇數(shù)；（ii ）2 2d = 2 : x = | b - 3a |,y = 2 ab ,a 0，b 0，（a, b ） = 1，3 .|b，a, b 一奇一偶。反之，易驗(yàn)證（i ）或（ii ）是原 不定方程的解，且X 0 ， y 0 ， z 0 ， （x, y） = 1 。資料個(gè)人收集整理，勿做商業(yè)用途2243.證明不等式方程 X +y =z ,（x, y ）=1,x 0, y0,z/x的一切正整數(shù)解.可以寫(xiě)成公式：X =4ab(a2-b2), y = I ab6a2b21，2 2z = a +b其中 a AO,b AO,(a,b )=1,a, b一單一雙2 2

29、 2證明：由定理1知道原方程的解是x=2cd,y=c -d ,z=C +d ,cd :0,(c,d ) = 1，且 c， 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 一6a b )(a b)，22,44

30、-22、，224422(a +b- - - 2 2-6ab),4ab(a -b),(a 5),6.求方程X2 + y2 = z4 的滿(mǎn)足(X, y ) = 1 , 2 I x的正整數(shù)解。y, z 是 X2 + y2 = z4 的滿(mǎn)足(x, y) = 1y =a2-b2, z2 = a2 + b2, a b 0 , (a, b) = 1解：設(shè)x,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 + v,u v

31、0 ,(u, V)= 1 ,u, v 一奇一偶，于是得 X = 4uv(u - v)，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 1 x。易驗(yàn)證它是原不定方資料個(gè)人收集整理，勿做商業(yè)用途其中正負(fù)號(hào)可任意選取. 第三章同余31 / 78匕1同余的概念及其基本性質(zhì)1，證明(i)若愿三 Bong (modm)Xi 三yi(modm)、i=1 ,2,、，k則送 AaigxHX” 三 S B|y?HIykk(modm)特別地，若 ai 三

32、bi (modm), i=0, 1, |,n 則anXanjLXn-+ )|(abnXbnjXn-+b0 (modm)a(modm),b d d(ii)若 a 三b(modm), ko,Uak 三bk(modmk),(iii )若a三b(modm), d是a, b及m的任一正公因數(shù)，則(iv) 若 a 三b(modm)， d/m,dA0.貝U a 三b(modd).證明：(i)據(jù)性質(zhì)戊，由Xj三yi (mod m), i =1,211, k.得 x 三 yPCmod m),i =1,2，HI ,k,進(jìn)一步，則 矚心X, lilxF 三 B哦|ay,|l|y訃(mod m)最后據(jù)性質(zhì)丁，可得:無(wú)

33、 直3供xf 川爐三 2 BopiiOtyFlilyF (modm) (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)1 c a -b m冃口 a b mt d/a,b,m,d AO,二 =s，即一一一= s,ddd d d仍據(jù)定理1,立得旦三b(mod -),b d d(iv) 據(jù)定理 1, a 三b(modm)= aa = ms,(s 亡 z),又：d/m,”.m =dt,t 乙 故 a -b =ms

34、=d(st), st 忘 z, ”a 三 b(mod d).2、設(shè)正整數(shù) a =an10n +an1On-+|Hao,O a 10ni試證11整除的充分且必要條件是11整除送(-1)4.y證明：10三1(mod11),”.由上題(i)的特殊情形立得a =an10n +an丄10“+ Illa0 三 an(1)n +anj1(1)2 卄II a0(mod11)na 三送(-1)i(mod11),iz011/a = 1/送(-1)ai3.找出整數(shù)能被37, 101整除有判別條件來(lái)。解：；1000 三 1(mod37)故正整數(shù) a =ak1000k +akjLl000kd+樸| ao,O 蘭 a 1

35、000立得 37/au 37/z； ai./ i=0Tl00 三 T(mod101).故設(shè)正整數(shù) a =bs100s +bs4l00s+i|b0,0 b 1)證明：(數(shù)學(xué)歸納法)設(shè)a =2m+12 一(1) n=1 時(shí)，a =(2m+1=4m(m+1 )+1 三 1(mod8 ),結(jié)論成立。(2 )設(shè)門(mén)=k時(shí)，結(jié)論成立，即：2 k丄22 kQ(2m+1 ) 1 三0(mod 2宀戶(hù)(2m+1 ) 1 =2* , (t 亡 z)rjkrjkc krjkrj k而 a -1 =(a -Ha+1 ) = (a -Ha -1-2)= (2kr )2 +2 儀心 t=t2+ 卻t 2k+ 3 =t 2心

36、(t尹中1 )三0( m 0 dk23)故門(mén)=k +1時(shí)，結(jié)論也成立； n1時(shí)，結(jié)論也成立。證明：若2 pa, n是正整數(shù)，則a2三1 (mod 2n + 2)。2n設(shè)a = 2k + 1,當(dāng)n = 1時(shí)，有a2 = (2k + 1)2 = 4k(k + 1) + 1 三 1 (mod 23),即式(4)成立。設(shè)式(4)對(duì)于n = k成立，則有a2 三 1 (mod 2k + 2) = a2 = 1 +q2k + 2其中q亡乙所以k +a2 = (1 +q2k+2)2 = 1 +q 2k + 3 三 1 (mod 2k + 3),其中q是某個(gè)整數(shù)。這說(shuō)明式(4)當(dāng)n = k+ 1也成立。 由歸

37、納法知式(4)對(duì)所有正整數(shù)n成立。m =m1m2.mk 的完全剩余系，其中miMi = m (i = 1,2.k-1)。(i 1535625;(ii 115806633/78解:(i 1535625=33x5鐵7xi3 ;(ii )ii58066 = 2x3272xi3xi0i2剩余類(lèi)及完全剩余系1、證明x=u+ ps% , u =0,i,2，川，pt i , ts是模ps的一個(gè)完全剩余類(lèi)。證明：顯然對(duì)u,v的不同取值，x共有ps丄-pt =ps個(gè)值，故只需證這樣的ps個(gè)值，關(guān)于模ps的兩兩互不同余。若 5 + ps弋4 三上 + psV2 (mod ps )Ui=5 -U2 三 p-V2 X

38、mod ps )=pZ I Ui -U2，即 5 三 u2 (mod ps丄戶(hù) u u2呂 ps V,三 pS 丄V2 (mod p s 戶(hù) w 三 V2 (mod pt 戶(hù) v, = v?二 Ui =U2 或 Vi 打2 時(shí),Vu pt側(cè)od ）jp .結(jié)論成立。2、若mi,m2 J11 ,mk是k個(gè)兩兩互質(zhì)的正整數(shù)，xi, x2（ ,xk分別通過(guò)模mi,m2（ ,mk的完全剩余類(lèi)，則MiXi + M x 2川 +MkXk通過(guò)模mimJUmm的完全剩余系，其中 m =mMi， i =i,2jll,k證明:（i）（數(shù)學(xué)歸納法）根據(jù)本節(jié)定理3,知k =2時(shí)，結(jié)論成立。設(shè)對(duì)整數(shù)k -i ，結(jié)論成立

39、，即若mh,km兩兩互質(zhì)，令x2 +HI +Mk_xk_i 當(dāng) xi,x2J|jx k分別通過(guò)模 mi, m2(,mk 的完全剩余系時(shí)，s必過(guò)?，F(xiàn)增加 mk,使(口匚，口小=1 (i=1,.k1)，m = mkMm1m2.mk令 M i =M kmk(1,.k 1)， m =M , =mim2.mk則易知(m,m2,., mQ =(mk, M k) =1 ,再令 X = MkX), +mkS ,Xk過(guò)模mk的完全剩余系，S過(guò)模M k的完全剩余系時(shí)，據(jù)本節(jié)定理3 , X必過(guò)模k結(jié)論成立。= mkM k =m,m2. mk的完全剩余系，即對(duì)3n+ _13、(i)證明整數(shù)-H ,.-1,-0,1,.

40、, H (H =)中每一個(gè)整數(shù)有而且只有一種方法表示成313 Xn +3 XnA +.3x + X0的形狀，其中Xi =1,0,1(i =0,1,. n);反之，中每一數(shù)都 -H且 H,。(ii)說(shuō)明應(yīng)用n+1個(gè)特別的砝碼，在天平上可以量出1到H中的任意一個(gè)斤數(shù)。證明：(i )當(dāng)Xi =1,0,1(i =0,1,. n)時(shí)，過(guò)模2H +1=3n*的絕對(duì)最小完全剩余系，也就是表示-H,H 中的2H +1個(gè)整數(shù)，事實(shí)上，當(dāng)Xi = -1,0,1時(shí)，共有3心個(gè)值，且兩兩互不相等，否則資料個(gè)人收集整理，勿做商業(yè)用途n ic n 二丄 c 丄n丄 n，-,3 Xn +3 Xn+.3X1 +X0 =3 X

41、n +3Xn+ .3為 + X。-3n(Xn -Xn) +3nrXn4 -XnJ+.3(X1 -X1)=Xo -Xo =3| Xo -x0= Xo =x0.此即3n4(Xn Xn) +3Z(Xn4 -Xn4)+.(xX)=0III=3| X1 為=X1 =X1 = .= Xn =Xn3n + 1又的最大值是3n+3n*+ .3+1 =H31最小值是3n 3n 4 -一3 -1 = H所以，結(jié)論成立。(ii)特制n+1個(gè)砝碼分別重1,3,32,.,3n斤，把要稱(chēng)的物體 2半(dj ) = 2 及取-17y(di 丿的砝碼放在天平的右盤(pán)，X取i的砝碼放在左盤(pán)，則從(i)的結(jié)論知，當(dāng)Xi取適當(dāng)?shù)闹禃r(shí)

42、,可使T =3nXn + 3n-Xnj +.3X +X0.之值等于你所要稱(chēng)的物體的斤數(shù)(H卜資料個(gè)人收集整理，勿做商業(yè)用途4、若mi,m2,.,mk是K個(gè)兩兩互質(zhì)的正整數(shù)，Xi,X2,.Xk分別過(guò)模mi,m2,.,mk的完全剩余系,Xi +m1xm1 ,m2X3 +.m1, m2,., mkxk通過(guò)模mi, m2,., mk的完全剩余系。證明：(數(shù)學(xué)歸納法)(1) K =2時(shí)，x1, X2分別過(guò)模mjm?的完全剩余系時(shí),為 +0X2共有 m1m2個(gè)值，且若Xi +miX2 三 xl+mix2(mod mim2)= mi(X2 -x2)三 Xi-Xi(mod 口口2)二 01,|* 為，且 X2

43、 -x；三一(mod m2) mi= Xi = xi， X2 =x；，即k = 2時(shí)結(jié)論成立;(2)設(shè)當(dāng)X2,川，Xk分別過(guò)模m2,川，mk的完全剩余系時(shí),X2 + m2X3 +川+ m2m3lUmk/Xk過(guò)模m2H( mk的完全剩余系。因?yàn)?mi,m2 Hlmki，由本節(jié)定理2得, mi(X2 +m2X3 +ill + m2川mk4Xk)亦過(guò)模m2HI mk的完全剩余系。當(dāng)X,X2,川,Xk 4, Xk分別過(guò)模mi,m2,川，mj mk的完全剩余系時(shí),2有mim2 IHmk個(gè)值，且據(jù)歸納假設(shè),若 X, + miX2 +川+ 葉 Hlmk；xk4 +葉 Hlmk4XkXiXiXi= Xi ,X

44、2 =x2,，Xk =x；。三Xi+miiX； +IHmik/xk二+mi|Hmk4xk(mod m(mk)= Xi(mod m) ； X2 +m2X3 +川 +m|mkjLXk三x2 +m2x3 十H +ml km /xm od (槍 km)= x,(modm), X2=x2(modm2),，x xk(mod mk)37 / 78所以 xm1x 1(+m1mJ|mk_iXk 過(guò)模 m1m2iH mk 的完全剩余系。3.簡(jiǎn)化剩余系與歐拉函數(shù)1.證明定理2：若ai,a2,川，am)是*(m)與m互質(zhì)的整數(shù), 并且兩名對(duì)模m不同余，則ai,a2ll,aem)是模m的一個(gè)簡(jiǎn)化剩余系。證明:ai,a2ya軸)兩s對(duì)模m不同余，所以它們分別取自模 m的不同剩余類(lèi),又；a1,a2,，am)恰是*(m)個(gè)與m互質(zhì)的整數(shù)，即它們恰取自與模 m互質(zhì)的全部剩余類(lèi)。2 .若m是大于1的正整數(shù)，a是整數(shù)，(a,m)=1 , 通過(guò)m的簡(jiǎn)化剩余系,at 1則mmj=h(m)，其中Z表示展布在所通過(guò)的一切值上的和式。證明：由定理3知，匕通過(guò)m的簡(jiǎn)化剩余系:ai,a2,ill,a感m)，其中 Ov ai 2,則*(m)必是偶數(shù)，又由(amri,得(