初等數(shù)論練習題答案

1、初等數(shù)論練習題一一、填空題1、d(2420)=12;cp(2420)=8802、設a,n是大于1的整數(shù),假設aU是質數(shù),那么3、模9的絕對最小完全剩余系是卜4,-3,-2,-1QL2341.4、同余方程9x+12三0(mod37)的解是x三(mod37).5、不定方程18x-23y=100的通解是x=900+23t,產700+18t0.6、分母是正整數(shù)m的既約真分數(shù)的個數(shù)為_如_.7、181°°被17?除的余數(shù)是一辿.9、假設p是素數(shù),那么同余方程x>1l(modp)的解數(shù)為pT.二、計算題1、解同余方程:3/11x200(mod105).解：因105=357,同余方

2、程3x21x200(mod3)的解為x1(mod3),同余方程3x.llx380(mod5)的解為x0,3(mod5),同余方程3x°ll,x200(mod7)的解為x2,6(mod7),故原同余方程有4解.作同余方程組：xA(mod3),xbz(mod5),x&(mod7),其中b、=1»bz=0,3>&=2,6>由孫子定理得原同余方程的解為x13,55,58,100(mod105)°2、判斷同余方程X?三42(mod107)是否有解故同余方程x2=42(mod107)有解.3、求(127156+34)28除以in的最小非負余數(shù).解：

