初等數(shù)論試題庫

#解同余式56M1三1(mod5)35M2三1(mod8)40M3三1(mod7)5 5 5得到Mi=1,M'2=3,M‘3=3于是所求的解為x三5612 35334031(mod140)三267(mod280)所以x三267(mod280).證：因為4,5,7兩兩互素,所以可以利用孫子定理求解.M1=35,M2=28,M3=20,m=140解同余式35M1三1(mod4),28M2三1(mod5),20m3=1(mod7),得到M1=-1,M匕=2,M‘3=-1于是所求的解為x三35(—1)32822 20(—1)6(mod140)三97(mod140)解：因為5,8,7兩兩互素，所以有解利用孫子定理求得M1=56,M2=35,M3=40.m=28°解同余方程56M；三1(mod5),35M2=1(mod8),40M3三1(mod7),得至UM「=1,M‘2=3,M‘3=3.于是所求的解為x三561(-3)353(-5) 4031(mod280)得x三267(mod280).解因為7,8,9兩兩互素，所以可以利用孫子定理.M1=72,M2-63,M3=56,m=494解同余式72Ml三1(mod7),63M2三1(mod8),56M3三1(mod9),得至1」M1=4,M,2=T,MI=-4.于是所求的解為解：因為4,5,7兩兩互素，所以可以利用孫子定理求解x三1(mod4)?x三1(mod5)原方程即為M三-3mod7)M1=35,M2=28,M3=20,m=140解同余式35M1三1(mod4),28M2三1(mod5),20M3=1(mod7),得至yM1=-1,M12=2,M13一1.于是所求的解為x三35(-1)1 2821 20(-1)(_3)(mod140)=81(mod280)所以x三81(mod140).解：因為5,8,9兩兩互素，所以有解利用孫子定理求得i=72,M2=45,M3=40.m=360M解同余方程72M1三1(mod5),45M2三1(mod8),40M3三1(mod9),得到M/=3,MS=5,MH=—2于是所求的解為x=7232 4535 40(-2)(-6)(mod360)得x三147(mod360).三、證明(1)A、敘述威爾遜定理。B.證明若(m-1"，1=0(modm),則m為素數(shù)(2)證明當(dāng)n是奇數(shù)時，有3(??(3)敘述并且證明歐拉定理。(4)解同余方程17八-2(mod25)敘述并且證明帶余除法定理。敘述并且證明費爾馬小定理。(7)證明：若則當(dāng)：通過模匚的完全剩余系時，貝U—「也通過模的完全剩余系.答案(1)A.(威爾遜定理)整數(shù)/是素數(shù)，則匚--■W證：若m不是素數(shù)，則m=ab1：a,b<m,則a|(mT)!,a|(m-1)!*1,則有aI1不可能，所以m是素數(shù)。⑵證明：因為2=T(mod3),所以2n+1三(一1)n+1(mod3).于是，當(dāng)n是奇數(shù)時，我們可以令n=2k1.從而有2n+1三(—1)2k++1三0(mod3),

