初等數(shù)論第三版習(xí)題解答

1、文檔來(lái)源為:從網(wǎng)絡(luò)收集整理.word版本可編輯.歡迎下載支持第一章整數(shù)的可除性§1整除的概念帶余除法1 證明定理3定理3若a1，a2,L,an都是m得倍數(shù)，q1，q2,L,qn是任意n個(gè)整數(shù)，則q1a1q2a2Lqnan是m得倍數(shù)證明：Qa1,a2L,an都是m的倍數(shù)。存在n個(gè)整數(shù)p1,p2,Lpn使a1p1m,a2p2m,L,anpnm又q1,q2,L,qn是任意n個(gè)整數(shù)即q1a1q2a2Lqnan是m的整數(shù)2證明3|n(n1)(2n1)證明Qn(n1)(2n1)n(n1)(n2n1)又Qn(n1)(n2),(n1)n(n2)是連續(xù)的三個(gè)整數(shù)故3|n(n1)(n2),3|(n1)n

2、(n1)從而可知3|n(n1)(2n1)3.若ax。by。是形如axby(x,y是任意整數(shù)，a,b是兩不全為零的整數(shù))的數(shù)中最小整數(shù)，(ax0by0)|(axby)證：Qa,b不全為0在整數(shù)集合Saxby|x,yZ中存在正整數(shù)，因而有形如axby的最小整數(shù)ax0by0x,yZ，由帶余除法有axby(ax0by0)qr,0rax0by0則r(xxoq)a(yy°q)bS,由a%by。是S中的最小整數(shù)知r0文檔來(lái)源為：從網(wǎng)絡(luò)收集整理.word版本可編輯.歡迎下載支持.Qax0by0|axby(x,y為任意整數(shù))ax0by0|a,ax0by0|bax。by0|(a,b).又有(a,b)|a

3、,(a,b)|b(a,b)|axoby。故axoby。(a,b)4.若a,b是任意二整數(shù)，且b0,證明：存在兩個(gè)整數(shù)s,t使得成立，并且當(dāng)b是奇數(shù)時(shí)，st是唯一存在的.當(dāng)b是偶數(shù)時(shí)結(jié)果如何?丁3b證：作序列L,b0b一,0,一223b,b，,L2則a必在此序列的某兩項(xiàng)之間即存在一個(gè)整數(shù)q,使qb2|b成立(i)當(dāng)q為偶數(shù)時(shí)，若b0.則令s2,tabsa-b,則有2若b0則令s2，tabs則同樣有t(ii)當(dāng)q為奇數(shù)時(shí),0則令s?,tabsaLtbsa-b,則同樣有t綜上所述，存在性22得證.下證唯一性當(dāng)b為奇數(shù)時(shí)，設(shè)bstbs1ti則ttib(ss)b而t：tiTttitib矛盾故sS,tti

4、當(dāng)b為偶數(shù)時(shí)，s,t不唯一，舉例如下：此時(shí)b為整數(shù)2過(guò)最大公因數(shù)與輾轉(zhuǎn)相除法文檔來(lái)源為：從網(wǎng)絡(luò)收集整理,word版本可編輯.歡迎下載支持1.證明推論4.1推論4.1a,b的公因數(shù)與（a,b）的因數(shù)相同.證：設(shè)d是a,b的任一公因數(shù)，d|a,d|b由帶余除法d|abqiri,d|briq22,d|rn2rn0nrn（a,b）,即d是（a,b）的因數(shù)。反過(guò)來(lái)（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 .證明：見(jiàn)本書P2,P3第3題證明。3 .應(yīng)用§1習(xí)題4證明任意兩整數(shù)的最大公因

5、數(shù)存在，并說(shuō)明其求法，試用你的所說(shuō)的求法及輾轉(zhuǎn)相除法實(shí)際算出（76501,9719）.解：有§1習(xí)題4知：ba,bZ,b0,s,tZ,使abst,|t|-2,使 bst G" | 向2鳥(niǎo),L，如此類推知: 22證：由P3§1習(xí)題4知在（1）式中有色回2n2n1而b是一個(gè)有限數(shù),N,使 tn1 0(a,b) (b,t)(t,G)“士）L（tn,tn 1） （tn,0）卜，存在其求法為:(a,b) (b,abs) (abs, b (a bs)&) L4.證明本節(jié)（1）式中的nlog blog 2文檔來(lái)源為：從網(wǎng)絡(luò)收集整理.word版本可編輯.歡迎下載支持2n

6、12n，1log blog blog 2 b ，即 n log 2log 20rrrn_1rnj.Lrn1rn八八22221 2T，2nb,n次整除的進(jìn)一步性質(zhì)及最小公倍數(shù)1 .證明兩整數(shù)a,b互質(zhì)的充分與必要條件是：存在兩個(gè)整數(shù)s,t滿足條件axbt1.證明必要性。若(a,b)1,則由推論1.1知存在兩個(gè)整數(shù)s,t滿足：asbt(a,b),asbt1充分性。若存在整數(shù)s,t使as+bt=1,則a,b不全為0。又因?yàn)?a,b)|a,(a,b)|b,所以(a,b|asbt)即(a,b)|1。又(a,b)0,(a,b)12 .證明定理3定理3a1,a2L,an|a1|,向|L,同|證：設(shè)a，a2,