3、易知1271=50(mod111).由502三58(mod111),503三58X50三14(mod111),509=143=80(mod111)知5028三(509)3義50三8.3義50三8.3義50三68X50三70(mod111)從而50,6三16(mod111)(,故(127156+34)28三(16+34)28=5028=70(mod111)三、證實題1、p是質數(shù),(a,p)=1,證實：(1)當a為奇數(shù)時,ap-1+(p-l)a=0(modp)；(2)當a為偶數(shù)時,a-Cp-DO(modp).證實：由歐拉定理知三1(modp)及8-1尸三-1(modp)立得(1)和(2)成立.9n

4、2、設a為正奇數(shù),n為正整數(shù),試證a=l(mod2n+2)o(1)*證實設a=2卬1,當a二1時有才二(2卬1)2=4m(m1)11(mod23),即原式成立.2k設原式對于A二A成立,那么有aI(mod2*1),/=1或上：加1其中血,所以a-=(1或尸=1q21(mod2),其中q是某個整數(shù).這說明式(1)當a=A1也成立.由歸納法知原式對所有正整數(shù)a成立.3、設p是一個素數(shù),且lWkWp-l.證實：C；t(-1)"(modp)o證實：設人=?1(PK)得：kk!A=(p-1)(p-2)(p-k)=(-1)(-2)(-k)(modp)乂(k!,p)=1,故A=C；_1(一1)&q

5、uot;(modp)4、設p是不等于3和7的奇質數(shù),證實：p6三l(mod84).說明：由于84=4X3X7,所以,只需證實：p6=l(mod4)p6=l(mod3)p6=l(mod7)同時成立即可.證實：由于84=4X3X7及p是不等于3和7的奇質數(shù),所以(p,4)=1,(p,3)=1,(p,7)=1o由歐拉定理知:pG,=p2=l(mod4),從而p6=l(mod4)o同理可證：p6=l(mod3)p6=l(mod7)o故有p三1(mod84).注：設p是不等于3和7的奇質數(shù),證實：p',三l(mod168).(見趙繼源p86)初等數(shù)論練習題二一、填空題1、d(1000)=_16_

6、：o(1000)=_2340_.2、2021!的標準分解式中,質數(shù)11的次數(shù)是您3、費爾馬(Fermat)數(shù)是指Fn=22"+1,這種數(shù)中最小的合數(shù)Fn中的4、同余方程13x三5(mod31)的解是x三29(mod31)5、分母不大于m的既約真分數(shù)的個數(shù)為(力+(/+.+(而.6、設7|(80"-1),那么最小的正整數(shù)n=_0_.7、使41x+15y=C無非負整數(shù)解的最大正整數(shù)C=_559_.9、假設是質數(shù),np1,那么同余方程1(modp)的解數(shù)為n.二、計算題1、試求2002?®320tM被19除所得的余數(shù).解：由2002三7(mod19)20022=U(mo

7、d19)20023=1(mod19)又由三22004三(2?)m2三1(mod3)可得：200220G32.("=20()230+1=(20023)nX2002=7(mod19)2、解同余方程3x"4./6x180(mod5).解：由Fermat定理,x5x(mod5),因此,原同余方程等價于x30(mod5)將x0,1,2(mod5)分別代入上式進行驗證,可知這個同余方程解是x1(mod5)o3、a=5,m=21,求使a*1(modm)成立的最小自然數(shù)x.解:由于(5,21)=1,所以有歐拉定理知5三l(mod有).又由于(21)=12,所以xll2,而12的所有正因數(shù)為

8、1,2,3,4,6,12.于是x應為其中使5、1(mod12)成立的最小數(shù),經計算知：x=6.三、證實題1、試證131(5琬+4(川+2000).(提示:可取模13進行計算性證實)證實：54m+46n+2000252m+642n+2000(-1)2m+(-1)2n+200020020(mod13).2、證實Wilson定理的逆定理：假設n1,并且(a1)!1(modn),那么n是素數(shù).證實：假設a是合數(shù),即n二門也,1<a：<n,由題設易知(a1)!1(modnJ,得01(modnJ,矛盾.故是素數(shù).3、證實：設區(qū)表示全部由1組成的s位十進制數(shù),假設.是素數(shù),那么s也是一個素數(shù).證

9、實：假設S是合數(shù),即s=ab,l<a,bs.那么一二"二="3="二,其中“>是正整數(shù).999由R>1也是正整數(shù)知R是合數(shù),這與題設矛盾.故s也是一個素數(shù).4、證實：假設2P1是奇素數(shù),那么(r!(l)p0(mod2pl)o證實：由威爾遜定理知1(2p)!=pl(p1)(2p)(1)0(mod2r1),由此得3(1)P0(mod2Pl)o5、設p是大于5的質數(shù),證實：p4=l(mod240)o(提示：可由歐拉定理證實)證實：由于240=23X3X5,所以只需證：p4三l(mod8),p4=l(mod3),p4=l(mod5)即可.事實上,由(8)

10、=4,(3)=2,(5)=4以及歐拉定理立得結論.初等數(shù)論練習題三一、單項選擇題1、假設n>l,(n)=T是n為質數(shù)的(C)條件.A.必要但非充分條件B.充分但非必要條件C.充要條件D.既非充分乂非必要條件2、設n是正整數(shù),以下各組a,b使R為既約分數(shù)的一組數(shù)是(D).a=n+Lb=2n-1=2n-1,b=5n+2=n+Lb=3n+1=3n+1,b=5n+23、使方程6x+5y=C無非負整數(shù)解的最大整數(shù)(2是(A).4、不是同余方程28x三21(mod35)的解為(D).=2(mod35)B.x=7(mod35)C.x=17(mod35)D.x=29(mod35)5、設a是整數(shù),(l)a

11、=0(mod9)(2)a=2021(mod9)(3)a的十進位表示的各位數(shù)字之和可被9整除(4)劃去a的十進位表示中所有的數(shù)字9,所得的新數(shù)被9整除以上各條件中,成為91a的充要條件的共有(C).二、填空題1、0(2021)=,4896：q>(2021)=528o2、數(shù)C瑞的標準分解式中,質因數(shù)7的指數(shù)是_3.3、每個數(shù)都有一個最小質因數(shù).所有不大于10000的合數(shù)的最小質因數(shù)中,最大者是22.4、同余方程24x三6(mod34)的解是xi三13(mod34)X2三30(mod34)_.5、整數(shù)n>l,且(n-l)!+l三0(modn),那么n為素數(shù).6、3被U除所得余數(shù)是三、計算

12、題1、判定(i)2fy3x10(mod5)是否有三個解；(ii)x2x4y30(mod5)是否有六個解解：(i)2dG3x10(mod5)等價于x3x4x30(mod5),乂xx-(x3Y4x3)(a,:3x5)+(6Y12x15),其中r(x)=6a,:12x15的系數(shù)不都是5的倍數(shù),故原方程沒有三個解.(ii)由于這是對模5的同余方程,故原方程不可能有六個解.2、設a是正整數(shù),求C/,C短,.,CH的最大公約數(shù).解：設(C晨C黑,第丁)=力由G.+C1+C-T=221知龍?zhí)栐O2且2fB即2*"n,那么由2Mllc晨及2Kl<4=軍0之3,3,5,2a1得d=2.I3、a=1

13、8,m=77,求使a*1(modm)成立的最小自然數(shù)x.解：由于(18,77)=1,所以有歐拉定理知182三l(mod77).又由于(77)=60,所以xl60,而60的所有正因數(shù)為1,2,3,4,5,6,10,12,15,20,30,60.于是x應為其中使18、1(mod77)成立的最小數(shù),經計算知：x=30.四、證實題1、假設質數(shù)p25,且2p+l是質數(shù),證實：4p+l必是合數(shù).證實：由于質數(shù)pN5,所以(3,p)=1,可設p=3k+l或p=3k+2.當p=3k+l時,2p+l=6k+3是合數(shù),與題設矛盾,從而p=3k+2,此時2p+l是形如6k+5的質數(shù),而4p+l=12k+9=3(4k

14、+3)是合數(shù).故啕:伙"初等數(shù)論練習題四一、單項選擇題1、假設F產2*+1是合數(shù),那么最小的門是(D).A.2B.3C.4D.52、記號b'lla表示b'la,但以下各式中錯誤的一個是(B).A.2力120!B.105II50!C.Il9II100!D.1316II200!3、對于任意整數(shù)n,最大公因數(shù)(2n+l,6nT)的所有可能值是(A).A.1B.4C.1或2D.1,2或44、設a是整數(shù),下面同余式有可能成立的是(C).A.a:=2(mod4)B.a:=5(mod7)C.a2=5(mod11)D.a:=6(mod13)5、如果a三b(modm),c是任意整數(shù),那

15、么以下錯誤的選項是(A)A.ac=bc(modme)B.ma-bC.(a,m)=(b,m)D.a=b+mt,tGZ二、填空題1、d(10010)=_32_,4>(10010)=_2880_o2、對于任意一個自然數(shù)n,為使自N起的n個相繼自然數(shù)都是合數(shù),可取N=(n+1)!3、為使3n-l與5n+7的最大公因數(shù)到達最大可能值,整數(shù)n應滿足條件n=26k+9,k£Z.4、在5的倍數(shù)中,選擇盡可能小的正整數(shù)來構成模12的一個簡化系,那么這組數(shù)是5,25,35,555、同余方程26x+l三33(mod74)的解是三24(mod74)x三三61(mod74)_.6、不定方程5x+9y=8

16、6的正整數(shù)解是_x=l,y=9或x=10,y=4.7、三、計算題1、設a的十進制表示是13a>45z,假設792n,求x,y,2.解：由于792=8911,故79248n,9及1".我們有8A845Jz=6,以及9n913xy45z=19xy9xy(1)llnllz54yx31=3yx113yNo(2)由于0x,y9,所以由式與式分別得出xy1=9或18,3yx=0或Hox+y+這樣得到四個方程組：k:一,3>+A其中a取值9或18,6取值0或11.在0x,y9的條件下解這四個方程組,得到：x=8,y=0,z=6.2、求3儂的末二位數(shù).解：(3,100)=1,.*.3*(

17、100)=1(mod100),而4)(100)=4>(2252)=40,J3,0=l(mod100)J3106=(310)103$三(3丁3.三一19X9三一171三29(mod100)末二位數(shù)為29.3、求(214940)35被73除所得余數(shù).解：=(10241,+40)35三(2"+40)"三(2°X21+40尸5三+的)55三72"三一1三72(mod73)四、證實題1、設a,az,a是模卬的完全剩余系,證實：(1)當m為奇數(shù)時,&+as=0(modm)；(2)當m為偶數(shù)時,氏+a、+as=(modm).2證實：由于1,2,血與國,a

18、2,aj都是模勿的完全剩余系,所以Z=Z/=1-11-1(1)當m為奇數(shù)時,由竽中m故r-1=0(mod而o2(2)當m為偶數(shù)時,由(m,m+l)=l即得：£?="'十三竺(mod而.占22.(m)2、證實：假設m>2,4,電,a.是模卬的任一簡化剩余系,那么=0(modm).也是模m證實：假設包,比,a.是模m的一個簡化剩余系,那么卬-&,勿-%,(/n)<?(rn>p(/n)的一個簡化剩余系,于是：三?).從而：2Zq司必加)(1辿/).f-lr-lr-10(in)/又由于m2,(而是偶數(shù).故：2,三“竺*三°(,).3、設卬

19、0是偶數(shù),a,包,&與儂乩,&都是模卬的完全剩余系,證實：EA3zbiy,as6J不是模卬的完全剩余系.證實：由于1,2,血與a,a,a都是模勿的完全剩余系,所以Wm(m+1)w/x小Zq三=(modin)o(1)i=i/=!22同理2?乙三"(modni).(2)1=12如果abi,a：bzy,as6J是模卬的完全剩余系,那么也有£(q+d)三竺(modni)./=12聯(lián)合上式與式和式,得到0三竺+竺三竺(mod血,222這是不可能的,所以ab,azb二,)as6J不能是模卬的完全剩余系.4、證實：(1)2730Ix13-x；(2)24|x(x+2)(25

20、x：-l)；(3)504Ix5-x3；(4)設質數(shù)p>3,證實：6pIxp-xo證實：(1)由于2730=2X3X5X7X13,2,3,5,7,13兩兩互質,所以:由x13-x=x(x12-l)=0(mod2)知:2Ix13-x；13Ixl3-x；由x"-x=x(x13-l)=x(x2-l)(x2+l)(x8+x4+l)=0(mod3)知：3Ix13-x；由x'3-x=x(x13-l)=x(x4-l)(x8+x*+l)=0(mod5)知：5Ix13-x；由x13-x=x(x1:-l)=x(x5-l)(x6+l)=0(mod7)知：7Ix"-x.故有2730|x

21、13-xo同理可證同理(3理(4)o初等數(shù)論練習題五一、單項選擇題1、設x、y分別通過模m、n的完全剩余系,假設(C)通過模mn的完全剩余系.A.n都是質數(shù),那么mynxB.mWn,那么mynxC. (m,n)=L那么mynxD. (m,n)=1,那么mxny2aX3X5X-X2003X2005X2007X2021X2021標準分解式中11的幕指數(shù)是(A).3、n為正整數(shù),假設2-1為質數(shù),那么.是AoA.質數(shù)B.合數(shù)k為正整數(shù)4、從100到500的自然數(shù)中,能被11整除的數(shù)的個數(shù)是B.5、模100的最小非負簡化剩余系中元素的個數(shù)是Co二、填空題1、同余方程a/b三0mock?有解的充分必要條

22、件是a,mIb.2、高斯稱反轉定律是數(shù)論的酵母,反轉定律是指設.與4是不相同的兩個奇質數(shù),3-廣¥pq3、被3除所得的余數(shù)為_1_.4、設n是大于2的整數(shù),那么-5、單位圓上的有理點的坐標是士工.土曰或仕,其中a與6是不全為.+ra'+ba2+/>2«+/零的整數(shù).6、假設3258Xa恰好是一個正整數(shù)的平方,那么a的最小值為迄.7、2021是一素數(shù),那么工卜_-1_.U011三、計算題1、求3用土7m9*13必°的個位數(shù)字.解：383義78X13刈°三38的父-32021X32021=-32003-200-2021=-3W27=-3X(32

23、)3013=3(mod10).2、求滿足(mn)=(而+S)的互質的正整數(shù)m和n的值.解：由(m,n)=1知,(mn)=(zn)(n)<>于是有:(zn)+(n)=(zz?)(n)設向二a,5二b,即有：a+b=abo顯然aIb,且bIa,因此a二b.于是由2a=a,得a=2,即向二n=2o故m=3,n=4或m=4,n=3.3、甲物每斤5元,乙物每斤3元,丙物每三斤1元,現(xiàn)在用100元買這三樣東西共100斤,問各買幾斤解：設買甲物X斤,乙物/斤,丙物Z斤,那么5x3ylz=100,3xyz-100o消去z,得到7x4y=100o顯然x=0,y=25是方程(1)的解,因此,方程(1)

24、的一般解是=4f,tly=25-7t由于x>0,y>0,所以OVt3o即看可以取值t.=1,tz=2,t3=3o相應的X,y,z的值是(x,y,z)=(4,18,78),(8,11,81),(12,4,84).四、證實題1、20n是質數(shù),那么有20nl999.2021個證實：99-9=1020u-1=0(mod2021)o2021個2、設p是4n+l型的質數(shù),證實假設a是p的平方剩余,那么p-a也是p的平方剩余.證實：由于質數(shù)p=4n+l,a是p的平方剩余,所以(/t/P-1/4=1-=(-i)i-=ip)p)p八pip)即：p-a也是p的平方剩余.3、p,q是兩個不同的質數(shù),且三

25、1(modq),aQ-l=l(modp),證實：ag三a(modpq)o證實：由p,q是兩個不同的質數(shù)知(p»q)=lo于是由Fermat定理ap=a(modp),乂由題設a'三1(modp)得到：aM=(aQ)p=a!：(a3'1)p=a?=a(modp)o同理可證：aw=a(modq).故：ap,=a(modpq)o4、證實：假設m,n都是正整數(shù),那么(mn)=(m,n)(見n).證實：易知mn與血有完全相同的質因數(shù),設它們?yōu)?那么乂mn=(m,n).m,n故(p(nm)=(加,)|>從(1一一)(1一一)-(1一)=0PiPiPk類似的題:設gnm,叫與m

26、由相同的質因數(shù),證實：(m)=m?®).初等數(shù)論練習題六一、填空題1、為了驗明20n是質數(shù),只需逐個驗算質數(shù)2,3,5,p都不能整除2021,此時,質數(shù)p至少是_金o2、最大公因數(shù)(4n+3,5n+2)的可能值是_L2_.3、設3°|40!,而3""J4O!,即3"II40!,那么a二工4、形如3n+l的自然數(shù)中,構成模8的一個完全系的最小那些數(shù)是1,4,7,10,13,16,19,22o5、不定方程x'+y'z12；x,(x,y)=l,x,y,z>0的整數(shù)解是且僅是x=2勖,y二#F,z=d/,其中十>6>0

27、,(a,6)=1,a與6有不同的奇偶性.6、21x三9(mod43)的解是x三25(mod43)07、73199二、計算題1、將上寫成三個既約分數(shù)之和,它們的分母分別是3,5和7.105解:設9=.+、+彳,即35x21y15z=17,因(35,21)=7,(7,15)=1,1V/JJJ/117,故有解.分別解5x3y=tIt15z=17x=t3u,y-2t5,Z,t=1115v,z=47v,幾,消去看得x=1115y3u,y-2230r5,v2o令二0,.二一1得至lj：x二4,y二一8,=3o即：-=-+-1053572、假設3是質數(shù)P的平方剩余,問是什么形式的質數(shù)解：:由二次互反律二=(

28、_1)P)p-iT"注意到P>3,p只能為三±1(mod3)且:三I311p=l(mod4)-1p=-l(mod4)=1只能以下情況p=l(mod3)p=l(mod4)p=-l(mod3)p=-l(mod4),p=l(mod12)或p三-l(modl2).3、判斷不定方程f+23產17是否有解解：只要判斷/三17(mod23)是否有解即可.:17=1(mod4)A17(mod23)無解.,即原方程無解.三、論證題1、試證對任何實數(shù)X,恒有(x)+(x+i)=(2x)2證實：設x=x+.,0W當時,x+i=X,2x=2x等式成立22當時,x+i=x+l,2x=2x+l工

