初等數(shù)論習(xí)題

第三章1.解依次計算同余式224，2416，28256，216=65536154，2321542=237161(mod641)。因此2.解有713，721(mod10)，r因此，若77(mod4)，則現(xiàn)在77(1)713(mod4)，所以由上式得到n即的個位數(shù)是3。m對模的同余，可分以下步驟進(jìn)行：3.注：一般地，若求k(ⅰ)求出整數(shù)，使a*km1(mod)；rrkrk(ⅱ)求出正整數(shù)，<，使得b*c(mod)；arm*(mod)。(ⅲ)4.例3求(2573346)26被50除的余數(shù)。解(2573346)26(7334)26=[7(72)164]26[7(1)164]26=(74)26326=3(35)53(7)5=37(72)22129(mod50)，即所求的余數(shù)是29。5.證明2x2-5y2=7沒有整數(shù)解.maaambb6.例1設(shè)>01,2,,}與{1,2,,}都是模的完全剩bmm余系，證明：abab{11,22,,ambmm}不是模的完全剩余系。Axxxm7.例2設(shè)={1,2,,}是模的一個完全剩余系，以mxxam{}表示的小數(shù)部分，證明：若(,)=1，則8.xxx}m9.例3設(shè){1,2,…,(m)是模的簡化剩余系，則xxx(12…(m))*21(modm。)xxx，(Pm。yi解記P=12…(m)則,)=1又記=im，1()y,y,ym(m)}也是模的簡化剩余系，因此則{12mrP*2P*(m)1(modm(mod)，再由Eule定理，推出)**同余式可以像等式一樣進(jìn)行代換。第二章1.利用輾轉(zhuǎn)相除法求解abcab2.例3設(shè)，，是整數(shù)，(,)=1，則在直線axbyc=上，任何一個長度大于的線段上至少有一個點的坐標(biāo)都是整數(shù)。解由定理1，直線axbyc=上的坐標(biāo)都是整數(shù)的xtyt(,)的坐標(biāo)是t，Z，x0y0其中(,)是直線axbyc=上的坐標(biāo)都是整數(shù)的點，由定理2，這樣的點是存在的。tPtxtyt對于任意的Z，記是以(,)為坐標(biāo)的點，則Pt1Pt與之間的距離這說明，兩個“相鄰的”坐標(biāo)是整數(shù)的點的距離是，從而得出所求之結(jié)論。3.例2將寫成三個分?jǐn)?shù)之和，它們的分母分別是2，3和5。解：設(shè)xyz則15106=19。tzxyt依次解方程56=19，1510=5，得到Z，uuv，,Z。uvxy取=0，=0，得到=1，=1，=4，因此zxyz4.若(,,)是方程(1)的滿足條件(2)的解，則下面的結(jié)論成立：xy(ⅰ)(ⅱ)(ⅲ)與有不同的奇偶性；xy與中有且僅有一個數(shù)被3整除；xyz，，中有且僅有一個數(shù)被5整除。xyzxyz證明(ⅰ)若2，2，則2，這與(,,)=1矛盾。xyxy所以與中至少有一個奇數(shù)。如果與都是奇數(shù)，則xyxy2=4m+1,，2=4n+1，22=4(m+n)+2,z2而=4N或4N+1,xyz所以，，不可能是方程(1)的解。xy因此，與有不同的奇偶性。第四章1.x2.1022(mod36)xx等價于解不定方程10-36y=22求整數(shù)，再按模36分類：x1336x3136(mod)(mod)3.12961125(mod1935)解（1296，1935）=9，9|1125，故同余式有9個解xx化簡為144125(mod215)4.從另一角度考慮（1）當(dāng)(a,)=1時,(2)恰有一個解：axbm(mod)(2)（2）當(dāng)(a,)=d≠1時,(2)有解時有d個解,且d|bx5.1022(mod36)兩種解法：x13x3136(mod)36(mod)x6.12961125(mod1935)解（1296，1935）=9，9|1125，故同余式有9個解x化簡為144125(mod215),故7.解同余方程組解將(1)的前一式乘以2,后一式乘以3再相減得到y(tǒng)194(mod7)，y54(mod7)，y2(mod7)。再代入(1)的前一式得到x3101(mod7)，x4(mod7)。xy即同余方程組(1)的解是4，2(mod7)8.七數(shù)余一，八數(shù)余一，九數(shù)余三，問此數(shù)？9.pp10．（Wilson定理)(1)!+10(mod)即模p的一個簡化剩余系中全體數(shù)之積對模p與-1同余。p證明(1)由Fermat定理，數(shù)1,2,,1是同余式xpp11(mod)的解，因此，利用定理2即有。(2)在（1）中取=即可注：Wilson定理其實是充要條件，即xp。ppp是素數(shù)當(dāng)且僅當(dāng)(1)!+10(mod)n定理4（Lagrange）同余方程(1)的解數(shù)，即最多有n個解n證明假設(shè)同余式(1)解數(shù)多于n,則至少有+1個不同的解，設(shè)xxip(mod)，1in1為（1）的n+1個不同的解,則由定理2，有fxanxxxxnp()(1)()(mod)，因此fxn+anxn+xxn+xnp0(1)(11)(1)(mod)。pi，所以上式不能成立。這個矛盾說(mod)，1panxnxi由于，+1n明同余方程(1)不能有1個解。證畢。注:(1)此定理僅對質(zhì)數(shù)模同余式成立.如x3x0(mod6)有6個解p(2)若同余式（1）解數(shù)大于n,則整除所有系數(shù)(3)由定理1，4知:(1)的次數(shù)>p時，(1)的解數(shù)<n;:(1)的次數(shù)n≤p時，(1)的解數(shù)可能等于n;第一章nn1.例1若是奇數(shù)，則821。nk解設(shè)=21，則nkkk21=(21)21=4(1)。kkn在和1中有一個是偶數(shù)，所以821Add2.例2設(shè)={1,2,,dkn}是的所有因數(shù)的集合，則Bn也是的所有因數(shù)的集合。=解由以下三點理由可以證得結(jié)論：AB(ⅰ)和的元素個數(shù)相同；(ⅱ)若diA，即din，則n，反之亦然；(ⅲ)若di，則aaa3.例3證明：方程122232=1999（1）無整數(shù)解。aaaAAA解若1，2，3都是奇數(shù)，則存在整數(shù)1，2，3，使得aAaA12=811，22=821，32=831，aA于是aaaAAA122232=8(123)3。aaa由于1999被8除的余數(shù)是7，所以1，2，3不可能都是奇數(shù)。aaaaaa由式(1)，1，2，3中只能有一個奇數(shù)，設(shè)1為奇數(shù)，2，3為偶數(shù)，則存在AAA整數(shù)1，2，3，使得aAaAra12=811，22=82，32=83，As于是aaa122232=8(123)1r，AAArsaaa其中和是整數(shù)，而且只能取值0或4。這樣122232被8除的余數(shù)只可能aaa是1或5，但1999被8除的余數(shù)是7，所以這樣的1，2，3也不能使式(2)成立。a注（1）定理中未要求的正負(fù)；（2）將>0換成<0也對，此時的范圍換成0≤r<-b即可；bbrabbqr（3）合起來即：設(shè)與是兩個整數(shù)，0，則存在唯一的兩個整數(shù)和，使得abqrrb=，0<||。4.由于每個非零整數(shù)的約數(shù)的個數(shù)是有限的，所以一組不全為零的整數(shù)的最大公約數(shù)是存在的，并且是正整數(shù)。aaaaa若1,2,,k兩兩互素，則可以推出(1,2,,k)=1，反之則不然，例如a(2,6,15)=1，但(2,6)=2a5.推論設(shè)是大于1的整數(shù)，且標(biāo)準(zhǔn)分解式為則：定理2任何大于1的整數(shù)a都至少有一個質(zhì)因數(shù)a證明若是質(zhì)數(shù)，則定理是顯然的。addd若不是質(zhì)數(shù)，那么它有兩個以上的正的非平凡因數(shù)，設(shè)它們是1,2,,k。ddee不妨設(shè)1是其中最小的。若1不是質(zhì)數(shù)，則存在1<1，2<d，使得1=deeeea12，因此，1和2也是的正的非平凡因數(shù)。這與1的最小性矛盾。所以1dd是質(zhì)數(shù)。a推論任何大于1的合數(shù)必有一個不超過的質(zhì)因數(shù)。add證明使用定理2中的記號，有=12，其中dda1>1是最小的質(zhì)因數(shù)，所以1*2。xy性質(zhì)設(shè)與是實數(shù)，則xxxxx(ⅰ)=[]+{},若0<1，則[]=0；xyxy(ⅱ)[][]；xxxx-x(ⅲ)[]≤<[]+1,1<[]≤x,x0≤{}<1;mmxmx(ⅳ)若是整數(shù)，則[]=[]；x(ⅴ)[][][yx+yxyx+y}],{}{}≥{x(ⅵ)[]=x{}=(ⅶ)(帶余數(shù)除法)若a,b是兩個整數(shù)，b>0，則(ⅷ)若a,b是任意兩個正整數(shù)，則不大于a而為b的倍數(shù)的正整數(shù)個數(shù)是6.設(shè)n是正整數(shù)，1kn1，則若n是素數(shù)，則n1kn1aaa7.例1設(shè)1,2,,n是整數(shù)，且aaaaaan12n=0，12n=，則4。nnnaaa解如果2不整除，則,1,2,,n都是奇數(shù)。于是12n是奇數(shù)個奇aaanaaa數(shù)之和，不可能等于零，這與題設(shè)矛盾，所以2，即在1,2,,n中至少有一aa個偶數(shù)。如果只有一個偶數(shù)，不妨設(shè)為1，那么2不整除i（2i）。此時有等式aaa2n=1，na在上式中，左端是(1)個奇數(shù)之和，右端是偶數(shù)，這是不可能的，因此，在1,aan2,,n中至少有兩個偶數(shù)，即4。aaafxaxaxa例2設(shè)0,1,,nZ，()=nn10，已知(0)與(1)fffx都不是3的倍數(shù)，證明：若方程()=0有整數(shù)解，則faaana3(1)=012(1)nx解對任何整數(shù)，都有xqrrq=3，=0，1或2，Z。rxqq(ⅰ)若=0，即=3，Z，則fxfq()=(3)=(3)n(3)anqa1qa0=3Q1a0=3Q1(0)，Q1ffx其中Z，由于(0)不是3的倍數(shù)，所以()0；rxq(ⅱ)若=1，即=31，Z，則qfxfqanqa1q()=(31)=(31)n(31)a0Q2ana1a0Q2f=3=3(1)，Q2ffx其中Z。由于(1)不是3的倍數(shù)，所以()0。fx因此若()=0有整數(shù)解，則必有xxqqq=32=31，Z，fxfqanqa1q于是0=()=(31)=(31)n(31)a0=3Q3a0a1a2anQ3f(1)n=3+(1)，Q3其中Z。所以3(1)=fa0a1a2an(1)*n。ab例3設(shè)，是整數(shù)，且92aabb2(1)ab則3(,).解由式(1)得到ababab9()233()23abab3()23ab(2)ab9()2再由式(1)得到abab933ab因此，3或3。abba若3，由式(2)得到3；若3，由(2)式也得到3。因此，總有3且3。abab3(,)。則a例4若>1，ana1是素數(shù)，則=2，并且是素數(shù)。na解若>2，則由anaan1an21=(1)(1)可知ana1是合數(shù)。所以=2。nnxyxy若是合數(shù)，則=，>1，>1，于是由xyx21=(21)(22(x(y1)