7、L,anm1,則a|m1(i1,2,L,n)伯|明。1,2,L,n)又設(shè)|a1|,|a?|,L,|an|m?Mm21m1。反之若|ai|m2，則ai|m2,m1|m2從而mm2,即a，a2,L,an產(chǎn)|4|,|a2|,L,|an|23 .設(shè)anxnan1xn1La1xa0(1)是一個(gè)整數(shù)系數(shù)多項(xiàng)式且a。，工都不是零，則(1)的根只能是以ao的因數(shù)作分子以an為分母的既約分?jǐn)?shù)，并由此推出2不是有理數(shù).證：設(shè)（1）的任一有理根為艮，（p,q）1,q1。則qnn 1n 1nanpan 1 p q Lapqaoq0（2）文檔來(lái)源為：從網(wǎng)絡(luò)收集整理.word版本可編輯.歡迎下載支持nn 1n 1n由（2

8、） anPaniP q La pqa0q ,所以q整除上式的右端，所以q|anpn,又（p,q）1,q1,所以（q,pn）1,q|an；n_n1n1_n又由（2）有anPan1PqLapqa°q因?yàn)閜整除上式的右端，所以P|aoqn,（p,q）1,q1,所以（qn,p）1,p|an故（1）的有理根為,且p|a0,q|an。q假設(shè)應(yīng)為有理數(shù)，xJ2,x220,次方程為整系數(shù)方程，則由上述結(jié)論，可知其有有理根只能是1,2,這與后為其有理根矛盾。故我為無(wú)理數(shù)。另證，設(shè)行為有理數(shù)V2=E,（p,q）1,q1,則q2cP22/2222222,2qp,（p,q）（2q,p）q1q但由（p,q）1

9、,q1知（p2,q2）1,矛盾，故也不是有理數(shù)。制質(zhì)數(shù)算術(shù)基本定理1 .試造不超過(guò)100的質(zhì)數(shù)表解：用Eratosthenes篩選法（1）算出而010a2 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ù)排列如下：T23r5-67-8-91011 12 13 14 15 16 17 t8 19 20文檔來(lái)源為：從網(wǎng)絡(luò)收集整理.word版本可編輯.歡迎下載支持.2422232425262728293031323334353637383940414243444546474849505452535455565758596061626364

10、65666768697071727374757677787980848283848586878889909492939495969798991001w2.求及635000的標(biāo)準(zhǔn)式.解：因?yàn)?|848,所以8|A,A8279884881034985623B,3又8|856,所以8|B,B812937322C,又4|32,所以4|C,C432343322D又9|(3+2+3+4+3+3),所以9|D,D93593732E,又9|(3+5+9+3+7),所以9|E,E939933又399331331311所以A2835113;同理有8105722663500023335473112172337。3.

11、證明推論3.3并推廣到n個(gè)正整數(shù)的情形.推論3.3設(shè)a,b是任意兩個(gè)正整數(shù)，且aPi1P22Lpnn,i0,i1,2,L,k,bPi1P22L-i0,i1,2,L,k,則(a,b)pi1P22Lpj,a,bPi1pjLpj,其中imin(i,J,imin(i,i),i1,2,L,k證：Qimin(i,i),0ii,0iikiiiiPiPi，PiPii1i1i1i1:pP22Lpj|(a,b),又顯然(a,b)|p/p22LPkkP11P22LPkk(a,b),同理可得pJp-LPkka,b,imaxi,i推廣設(shè)aP111P212LPk1k,a2P121P222LPk2k,L冏P1n1P2n2L

12、Pknk(其中Pj為質(zhì)數(shù)j1,2,L,k,ai為任意n個(gè)正整數(shù)i1,2,L,n,j0),則4.應(yīng)用推論3.3證明§3的定理4(ii)證：設(shè)aP11P22LPkk,bP11P21LPkk,其中P1,P2,Pk是互不相同的素?cái)?shù),(a,b)P11P21Lpj,a,bP11P21Lpj,i(1ik)都是非負(fù)整數(shù)，有mini,1，1ik,maxi,i,1ikok由此知(a, b)a, b = pii 1kmin i, i max i , iPii 1kiiabpi=ab；從而有a,b1(a,b)5.若2n1是質(zhì)數(shù)（n>1）,則n是2的方嘉.證：（反證法）設(shè)n2kl（l為奇數(shù)），kkkok