29、等式成立22故對任何實數(shù)X,恒有區(qū)+卜+'=2X.22、證實：(1)當n為奇數(shù)時,3|(2,1)；(2)當n為偶數(shù)時,3/(2n+l)o證實：由2“+1三(-1)n+l(mod3)立得結論.3、證實：(1)當31n(n為正整數(shù))時,7|(20-1)；(2)無論n為任何正整數(shù),7l(2n+l)o證實：(1)設n=3m,貝lj2匚1=8n1三0(mod7),即：7|(2n-l)；(2)由于23nl=1(mod7)得2+1=2(mod7)»21+1=3(mod7),2+1=5(mod7).故無論n為任何正整數(shù),7J(2n+l)o4、設m>0,n>0,且m為奇數(shù),證實：(

30、2工-1,2n+1)=1.證實一：由m為奇數(shù)可知：2n+lI2m+b又有2y|2.1,于是存在整數(shù)x,y使得：2"1xY'l,2Ty=2嘰1.從而2a+lx-2B-ly=2o這說明:2B-1,2n+l|2由于2*+1,2=-1均為奇數(shù)可知：2口-1,21二1.證實二：設2"-1,2n+l=d,那么存在s,t£Z,使得2'=sd+l,2n=td-lo由此得到:2mH=sd+1n,2m=td-lm于是2-pd+-qd-1,p,所以：q-pd=2.從而d2,就有,=1或2.由由于m為奇數(shù),所以"二1.即(2m-l,2n+l)=lo注：我們已證過