即3（2。1）.⑶歐拉定理）若 則「°證明：設(shè)Fi是模匚的一組互素剩余系.T小喊由§2.2定理知磯同％附是模肌的一組互素剩余系.' ' 即‘：（值J）?1（廣12???心偉））；01…伽）鬧町/./叫三l（tnod閻⑷解：因為（17,25）=1,所以同余方程17^"2（mod25）有一解⑸）帶余除法定理且’ 」V廠匚使得一 成立,證明：（存在性）作整數(shù)序列：…臨廣地臨（U2&3…對于」必存在一個整數(shù)：使得--匚-」成立令 即：一惟一性）：若 使得'1 '<■'lr?il=ki-d又-「0VA-r|<i二Q￡g笛|〈1又：g?]EZ,,g-盤=o即g.g】從而有:*■'是惟一的.a=a(modp)(modp),⑹費爾馬定理：對任意的素數(shù)pa=a(modp)(modp),若（a,p）=1,由歐拉定理有a"（modp）兩邊同乘a即有⑺證明：當(dāng)，通過模匚的完全剩余系〔； '時，令4邙馬+力212-朋則■'■"". L'■'■'■■.'■■■■一否則，-’一-'?‘使得即直角十心-""A+A(niodm).'.aai又- -這與； 、是模匚的一組完全剩余系矛盾.■〔一■八；構(gòu)成模匚的完全剩余系.即衛(wèi)丁+;也通過模的完全剩余系四、綜合應(yīng)用(1)解方程X47x4=0(mod27) (10分)解：由X47x4=0(mod3)得x="mod3)得x=1+3t代入X47x4三0 (mod9)有11t=~1(mod3)有=1i代入x=1+3t得x=40代入x47x4=0(mod27)有-h=2(mod3)h=2啊代入有x=2227t2即x=22(mod27)(2)設(shè)2P+1為素數(shù)試證(P!)2(-1)p=0(mod2PT)(10分)答案證：因n=2P+1為素數(shù)，由威爾遜定理5-1)!'(modn)即有(n-1)!1三(n-1)(n-2) 321三1(n-1)2(n-2)p(n-p)1(modn)=(P!)2(-1)P1=0(mod2P1)即證p(3)設(shè)P=4n+3是素數(shù)，證明當(dāng)q=2p+1也是素數(shù)時，梅森數(shù)Mp=2T不是素數(shù)。(10分)答案2_證：因q=8n+7,由性質(zhì)2是q=8n+7的平方剩余， (?=1(modq)即q|24n，；-13.所以梅森數(shù)Mp=2-1不是素數(shù)。(4) 3c3小3證x 3y9z無正整數(shù)解。(8分)答案3 3 3證：假設(shè)x3y=9z有解，設(shè)(X,y,z)是一組正整數(shù)解，則有x是3的倍數(shù)，設(shè)X=3xi,又得至Uy為3的倍數(shù)，設(shè)i，又有i，xi3yi=9zi則有解區(qū)，％,乙)且z>zi這樣可以一直進行下去，z>zi>z2>z3>z4>???但是自然數(shù)無窮遞降是不可能的，于是產(chǎn)生了矛盾(5)設(shè)n是大于2的整數(shù)，證明「5)為偶數(shù)(iO分)答案證：因為由，n)=i,由歐拉定理有(-J(nAi(mod門)，因為n大于2,只有"n)為偶數(shù)。(6)如果整系數(shù)的二次三項式P(x)=xbxc當(dāng)x=O'i時的值都是奇數(shù)，證明 p(x)=O沒有整數(shù)根(8分)答案：證：由條件可得c為奇數(shù)，b為偶數(shù)2如果p(x)=0有根q,若q為偶數(shù)，則有qbqc為奇數(shù)，而p(q)=0為偶數(shù)，不可能，若q為奇數(shù)，則有q2bqc為奇數(shù)，而p(q)=0為偶數(shù)，也不可能，所以P(x)=0沒有整數(shù)根(7)解方程45x=21(mod132).(10分)答案：解因為(45,132)=3|21,所以同余式有3個解.將同余式化簡為等價的同余方程 15x=7(mod44).我們再解不定方程15x-44y=7,得至一解(21,7).因此同余式的3個解為x三21(mod132)132Jx三21(mod132)三65(mod132)3 ,132x三212 (mod132)三109(mod132)3(8)證明：用算術(shù)基本定理證明V是無理數(shù)。(10分)答案：P證：假設(shè)-3是有理數(shù)，則存在二個正整數(shù)p,q,使得.3=q,由對數(shù)定義可22得有3q=p，則同一個數(shù)左邊含奇數(shù)個因子，右邊含偶數(shù)個因子，與算術(shù)基本定理矛盾。?一 3為無理數(shù)。(9)、證明：對任何正整數(shù)n，若n不能被4整除，則有5|1n2n3n4n(10分)答案：_ 4 —證：則題意知n=4q+r，r=1，2，3。因為。,5)=1,i=1,2,3,4所以有i=i(mod5)當(dāng)r=1時有?2 34三0(mod5)當(dāng)r=2時有12223242三0(mod5)當(dāng)r=3時有13233343=0(mod5)從而證明了結(jié)論。(10)、解不定方程4x+5y=i0(10分)答案：解：因為(4，5)=1，所以方程有解，由觀察得有特解x=0，y=2所以方程的解為xmyW't-z(11)8x=9(mod11) (10分)答案解：因為(8,11)=1,所以同余式有解由形式分?jǐn)?shù)有9 9x 3(mod11)88T1P(12)證明梅森數(shù)Mp=2-1的素因子q?P.(10分)答案證：設(shè)q是2p-1的質(zhì)因數(shù)，由于2p-1為奇數(shù)，二2,…(2,q)=1,由條件q|2p-1,即2p三1(modq)又…(q,2)=1,2p三1(modq)設(shè)i是使得2x=1(modp)成立最小正整數(shù)若1<i<p，則有i|p則與p為素數(shù)矛盾…i=p,…p|q-1，從而證明了結(jié)論。p9A_P(13) 試證若P式2,5且是素數(shù)，則P，(9分)答案證：因為p=2,5且是素數(shù)所以(p，10)=1，由歐拉定理有p10Tmodp)，從而有p9A9p-1(14)證明：對任何的正整數(shù)a,5a+2不可能是平方數(shù)(9分)答案證：因為平方數(shù)被5除后的余數(shù)為1,4，而5a+2被5除后的余數(shù)為2,2不同余1,4關(guān)于5,所以不相等判斷方程X2=3(mod83)是否有解，若有解則有幾解( 8分)答案(—)=1解：因為83，所以有解，由性質(zhì)知有解就有兩解.求4X2-xy-3=0的整數(shù)解.(10分)答案y=4x——解：因為x"，所以x,因為y為整數(shù)，所以x只能取-1,-3,1,3乂=1 X3=3 x4從而原方程的解為y=1, 丫3=11 =_3』4=2.判斷同余方程x三73(mod137)是否有解，若有解，有幾解.(8分)答案( )=12解：因為137,所以同余方程x三73(mod137)有解由定理有解則有兩解。22.證明：不存在整數(shù)x,y使等式x+y=1995成立.(10分)答案證：假設(shè)有整數(shù)x,y存在，使x2+y2=1995成立。…X2，y2被4除余數(shù)為0或1.…X2+y2被4除余數(shù)為0，1或2.又v1995被4除余數(shù)為3.???得出矛盾，假設(shè)不成立.故沒有整數(shù)x，y存在，使x2+y2=1995成立..設(shè)721a673b，試求a，b的值.(10分)答案解72=8X9,且(8，9)=18|a673b，且9|a673b?8|73b=b=6且9|a+6+7+3+6即9|22+a,即a=5,所以a=5，b=6.用1,2,。。。8,9不重復(fù)地寫出被11整除最大的九位數(shù)(10分)答案因為被11整除的數(shù)的特征是奇數(shù)位數(shù)碼之和減去偶數(shù)位數(shù)碼之和為11的倍數(shù),要寫最大的九位數(shù),前面可用98765,然后對后面的數(shù)字進行調(diào)整，此時奇數(shù)位數(shù)碼和比偶數(shù)位數(shù)碼之和大7,只要后面最大4或小7即可,小賣7不行,只能大4,剛好4,3之和比1,2之和大4,為了最大,后4位為2413,所以所求數(shù)為987652413.解方程x22x2=0(mod125)(10分)答案解：由x22x2=0 (mod5)得1,2(mod5)對xFgod5)得x=1+5t代入x22x2=0 (mod25)有4t=_i(mod5)有i代入x=1+5t得x=625t1代入x22x2=0(mod125)有1(2代入有x=56+125t2x三56(mod125)同理另一解為x=67(m°d125)(22)設(shè)P為素數(shù)，試證對任整數(shù)a,都有P|(P—1)!aP+a°(10分)答案證：由威爾遜定理(p-1)!=-1(modp)由歐拉定理a%(modP)，兩式相乘即得(p_1)!aP三a(modp)P即有P|(P—D!a+a(23)證明不定方程x2-2xy2+5z+3=0無整數(shù)解答案證:若不定方程有解，則x=y2_；y4一5z-3但y4=0,1(mod5),二對y,zy4-5z-3=2,3(mod5)而一個平方數(shù)三0,1,4(mod5)???y4-5z-3不可能為完全平方，即?-y4-5z-3不是整數(shù)，所以原不定方程無解。