13、k,貝U2n121(22)'1(221)22()22()L1122k1(22k)'12n1,2n1為合數(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,2930730產(chǎn)4,1130112L11213301330132133013迎L132173017301721,1919232912.設(shè)(i)(ii)證:所以30!-23-145235n是任一正整數(shù),。）設(shè)所以nmn742_21113171923是實(shí)數(shù)，證明:m.則由性質(zhì)nmnnmII知mnmn,nn29m1,+1之

14、間只有唯一整數(shù)m,所以必n,k(ii)證法一設(shè)nk1,kn0,1,2,L,n1,nk1,nn當(dāng)n1時(shí),當(dāng)n時(shí)，2證法二1,i-;n1,1;nn1.令f()Ln，ion1,f()是以1為周期的函數(shù)。n又當(dāng)0,1)時(shí)，”)000,R,f()0,n11即n°i0n則表現(xiàn)了較高的技巧評(píng)注:證一充分體現(xiàn)了常規(guī)方法的特點(diǎn)，而證3.設(shè)，是任意二實(shí)數(shù)，證明：(i)或1(11) 22證明：(i)由高斯函數(shù)x的定義有，所以1。r,s,0當(dāng)rs0時(shí)當(dāng)rs0時(shí)故(ii)設(shè)x,則有0xy下面分兩個(gè)區(qū)間討論：若0xy1,則x若1xy2,則x所以r1;0s1。則1或1y,0x,y1,2y0,所以y1,所以(ii)

15、(證法2)由于對(duì)稱，不妨設(shè)文檔來(lái)源為：從網(wǎng)絡(luò)收集整理.word版本可編輯.歡迎下載支持4 .(i)設(shè)函數(shù)在閉區(qū)間QxR上是連續(xù)的，并且非負(fù)，證明：和式表示平面區(qū)域QxR,0yf(x)內(nèi)的整點(diǎn)(整數(shù)坐標(biāo)的點(diǎn))的個(gè)數(shù).(ii)設(shè)p,q是兩個(gè)互質(zhì)的單正整數(shù)，證明：(iii)設(shè)T是區(qū)域/不好與戶內(nèi)的整點(diǎn)數(shù)，證明：(iv)設(shè)">。，T是區(qū)域x>0;。，盯五四內(nèi)的整點(diǎn)數(shù)，證明：證明：(略)5 .設(shè)也是任一正整數(shù)，且?guī)锥?。?amp;加+任爐+，p是質(zhì)數(shù)，01三q<p,證明：在n!的標(biāo)準(zhǔn)分解式中，質(zhì)因數(shù)p的指數(shù)是其中:.一-一.:.證明：在短的標(biāo)準(zhǔn)分解式中，質(zhì)因數(shù)p的指數(shù)有限，

16、即n=Ga+aip+a2p2+-+atp所以而第二章不定方程§2.1習(xí)題1、解下列不定方程a)15x25y100b)306x360y630解：a)原方程等價(jià)于：3x5y20顯然它有一個(gè)整數(shù)解x010,y02,一，x105t故一般解為(t0,1,2,L)y23tb)原方程等價(jià)于：17x20y35顯然它有一個(gè)整數(shù)解x0735,y0635x73520t故一般解為(t0,1,2,L)y63517t2、把100分成兩份，使一份可被7整除，一份可被11整除。文檔來(lái)源為：從網(wǎng)絡(luò)收集整理.word版本可編輯.歡迎下載支持.解：依題意即求7x11y100的正整數(shù)解，解得x08,y04.一x811t一般

17、解是：(t0,1,L)y47t但除t0外無(wú)其他正整數(shù)解，故有且只有10056443、證明：二元一次不定方程axbyN,a0,b0,(a,b)1的非負(fù)整數(shù)解為里或更1abab證明：當(dāng)N0時(shí)，原方程沒(méi)有整數(shù)解，而10故命題正確ab當(dāng)N0時(shí)，原方程有且只有一個(gè)非負(fù)整數(shù)解0,0而011abab因?yàn)閍,b1所以原方程有整數(shù)解%,y0,y0(1)n1q1,LQiN,%(1)nq2,LqN，一a其中一q1,q2,q3,Lq,由于ab0,故x0,y0中一正一負(fù)，可設(shè)x0,y0bxx0bt原方程的一般解是：t0,1,LyVoat要求x0bt0,y0at0x0t近,ba僅當(dāng)也是整數(shù)時(shí)，才能取t也，否則t故這個(gè)不等

18、式的整數(shù)解個(gè)數(shù)T是：當(dāng)是整數(shù)時(shí)Tx0by0a1x0bya1因而且x0y。TN1abbaab當(dāng)必不是整數(shù)時(shí)Tx0必x0為1ababaXo因而Nabyoa所以(m)證明2:Xoyo次不定方程axby=NXXo切整數(shù)解為°yv。bt,tZ,于at是由XO,y。得生a整數(shù)個(gè)數(shù)為更或里abab4、證明:元一次不定方程axXo生，9的長(zhǎng)度是abab故此區(qū)間內(nèi)的時(shí)有非負(fù)整數(shù)解，Nab證明：先證后一點(diǎn)，當(dāng)Nab貝Udmm?).abkhab,khbyN,(a,b)b則不然。1,a1,b1,當(dāng)Nabab時(shí)，原方程有非負(fù)整數(shù)解Xo,yo2,這是不可能的。次證，當(dāng)N>ab-a-b時(shí)，因（a,b）=1，