31、：記M=2*1,對于正整數(shù)a,b,有M,其=理.顯然當aWb,a,b為質數(shù)時,必必=lo初等數(shù)論練習題七一、單項選擇題1、設a和b是正整數(shù),那么巨業(yè)1,必4=AabA.1B.aC.bD.a,b2、176至545的正整數(shù)中,13的倍數(shù)的個數(shù)是BA.27B.28C.29D.303、200!中末尾相繼的0的個數(shù)是AA.49B.50C.51D.524、從以下滿足規(guī)定要求的整數(shù)中,能選取出模20的簡化剩余系的是BA.2的倍數(shù)B.3的倍數(shù)C.4的倍數(shù)D.5的倍數(shù)5、設n是正整數(shù),以下選項為既約分數(shù)的是A.21/1+4二+1?2-1cn+1A.B.C.D.14/7+32n-15n+23+1二、填空題1、31

32、4被163除的余數(shù)是_1_.(歐拉定理)2、同余方程3x=5(modl3)的解是x三5(modl3).4、-n=-4o5、為使n-1與3n的最大公因數(shù)到達最大的可能值,那么整數(shù)n應滿足條件n=3k+l,k£Z.6、如果一個正整數(shù)具有21個正因數(shù),問這個正整數(shù)最小是26X36576.7、同余方程x3+x:-x-l=0(mod3)的解是x三1,2(mod3).三、計算題1、求不定方程X2y3z=41的所有正整數(shù)解.解：分別解x2y=ttZz二41得x-t2uy-uZ,t=413vz-V%消去t得at=413v2uy-uz-vu,由此得原方程的全部正整數(shù)解為(x,y,z)-(413v2uy

33、u,v),>0,v0,413v2u>0.2、有一隊士兵,假設三人一組,那么余1人；假設五人一組,那么缺2人；假設十一人一組,那么余3人.這隊士兵不超過170人,問這隊士兵有幾人解：設士兵有x人,由題意得x1(mod3),x2(mod5),x3(mod11)o在孫子定理中,取生二3,生二5,雄二11,卬二3511=165,M,=55,業(yè)二33,屈二15,M,=1,M=2,叢=3,那么x1551(-2)332315358(mod165),因此所求的整數(shù)X=52+1651,tZo由于這隊士兵不超過170人,所以這隊士兵有58人.3、判斷同余方程X?三286(mod443)是否有解解：28