P(24)證明梅森數(shù)Mp=2-i的素因子q一定為2Pt+l型。(p>2為素數(shù))(10分)答案證：設(shè)q是2p-1的質(zhì)因數(shù)，由于2p-1為奇數(shù)，二2,???(2q)=1,由條件q|2p-1,即2p三1(modq)又???(q,2)=1,2p三1(modq)設(shè)i是使得2x=1(modp)成立最小正整數(shù)若1<i<p,則有i|p則與p為素數(shù)矛盾???i=p,???p|q-1又???q-1為偶數(shù)，2q-1,…2p|q-1,q-1=2pk,即q=2pk+1(25)證明形如4m+1的素數(shù)有無窮多個(10分)答案證：假設(shè)形如4m+1的素數(shù)只有有限個，設(shè)為P1…pk,2,顯然(2p1…pk)+1的最小素因數(shù)p是奇數(shù)，且p與p門?pk不同，設(shè)p為4m+3形的素數(shù)，但p整除(2p1…pk)+1,表明(2p1…pk)+1=0(modp)即x2=(-1)(modp)有解，即〃，但矛盾,三(“)2三(1即x2=(-1)(modp)有解，即〃，但矛盾,?p為4m+1形，這與4m+1的素數(shù)只有k個矛盾2(26) 如果整系數(shù)的二次三項式P(x)=xbxc當(dāng)x=0，1時的值都是奇數(shù)，證明p(x)=0沒有整數(shù)根(6分)答案證：由條件可得c為奇數(shù)，b為偶數(shù)如果p(x)=0有根q,若q為偶數(shù)，則有qbqc為奇數(shù)，而p(q)=02為偶數(shù)，不可能，若q為奇數(shù)，則有q bqc為奇數(shù)，而p(q)=0為偶數(shù)，也不可能，所以P(x)=0沒有整數(shù)根(27)設(shè)P為奇素數(shù)，則有(8分)1p4-2+(p-1)p4二-Mmodp)1p2p (p—1)p三0(modp)答案證：由歐拉定理1p‘2pp-1)P， 1T1三p-1三1(modp)由費爾馬定理1p， 2p」 (p-1)心=1 2r-1=0(modp)(28)證明：對任何正整數(shù)k,m,nTOC\o"1-5"\h\z5k2 ,5m45n3 八有11|5 +4 +3 (6分)答案證：(5,11)=1,(4,11)=1,(3,11)=1由歐拉定理得510三1(mod11),310三1(mod11),4io三1(mod11),進步有5 5 55三1(mod11),3三1(mod11),4三1(mod11)對任何正整數(shù)k,m,n有5k25m45n3 2 4 3_5 4 3 =5 4 3=0(mod11)即有11|55k2 5n3(29) 證明：3是無理數(shù)。(8分)答案證：假設(shè)?3是有理數(shù)，則存在自數(shù)數(shù)a,b使得滿足x2=3y2即a2=3b2,容易22知道a是3的倍數(shù)，設(shè)@=3為，代入得b二3a1，又得到b為3的倍數(shù)，a1;：：b;：：a,22設(shè)b=3d，則a1=3d，這里b2s這樣可以進一步求得a2,b2…且有a>b>a1>b1>a2>b2>…但是自然數(shù)無窮遞降是不可能的，于是產(chǎn)生了矛盾，??? 3為無理數(shù)2(30)試證：對任何的正整數(shù)n,n2不能被4整除。(6分)答案證：n=2k時有n2 2=4k2 2,不能被4整除當(dāng)n=2k+1時有n2 2=4k24k3,不能被4整除所以有對任何的正整數(shù)n,n2不2能被4整除(31)解不定方程4x5y-10(6分)答案解：因為(4,5)=1，所以不定方程有解，由觀察得有特解fx=0-5t所以不定方程的解為』=2+4t為整數(shù)x=0,y=5(32)明：設(shè)d是自然數(shù)n的正因子，貝U有1d(n)_ld二n2dn (10分)答案n證：設(shè)d是n的因子，貝Ud也是n的因子，而n的因子數(shù)為d(n)nd=口丁 Gd)=n 口d=n2所以dln d|nd,所以dln 即有dn(33)P為奇素數(shù)，則有(10分)apbp=(ab)p(modp)答案證：由費爾馬小定理知對一切整數(shù)有ap三a(p)bp-b(P)，由同余性質(zhì)知有ap+bp=a+b(p)又由費爾馬小定理有(a+b)p=a+b(p)(a+b)p三ap+bp(p)2(34)、用初等方法解不定方程x-2值JT996二°答案(10分)2解：由題意知x為偶數(shù)，設(shè)x=1,則有x1_i0x1y.499=0即有

2x%(%-10丫)二-499由499為素數(shù)有兩因子只能取-八499,從而得x=2x=-2x=998x=-998-<<y=50j=-50.y=50、、目=-50、解不定方程式、解不定方程式15x+25y=-100.分）（8答案解：因為（15,25）|-100所以方程有解原方程的一組特解為x=°,y=一