19、故原方程有整數(shù)解（X°,y°）,一般解是X)yoa%0,1,L)要求x0-bt0yoato為ta餐會(huì)證明存在滿足這個(gè)不等式的整數(shù)bt0可取使Xobtor(orb）于是對(duì)于這個(gè)to有:Xbtortoyoatoyoa(Xob1)-(byoaXoaba)(Naba)(ababbbbaba)1yoatootoy。a這就證明了當(dāng)Nabab時(shí)，原方程有非負(fù)整數(shù)解.1,證明定理2推論。推論單位圓周上座標(biāo)都是有理數(shù)的點(diǎn)（稱為有理點(diǎn)），可以寫成的形式，其中a與b是不全為零的整數(shù)。證明：設(shè)有理數(shù)x,y(m0)滿足方程x y2222y2=1,即l2n2=m2,mm于是得l=2abd,n=(a2b

20、2)d,m=(a2b2)d或l=(a2b2)d,m=2abd,2,22,2,2,22ababab2ab、m=(ab)d,由此得(x,y)=(2,2)或(2,2)。反之，abababab代入方程x2y2=1即知這樣的點(diǎn)在單位圓周上。2.求出不定方程x23y2z2,(x,y)1,x0,y0,z0的一切正整數(shù)解的公式。解：設(shè)不定方程x23y2z2,(x,y)1有解則(1) 3/z-x 或 3/z+x 因?yàn)?3y2x)(z x)3/(zx)(zx)3/zx或3/z+x以下不妨設(shè)3/zx222 x,z1,設(shè)(x,z)d,則d/x,d/zd/3yzx,222若,3/d,9/x,9/z9/3y3/y3/x,

21、y與x,y1矛盾!、222這木3,d1d/yd/yQd/3y而d/xd/x,yd1 zx,zx1或2,設(shè)tzx,zxt/(zx)(zx)2x,t/(zx)(zx)2zt/2x.2z2即t1或t2zx右zx,zx1,則,zx1,3由引理可設(shè)z-xa2,zxb2,yab3從而，為證得x,z為整數(shù)，x,z1,必須有a,b均為奇數(shù)，且3a2b2zxzxzxzx右zx,zx2,1,12 z xaT2262其中a,b為一奇一偶，且有a,b14.解不定方程：x23y2y>0,z>0,(x,y)=1。解：設(shè)(zx,zx)=d,y=dab或z易知d=1x=db2,2。由(zx=3da2,x)(zx)