34、6=2X143,433是質數(shù),(143,443)=1奇數(shù)143不是質數(shù),但可用判定雅可比符號計算的勒讓德符號=1原方程有解.143-1=(-1)四、證實題1、設(a,ni)=1,4是使a'1(mod卬)成立的最小正整數(shù),那么(i)&®；(ii)對于任意的f,j0i,j&1,ij,有(mods).(1)證實：(i)由Euler定理,&(加,因此,由帶余數(shù)除法,有(in)=r,qZ,q>0,0r(因此,山上式及的定義,利用歐拉定理得到1,產)="泌+'三/(mod面,即整數(shù)r滿足a'1(modm),0r<4.由的定義可

35、知必是r=0,即“(加.(ii)假設式(1)不成立,那么存在f,j,0i,j41,ij,使a'a:(modni)o不妨設i>jo由于(a,而二1,所以az'0(modni),0<iJ<4.這與的定義矛盾,所以式(1)必成立.2、證實：設a,b,c,卬是正整數(shù),m>1,(6,向二1,并且ba1(mod而,b1(modni)(1)記,二(a,c),那么ba1(modni).證實：由裴蜀恒等式知,存在整數(shù)x,y,使得axcy二d,顯然xy<0.假設x>0,y<0,由式(1)知：16"=bdbC7=blb>7bd(mod揄.假設

36、x<0,y>0,由式知：1bcy=b名展bba)xbd(mod而.3、設是素數(shù),pb1,由,那么下面的兩個結論中至少有一個成立:(i) pbd1對于n的某個因數(shù)n成立;(ii) p1(modn).假設2)a,p>2,那么(ii)中的mod牙可以改為mod假設.證實：記d=5,p1),由/bbp11(modp),及第2題有bc1(modp)o假設m那么結論(i)得證.d-n,那么即1,即p1(modn),這就是結論(ii).假設2/mp>2,那么1(mod2).由此及結論(ii),并利用同余的根本性質,得到p1(mod2h)o初等數(shù)論練習題八一、單項選擇題1、設a>

37、1,那么為素數(shù)是(/21)!1(modn)的(C).A.必要但非充分條件B.充分但非必要條件C.充要條件D.既非充分又非必要條件2、小于545的正整數(shù)中,15的倍數(shù)的個數(shù)是(C)3、500!的標準分解式中7的幕指數(shù)是(D)4、以下各組數(shù)中,成為模10的簡化剩余系的是(D),9,-3,1,1,7,9,7,11,13D.1,1,3,35、設n是正整數(shù),以下選項為既約分數(shù)的是A,3n+1口n+12n1p.n+1A,d.i.u.5n+22n-l5n+23n+1二、填空題1、.(120)=360o2、7355的個位數(shù)字是3.3、同余方程3x三5(modl4)的解是x三1l(modl4).4、()=102

38、3一5、-&=26、如果一個正整數(shù)具有6個正因數(shù),問這個正整數(shù)最小是12.7、同余方程x'+x2-x-l=0(mod5)的解是乂三±l(mod5).三、計算題1、5知是素數(shù),判定方程x2429(mod563)是否有解.解：把(即看成Jacobi符號,我們有I.563)(429、/八(563旃尸再H旃1=<429>(13)與號(27)(1)127；113；113J故方程x2429(mod563)有解.2、求出模23的所有的二次剩余和二次非剩余.解：模23的所有的二次剩余為xl,2,3,4,6,8,9,12,13,16,18(mod23)；模23的所有的二次非

39、剩余為x5,7,10,11,14,15,17,19,20,21,22(mod23).3、試求出所有正整數(shù)A,使得1"+2八+3'+4c能被5整除.解：假設n為奇數(shù),Mr+2a+3n+4flln+2fl+(-2)(-1)"0(mod5)；假設n=2m,mez,那么1=+2八+3"+4產+2*+(-2)(-1)2a2+2X2*=2+2X4°=2+2X(-DYmod5)；當m為奇數(shù)時,/+20+3"+4為奇od5)；當m為偶數(shù)時,l3+2n+33+r4(mod5).故當4Jn時,5|ln+2fl+3n+4fl0四、證實題1、證實：假設質數(shù)p&

40、gt;2,那么2.1的質因數(shù)一定是2pk+l形.證實：設q是2"-1的質因數(shù),由于2,-1為奇數(shù),qW2,(2,q)=1.由條件q2-1,即2,三1(modq).設方是使得2,三1(modq)成立最小正整數(shù),假設那么有力p.這與p為質數(shù)矛盾.從而h=p,于是ptrio乂丁為偶數(shù),2；/112p1,rl=2pk,即q=2pk+lkGZ.2、設(m,n)=1,證實：m"+n0=1(modmn)o證實：由于(m,n)=1,所以由歐拉定理知：n=1(modm),m"=1(modn)于是mn)+n'=1(modm),m'+n,a>=1(modn)o乂由

41、于(m,n)=1,所以m"'+n'=1(modmn).注：此題也可這樣表述：假設兩個正整數(shù)a,b互質,那么存在正整數(shù)m,n,使得ax+ba=l(modab)onp+3、設(a,b)=1,a+bWO,p為一個奇質數(shù),證實：(.+d)=1或p.a+b說明：事實上,設("+4心£)=4,只需證實：dP即可.a+b證實：由a+b三0(moda+b),即a三-b(moda+b),知a"三(-b)(moda+b)o其中又.+lyP=Sb+一心2+產三+產+(nx)da+).a+h令(a+b,匚上)=d,貝ljd又(a,b)=1,d|(a+b)知(d,