22、=3y2得y=dab|b23a2|ab,zb23a22，3|b,a,b同為奇數(shù)；(ii)3a2|,z=b23a2,a>0,b>0,(a,b)=1a,b反之，易驗(yàn)證（i）或（ii）是原不定方程的解，且x>0(x,y)=1223.證明不等式方程xy4z,x,y1,x0,y0,z/x的一切正整數(shù)解.2可以寫成公式：x4ab（a2b),y其中a0,b0,a,b1,a,單一雙證明：由定理1知道原方程的解是x2cd,y2d，z0,c,d奇一偶,其中,c2ab,d22ab，ab0,a,bb為一奇一偶.所以2x4ab(a2b),y是原方程的正整數(shù)解(x0,y0,z0,x,y1,2/x,且ab

23、2是奇原方程正整數(shù)的解有：0,0,0,0,2a,0,a24ab(a4(a422b6ab),2(a44(abC22、6ab),224ab(ab)，/22(ab),6.求方程x2y2z4的滿足（x,的正整數(shù)解。y,z是x2y2=z4的滿足(x,y)=1,2x的正整數(shù)解y=a2b2,z2=a2b2,a>b>0,(a,b)=1，a,b再由z2=a2b2得a=2uv,b=u2v2,z=u2v2或a=u2v2,b=2uvz=u2v2,文檔來(lái)源為：從網(wǎng)絡(luò)收集整理.word版本可編輯.歡迎下載支持u>v>0,(u,v)=1,u,v一奇一偶，于是得x=4uv(u2v2),y=|u4v46

24、u2v2|,z=u2v2,u>v>0,(u,v)=1,u,v一奇一偶。反之，易驗(yàn)證它是原不定方程的整數(shù)解，且x>0,y>0,z>0,(x,y)=1,2x。其中正負(fù)號(hào)可任意選取.第三章同余1同余的概念及其基本性質(zhì)1、證明(i)若1Lkl(modm)x,yi(modm)、i=1,2,、，k則1LkxJLKk1,L,ky11Lykk(modm),L,k1,L,k特別地，若aibi(modm),i=0,1,L,門則anxnan1xn1La0bnxnbn1xn1Lb0(modm)(ii)若ab(modm),k0,nakbk(modmk),(iii)若ab(modm),d是a

25、,b及m的任一正公因數(shù)，則ab(modm),bdd(iv)若ab(modm),d/m,d0.貝1Jab(modd).證明：(i)據(jù)性質(zhì)戊，由xiyi(modm),i1,2,L,k.得xiyii(modm),i1,2,L,k,進(jìn)一步，則最后據(jù)性質(zhì)丁，可得：1Lk/Lxk1,L,kM1Lykk(modm),L,k1,L,k(ii)據(jù)定理1,ab(modm)m/ab,又據(jù)定理1,即得kakb(modmk).(iii)據(jù)定理1,ab(modm)m/ab,即a-b=ms(sz)文檔來(lái)源為:從網(wǎng)絡(luò)收集整理.word 版本可編輯.歡迎下載支持abmabmQd/a,b,m,d0,-s，即一ddddd仍據(jù)定理(

26、iv)據(jù)定理 1, a b(modm) a a ms,(s z),又Qd m, m dt,t 乙故 a b ms d (st), st z,2、設(shè)正整數(shù) a an10n an 110n 1 L a0,0 a 10n i試證11整除的充分且必要條件是 11整除 (1)ai. i 1證明：Q101(mod11),由上題(i)的特殊情形立得11a11( 1) ai/ i 0,3.找出整數(shù)能被37, 101整除有判別條件來(lái)解：Q 1000 1(mod37)故正整數(shù) a ak1000k ak 11000k 1 L a0,0 a 1000立彳導(dǎo)37. a37ai.i 0故設(shè)正整數(shù)a bs100sbs110

27、0s1Lb0,0b100',立彳#101.a101(1)ibi.i04、證明641|2321證明：:28256mod641216256265536154mod641322：2154237161mod641即641I23215、若a是任一單數(shù)，則a2n1mod2n2,n1證明：(數(shù)學(xué)歸納法)設(shè)a2m122(1)n1時(shí)，a2m14mm111mod8，結(jié)論成立。(2)設(shè)nk時(shí)，結(jié)論成立，即：2kkk22k22m110mod2k22m112k2t，tz2k 1而 a212k1 a21kka2 1a21 2故n k 1時(shí)，結(jié)論也成立；：1 時(shí)，結(jié)論也成立。n證明：若2|a，n是正整數(shù)，則a21(

28、mod2n+2)。(4)設(shè)a=2k1，當(dāng)n=1時(shí)，有a2=(2k1)2=4k(k1)11(mod23)，即式(4)成立。設(shè)式(4)對(duì)于n=k成立，則有a21(mod2k+2)a2=1q2k+2，其中qZ，所以k12k+22k+3k+3a=(1q2+)=1q2+31(mod2+3)，其中q是某個(gè)整數(shù)。這說(shuō)明式(4)當(dāng)n=k1也成立。由歸納法知式(4)對(duì)所有正整數(shù)n成立。i1535625；ii1158066解：i15356253354713；§2剩余類及完全剩余系s1、證明xupv，u0,1,2,L,p1，ts是模p的一個(gè)完全剩余類。證明：顯然對(duì)u,v的不同取值，x共有pstptps個(gè)值

29、，故只需證這樣的ps個(gè)值，關(guān)于模ps的兩兩互不同余。ststs若u1pv1u2pv2modpststpIuU2,即u1u2modpu1u2UiU2或VlV2時(shí)，u1pstv1u2pstv2modps.結(jié)論成立。2、若m1,m2,L,mk是k個(gè)兩兩互質(zhì)的正整數(shù)，x1,x2,L,xk分別通過(guò)模m1,m2,L,mk的完全剩余類，則通過(guò)模m1m2Lmkm的完全剩余系，其中mmMi,i1,2,L,k證明：(數(shù)學(xué)歸納法)(1)根據(jù)本節(jié)定理3,知k2時(shí)，結(jié)論成立。設(shè)對(duì)整數(shù)k1,結(jié)論成立，即若mi,m2,L,mki兩兩互質(zhì)，令sM1X)M2x2LMk1xk1,當(dāng)x1,x2,L,xk1分別迎過(guò)模m1,m2,L,

30、mk1的元全剩余系時(shí)，s'必過(guò)模'''mm1m2.mk1的元全剩余系，其中miMim(i1,2.k1)?，F(xiàn)增加mk,使(mi,mk)1(i1,.k1),令MiMkmk(1,.k1),m'Mkm1m2.mk1,mmkMkm1m2.mk則易知(m,m2,.,mk)(mik,Mk)1,'再令xMkxkmks,一、一.、,'、一.、.、一.當(dāng)xk過(guò)模mk的完全剩余系，s過(guò)模Mk的完全剩余系時(shí)，據(jù)本節(jié)定理3,x必過(guò)模mmkMkm1m2.mk的完全剩余系，即對(duì)k結(jié)論成立。31,3、(i)證明整數(shù)H,.1,0,1,.,H(H)中每一個(gè)整數(shù)有而且只有一種

31、萬(wàn)法表不成313nxn3014 1.3x x0的形狀，其中xi1,0,1(i0,1,.n);反之，中每一數(shù)都H且H,o(ii)說(shuō)明應(yīng)用n1個(gè)特別的祛碼，在天平上可以量出1到H中的任意一個(gè)斤數(shù)。證明：(i)當(dāng)xi1,0,1(i0,1,.n)時(shí)，過(guò)模2H13n1的絕對(duì)最小完全剩余系，也就是文檔來(lái)源為：從網(wǎng)絡(luò)收集整理.word版本可編輯.歡迎下載支持表示H,H中的2H1個(gè)整數(shù)，事實(shí)上，當(dāng)xi1,0,1時(shí)，共有3n1個(gè)值，且兩兩互不相等，否則此即又的最大值是3n3n1.31最小值是3n3n1.31所以，結(jié)論成立。(ii)特制n1個(gè)祛碼分別重1,3,32,.,3n斤，把要稱的物體di及取-1i1i1di

32、的祛碼放在天平的右盤，x取1的祛碼放在左盤，則從(i)的結(jié)論知，當(dāng)Xi取適當(dāng)?shù)闹禃r(shí)，可使T3nXn3n1Xn1.3xX0.之值等于你所要稱的物體的斤數(shù)H。4、若m1,m2，,mK個(gè)兩兩互質(zhì)的正整數(shù),為，x2，xk分別過(guò)模m1,m2，mk的完全乘U余系,則x1m1x2m1,m2x3.m1,m2,.,mkxk通過(guò)模m1,m2，mk的完全剩余系。證明：(數(shù)學(xué)歸納法)(1)K2時(shí)，x1,x2分別過(guò)模m1,m2的完全剩余系時(shí)，x1m1x2共有m1m2個(gè)值，且若xx,m1x1x1,且x2x2(modm2)m1x1x1,x2x2,即k2時(shí)結(jié)論成立；(2)設(shè)當(dāng)x2,L,xk分別過(guò)模m2,L,mk的完全剩余系時(shí)

33、，x2m2x3Lm2m3Lmk1xk過(guò)模m2Lmk的完全剩余系。因?yàn)?m,，m2LmJ1,由本節(jié)定理2得，m1(x2m2x3Lm2Lmk1xk)亦過(guò)模m2Lmk的完全剩余系。文檔來(lái)源為：從網(wǎng)絡(luò)收集整理.word版本可編輯.歡迎下載支持當(dāng)Xi,x2,L,xk1,xk分別過(guò)模m1,m2,L,mk1,m.的完全剩余系時(shí),2有m1m2Lmk個(gè)值，且據(jù)歸納假設(shè)，若Xim1X2Lm1Lm.2Xk1m1Lm.1x.x1x1（modm1）；x2m2x3Lm2Lmk1xkx1x1（modm1）,x2x2（modm2）,，xkxk（modmk）x1x1，x2x2，xkxk。所以x1m1x2Lm1m2Lmk1xk過(guò)

34、模m1m2Lmk的完全剩余系。3.簡(jiǎn)化剩余系與歐拉函數(shù)1 .證明定理2：若a1,a2,L,a是（m）與m互質(zhì)的整數(shù)，并且兩對(duì)模m不同余，則a1,a2,L,a）是模m的一個(gè)簡(jiǎn)化剩余系。證明：Q4,a2,L,a（m）兩對(duì)模m不同余，所以它彳門分別取自模m的不同剩余類，又Qa1,a2,L,a恰是（m）個(gè)與m互質(zhì)的整數(shù)，即它們恰取自與模m互質(zhì)的全部剩余類。2 .若m是大于1的正整數(shù)，a是整數(shù)，（a,m）1,通過(guò)m的簡(jiǎn)化剩余系，a1則一1（m）,其中表示展布在所通過(guò)的一切值上的和式。m2證明：由定理3知，通過(guò)m的簡(jiǎn)化剩余系：a1,a2,L,a，其中0v廿vm且（am）1,而曳亙（i1,2,L（m）。mm

35、若m>2,則（m）必是偶數(shù)，又由（ai,m）1,得（mai,m）1,且易見(jiàn)mai文檔來(lái)源為：從網(wǎng)絡(luò)收集整理.word版本可編輯.歡迎下載支持.故亙mmaiaim烏1mm所以aa1a2.La(m)mmmm左邊每一項(xiàng)三都存在另一項(xiàng)m五(ij),mmm一aa1使得亙,1,右邊共有-(m)對(duì)，mm2a1此即a-1(m)om2a1特別地，當(dāng)m=2時(shí)，(2)1,-om23.(i)證明(1)(p)L(p)p,p質(zhì)數(shù)。(ii)證明(d)a,其中展布在a的一切正整數(shù)上的和式。dada證明：因?yàn)?pk)pkpk1,(k1,2L,)所以(1)(p)L(p)21=1(p1)(pp)L(pp)=p(ii)設(shè)ap1

36、1p22Lpkk是a的標(biāo)準(zhǔn)分解式，則d(1rLp11)(1p2Lp22)L(1pkLpj),da=p11P22Lpkk=a4.若m1,m2,L,mk是k個(gè)兩兩互質(zhì)的正整數(shù)，1,2,L,k分別通過(guò)模m1,m2,L,mk的簡(jiǎn)化剩余系，則通過(guò)模m1m2Lmkm的簡(jiǎn)化剩余系，其中mm|Mi,i1,2,L,k0證明：（數(shù)學(xué)歸納法） 1） 1）由定理4知k=2時(shí)，結(jié)論成立； 2） 設(shè)k-1時(shí)結(jié)論成立，即mm1Lmk1miMi（i1,L,k1），1,2,L,k1分別過(guò)模m1,L,mk1時(shí)，過(guò)m模的簡(jiǎn)化剩余系。顯見(jiàn)（m,mk）1,則又由定理4知，mkMkk通過(guò)模mmT簡(jiǎn)化剩余系，注意到：所以，M11M22LM