42、b)=1.a+b(否那么設(d,b)=d'>1,立即得到d'Ia和d'Ib,這與(a,b)=1矛盾.)于是(d,D=lo故dp,即d=1或p.初等數(shù)論練習題九一、單項選擇題1、以下Legendre符號等于T的30被T是(D)2、100至500的正整數(shù)中,能被17整除的個數(shù)是(B)A.23B.24C.25D.263、設3a1500!,但30+11500!,那么.=CA.245D.2484、以下數(shù)組中,成為模7的完全剩余系的是(C)A.-14,-4,0,5,15,18,19B.7,10,14,19,25,32,40C.4,2,8,13,32,35,135D.-3,3,

43、4,4,15,5,05、設a是正整數(shù),那么以下各式中一定成立的是(B)B.(2nIt2n+l)=1C.,/?+l)=1D.(2n+l,n-l)=1二、填空題1、257%被50除的余數(shù)是匚2、同余方程3才三5(modi6)的解是x三7(mod16).3、不定方程9X一12戶15的通解是x=-1+4t,y=-2+3匕Z4、二1.I41J5、實數(shù)的小數(shù)局部記為*,那么-2=.4-6、為使3A與4a+1的最大公因數(shù)到達最大可能值,整數(shù)應滿足條件WA+2,k£Z.7、如果一個正整數(shù)具有35個正因數(shù),問這個正整數(shù)最小是26乂31二5184.三、計算題1、解不定方程9x+24y51000.解：解因