37、kk通過(guò)模m的簡(jiǎn)化剩余系。4歐拉定理?費(fèi)馬定理及其對(duì)循環(huán)小數(shù)的應(yīng)用101010解：若 10101 被 7 除的非負(fù)最小剩余是1010天是星期幾？r，則這一天就是星期r（當(dāng)r0時(shí)是星期日）Q10n71，由費(fèi)馬定理得1061mod7，10105又Q102mod7102454mod6即這一天是星期五28123715634被111除的余數(shù)。據(jù)歐拉定理，易知解： Q 111 37 3.11137336 2 72 ，123713612371361 mod372 181237111237136 1 mod111mod31237156 1237120mod111(1)又 Q12371 1112 50 n123

38、71 50 mod111故Q12371250253mod111Q12371453234mod111則123712034716mod111.由(1)即得123715616mod11112371563450mod111123715634285028mod111502016mod111n50846mod111“28123713450164670modlll.3、(i)證明下列事實(shí)但不許用定理1推論：若p是質(zhì)數(shù)，,，h2,Lha是整數(shù)，則(hih2Lha)ph1Ph2PLh；modp。(ii)由(i)證明定理1推論，然后再由定理1推論證明定理1。證明(i)2應(yīng)用數(shù)學(xué)歸納法：1當(dāng)a2時(shí)，按二項(xiàng)式展開(kāi)即得

39、2設(shè)ak時(shí)，結(jié)論成立，即當(dāng)ak1時(shí)，結(jié)論成立。(ii)在(i)的結(jié)論中，令幾h2Lha1,即得：即定理1推論成立。s進(jìn)一步，設(shè)mpJLPsS,則mpi1Pii1i1固對(duì)任一整數(shù)p,若a,p1,則由上述已證性質(zhì)得：ap11modp存在kz,使ap11kp故(ap1)p=1kpp1C1kpLkpp1p2l(lz)p依此類t可得(a)p1modp，即a1modp.Ri若a,m1,則a,pii1,i1,2,Ls.a1modpiiam1modpii,i1,2,Lsam1modm,定理成立。4、證明：有理數(shù)a,0ab,a,b1表成純循環(huán)小數(shù)的充分與必要條件是有一正數(shù)t使得同b余式10t1modb成立，并且

40、使上式成立的最小正整數(shù)t就是循環(huán)節(jié)的長(zhǎng)度。證明：i必要性，若結(jié)論成立，則由定理2知(b,10)=1,令t=b，則據(jù)歐拉定理得10t1modb;文檔來(lái)源為：從網(wǎng)絡(luò)收集整理.word版本可編輯.歡迎下載支持.a2充分性，若有正數(shù)t,滿足10t1modb令t為使上式成立的最小正整數(shù)，且10t=q1b1且0qab10ta10t1110t1。bb以下參照課本51頁(yè)的證明可得:a=0.aLat.即亙可表成循環(huán)小數(shù)，但循環(huán)節(jié)的長(zhǎng)度就是tobb第四章同余式1基本概念及一次同余式例解同余式12x150mod45解：Q(12,45)=3/15同余多項(xiàng)式有3個(gè)解而原同余式為4x 50 mod154 4x20 mod

41、15x0 10(mod15)與 x05(mod 45)也一樣所以原同余式的3個(gè)解是x 10 15t （t = 0、1、2）即 x1 10(mod15) , x2 25(mod15),x3 40(mod15)1、求下列各同余式的解30256x 179 mod3375ii1215x 560 mod2755iii1296x 1125mod1935i Q 337是素?cái)?shù),256,3371,原同余式有唯一解。先解同余式256x30-2- 1 mod33752由輾轉(zhuǎn)相除法，得256 104 337 791上述同余式的解是 x 104 mod337原同余式的解是x 104 179 81 mod337ii Q

42、(1215, 2755) =5,故先解30243x 112 mod551 5同i的方法的得其解是x 200 mod551原同余式的解是 x 200,751,1302,1853,2404 mod2755iii Q (1296, 1935)=9,故原同余式有 9個(gè)解。由 144x 30- 125 mod215 得 x 80 mod2155原同余式的解是x 80215t mod1935 ,t 0,1L 8.,x 4y2 .求聯(lián)立同余式y(tǒng)2x 9y解：據(jù)同余式的有關(guān)性質(zhì)，29840(mod143)')的解。0(mod143)x 4y 29(mod143) y 42(mod143)4(mod14

43、3)為所求的解。42(mod143)3 . (i)設(shè)m是正整數(shù)，(a, m)證明是同余式axb(modm)的解(ii)設(shè)p是質(zhì)數(shù)，0ap,證明是同余式axb(modp)的解.證明：(i)Q(a,m)1,axb(modm)有唯一解.而據(jù)歐拉定理，得a(m)1(modm),即xba(m)1(modm)是axb(modm)的解.(ii)Q0ap(a,p)1即axb(modp)有唯一解又Qa個(gè)連續(xù)整數(shù)之積必被a!所整除，故可令ab(1)a1(p1)L(pa1)ka!則”1)a1(p1)L(pa1)k(a1)!即b(1)2(a1)(a1)!k(a1)!(modp)a1(p1)L(pa1)/xb(1)-(

44、modp)a!是axb(modp)的解.設(shè)p是素?cái)?shù)，0<a<p,證明：一21(p1)(p2)(pa1)/.、xb(1)(modp)a!是同余方程axb(modp)的解解：首先易知b(1)a1(p1)(p2)(pa1)是整數(shù)，又由(a,p)=1知方程axa!b(modp)解唯一，故只須將xb(1)a1(-p-1(p一2一(-p-a”(modp)代入axa!(modp)驗(yàn)證它是同余方程的解即可4.設(shè)m是正整數(shù)，是實(shí)數(shù)，1m,(a,m)1,證明同余式有解.證明：因(a,m)1,故同余式ax1(modm)必有解x0,(i) 若0x0,則結(jié)論成立；(ii) 若%,令mqx。x1，0x1x0,

45、貝1ax1(ax0)q1q1(modm)又若x1，則由qm/m,結(jié)論成立.x0若x1令x0q2x1x20x2x1貝Uax21q1q2(modm).又若x2，則由 m q1x0 x1。92玉x2)x1即 m (1 qiq2)xi5x2,故 1 qQm q1x2mxi結(jié)論成立。若 x2,又令 xi q3x2 x3, 0 x3 x2.則ax3(qi q2 q1q2q3)(mod m)重復(fù)上述討論：即若x3，則結(jié)論成立，若x3.又令x2q4x3x4,0x4x3x2(mod3)例解同余方程組x3(mod5)x2(mod7)解：Q模3,5,7兩兩互質(zhì)，故原方程組對(duì)模m357有唯一解35M11(mod3)得

46、M12(mod3)21M21(mod5)M1M11(mod3)即M21(mod5)15M31(mod7)M31(mod7)根據(jù)孫子定理方程組的解是注意到x0x1x2L,故有限步后，必有axny(modm)其中0xn,ym,即結(jié)論成立。2.孫子定理試解下列各題：(i) 十一數(shù)余三，七二數(shù)余二，十三數(shù)余一，問(wèn)本數(shù)。(ii) 二數(shù)余一，五數(shù)余二，七數(shù)余三，九數(shù)余四，問(wèn)本數(shù)。(楊輝：續(xù)古摘奇算法(1275)。x3(mod11)解：依題意得x2(mod72)x1(mod13)則據(jù)孫子定理，上述方程組有唯一解(modll7213)7273Ml1(mod11)f4Ml1;由1113M21(mod72

47、7;SM21；1172M31(mod13KM31；故原方程組的解是x39362(1)1431(1)7921730(mod10296).x1(mod2)x2(mod5)(ii)依題意得x3(mod7)x4(mod9)2、(i)設(shè)m1,m2,m3是三個(gè)正整數(shù)，證明：(m1,m3),(m2,mb)mnmh,m3.(ii)設(shè)d(m1,m2).證明：同余式組xb1(modm1),xd(modm2)(1)有解的充分與必要條件是d.b1b2.在有解的情況下，適合(1)的一切整數(shù)可由下式求出：其中Xi,2是適合1的一個(gè)整數(shù)。iii應(yīng)用i,ii證明同余式組xbmodmi,i1,2,L,k2有解的充分與必要條件是

48、(mi,mj)|(bi,bj),i,j1,2,L,k,并且有解的情況下，適合(2)的一切整數(shù)可由下式求出：其中Xi,2,L,k是適合(2)的一個(gè)整數(shù)。證明：im皿),皿,)(m3)(mm3)(m2m(m1,m3),(m2,m3)(mmmh)文檔來(lái)源為：從網(wǎng)絡(luò)收集整理.word版本可編輯.歡迎下載支持即(m1，m3)(m2,m3)(52皿甲3m2m3)(mi,m2,m3)(mmh)ii設(shè)(1)有解c,即cb1(modm1),cb2(modm2)故此得b1b2(mod(m1,m2),必要性成立；反之，設(shè)d1blb2即b1b2(modd)則由§1定理，知方程m1yb2b1(modm2)必有

49、解，設(shè)其角I為yyo(modm2),即m1yob2bi(modm2)令xi,2bimiyo則易見(jiàn)：x1,2b1(modm1)且X1,2b2(modm2)即(1)有解在2,充分性得證。進(jìn)一步，若(1)有解x,y,則即xy是mnm2的公倍數(shù)，當(dāng)然也是mnmh的倍數(shù)，故若X1,2是(1)的一個(gè)解，則(1)的任一解x必滿足x*,2(modm,m2)。(iii)若同余式組xbi(modmi),i1,2,L,k有解,rtxbi(modmi)則也有解。從而由(ii)知必有xbj(modmj)(mi,mj)|(b,bj),i1,2,L,k,必要性成立。下證充分性。首先，推(i),用歸納法易證：又由(ii)知k2時(shí)，充分性也成立；xb1(modm1)現(xiàn)設(shè)同余式組M有解xb(modmhL,mk1),x bk 1(modmk 1)文檔來(lái)源為:從網(wǎng)絡(luò)收集整理.word 版本可編輯.歡迎下載支持即 b bi (mod mi ),1 i k 1 。設(shè) bi b limi ,1 i k 1 ；又由條件知(mi , mk ) | (bi bk) ，而bibk(bbk)limi ，從而(mi,mk)| bibk,1i k 1 ，所以 x2 41(mod16) ，即 ( m1 ,m2,L ,mk 1 ,mk) b bk ，x b(mod m1,L ,mk 1 )又由 (i