44、(9,24)=3,(3,-5)二1知原方程有解°原方程化為J9x24y=3b即J3x8y=t,(1)3t-5z=10003t-5z=1000,(2)解得t=5uZ=-200+3uhe小x=-u+8v再解3x8y=5u得到,u,%y=u-3vX=-M+8v故"y=u-3v,u,vZoZ=-200+3m2、設月二科生,xj是模卬的一個完全系,以3表示x的小數(shù)局部,假設血二i,求£竺約./-I"?解：當X通過模.的完全剩余系時,ax6也通過模卬的完全剩余系,因此對于任意的f(lim),ax：6一定與且只與某個整數(shù)J(1jm)同余,即存在整數(shù)k,使得axib-k

45、mj；(0jm-1).從而：3、設整數(shù)a2,求：即在數(shù)列1,2,口中,與口互素的整數(shù)之和.1</<«解：設在1,2,A中與A互素的(加個數(shù)是包,32,4用,(a；,n)=1,1&n1,1i(n),那么(n3i,n)=1,1n4n1,1i(n),因此,集合包,a2,a®與集合a&,na2,na®是相同的,于是aa2a<B)=naj(naj(na),2(aa2a(,)=n(n),因jht：axaza-n(ii)o24、設卬?1,(a,ni)=1,超,M是模卬的簡化剩余系,求：其中»表示x的小數(shù)局部.解：設ax：二卬q二,0斐

46、勿,由X；通過模卬的簡化剩余系知：ax：也通過模卬的簡化剩余系,從而匚通過模R的最小非負簡化剩余系,于是：zLlJ=£/+J=.iZhi營m營mm2in2四、證實題1、證實：設a是有理數(shù),b是使ba為整數(shù)的最小正整數(shù),假設c和ca都是整數(shù),那么b|co(提示：利用帶余數(shù)除法解決.)證實：設c=bq+r,OWrVb,q£Z,那么ca=(ba)q+ra.由于ca,baGZ,所以raWZ,于是ra=0,由aWO得尸0.故b|c.2、設是素數(shù),證實：(i)對于一切整數(shù)x,f'1(x1)(x2)(*p1)(modp)；(ii)(p1)!1(modp).證實：(i)az110(

47、modp)有解x1,2,p1(modp),故對于一切整數(shù)x,f'1(x1)(x2)(xp1)(modp)；<>(ii)在(i)中令x二p.3、證實：假設2/n,p是奇質數(shù),pIan-l,那么j=1o證實：由pIan-l知：a"1(modp)o又(p,a)=1得到a1a(modp)o+1c由于2In,所以(42)2三(mod),BJx"a(modp)有解.故=1oP)4、證實：假設p=1m+l是一質數(shù),那么(")=1.P證實：(竺)=()=(二1)=(-1),=(-1產=1.ppP5、設,是奇質數(shù),p1(mod4),那么：(±(與1)!

48、)21(modp)解由Wilson定理有：注：1設夕為質數(shù)且=4/1,那么同余方程/三一imod的解是x三±122/modp.2設p為質數(shù)且p=4加L假設且唯假設存在一個正整數(shù)a,使得才三1modpo初等數(shù)論練習題十一、單項選擇題1、設夕是大于1的整數(shù),如果所有不大于后的質數(shù)都不能整除,那么P一定是AoA.素數(shù)B.合數(shù)C.奇數(shù)D,偶數(shù)2、兩個質數(shù)p,q,滿足p+q=99,B.把194那么K+g的值是qpc941399B)D.四1113、2021!的標準分解式中,7的最高事指數(shù)為CA.331B.332C.333D.3344、n為正整數(shù),假設才斗1為質數(shù),那么.是DA.質數(shù)B.合數(shù)C.1D.2*k為非負整數(shù)5、當n>2時,歐拉函數(shù)®一