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

1、.初等數(shù)論練習(xí)題一一、填空題1、(2420)=27；(2420)=_880_2、設(shè)a，n是大于1的整數(shù)，若an-1是質(zhì)數(shù)，則a=_2.3、模9的絕對(duì)最小完全剩余系是_-4，-3，-2，-1，0，1，2，3，4.4、同余方程9x+120(mod 37)的解是x11(mod 37)。5、不定方程18x-23y=100的通解是x=900+23t，y=700+18t tZ。.6、分母是正整數(shù)m的既約真分?jǐn)?shù)的個(gè)數(shù)為_(kāi)j(m)_。7、18100被172除的余數(shù)是_256。8、 =-1。9、若p是素?cái)?shù)，則同余方程xp- 11(mod p)的解數(shù)為p-1。二、計(jì)算題1、解同余方程：3x2+11x-200 (m

2、od 105)。解：因105 = 357，同余方程3x2+11x-200 (mod 3)的解為x1 (mod 3)，同余方程3x2+11x-38 0 (mod 5)的解為x0，3 (mod 5)，同余方程3x2+11x-200 (mod 7)的解為x2，6 (mod 7)，故原同余方程有4解。作同余方程組：xb1 (mod 3)，xb2 (mod 5)，xb3 (mod 7)，其中b1 = 1，b2 = 0，3，b3 = 2，6，由孫子定理得原同余方程的解為x 13，55，58，100 (mod 105)。2、判斷同余方程x242(mod 107)是否有解？ 故同余方程x242(mod 107

3、)有解。3、求（127156+34）28除以111的最小非負(fù)余數(shù)。解：易知127150（mod 111）。由50258（mod 111），503585014（mod 111），50914380（mod 111）知5028（509）3508035080350685070（mod 111）從而505616（mod 111）。故（127156+34）28（16+34）28502870（mod 111）三、證明題1、已知p是質(zhì)數(shù)，（a，p）=1，證明：（1）當(dāng)a為奇數(shù)時(shí)，ap-1+(p-1)a0 (mod p)；（2）當(dāng)a為偶數(shù)時(shí)，ap-1-(p-1)a0 (mod p)。證明：由歐拉定理知ap-11

4、 (mod p)及(p-1)a-1 (mod p)立得（1）和（2）成立。2、設(shè)a為正奇數(shù)，n為正整數(shù)，試證1(mod 2n+2)。 （1）證明 設(shè)a = 2m+1，當(dāng)n = 1時(shí)，有a2 = (2m+1)2 = 4m(m+1)+11 (mod 23)，即原式成立。設(shè)原式對(duì)于n = k成立，則有1 (mod 2k+2) = 1+q2k+2，其中qZ，所以= (1+q2k+2)2 = 1+q2k+31 (mod 2k+3)，其中q是某個(gè)整數(shù)。這說(shuō)明式(1)當(dāng)n = k+1也成立。由歸納法知原式對(duì)所有正整數(shù)n成立。3、設(shè)p是一個(gè)素?cái)?shù)，且1kp-1。證明： （-1 ）k(mod p)。 證明：設(shè)A=

5、 得：k!A =（p-1）(p-2)（p-k）（-1）(-2)（-k）(mod p)又（k!，p）=1，故A= （-1 ）k(mod p)4、設(shè)p是不等于3和7的奇質(zhì)數(shù)，證明：p61(mod 84)。說(shuō)明：因?yàn)?4=437，所以，只需證明： p61(mod 4) p61(mod3) p61(mod 7) 同時(shí)成立即可。證明：因?yàn)?4=437及p是不等于3和7的奇質(zhì)數(shù)，所以（p，4）=1，（p，3）=1，（p，7）=1。由歐拉定理知：pj(4)p21(mod 4)，從而 p61(mod 4)。同理可證：p61(mod3) p61(mod 7)。故有p61(mod 84)。注：設(shè)p是不等于3和7的

6、奇質(zhì)數(shù)，證明：p61(mod 168)。（見(jiàn)趙繼源p86）初等數(shù)論練習(xí)題二一、填空題1、(1000)=_16_；（除數(shù)函數(shù)：因數(shù)的個(gè)數(shù)）(1000)=_2340_.（和函數(shù)：所有因數(shù)的和）2、2010!的規(guī)范分解式中，質(zhì)數(shù)11的次數(shù)是199_.3、費(fèi)爾馬(Fermat)數(shù)是指Fn=+1，這種數(shù)中最小的合數(shù)Fn中的n=5。4、同余方程13x5(mod 31)的解是x29(mod 31)_5、分母不大于m的既約真分?jǐn)?shù)的個(gè)數(shù)為j(2)+j(3)+j(m)。6、設(shè)7(80n-1)，則最小的正整數(shù)n=_6_.7、使41x+15y=C無(wú)非負(fù)整數(shù)解的最大正整數(shù)C=_559_.8、=_1_.9、若p是質(zhì)數(shù)，n

7、p-1，則同余方程xn 1 (mod p) 的解數(shù)為n .二、計(jì)算題1、試求被19除所得的余數(shù)。解：由20027 (mod 19)2002211(mod 19)200231 (mod 19)又由2003200422004（22）10021 (mod 3)可得：20023n+1(20023)n20027(mod 19)2、解同余方程3x14+4x10+ 6x-18 0 (mod 5)。解：由Fermat定理，x5x (mod 5)，因此，原同余方程等價(jià)于2x2+x- 30 (mod 5)將x 0，1，2 (mod 5)分別代入上式進(jìn)行驗(yàn)證，可知這個(gè)同余方程解是x 1 (mod 5)。3、已知a=

8、5，m=21，求使ax 1 (mod m)成立的最小自然數(shù)x。 解：因?yàn)椋?，21）=1，所以有歐拉定理知5j(21)1(mod 21)。 又由于j(21)=12，所以x|12，而12的所有正因數(shù)為1，2，3，4，6，12。于是x應(yīng)為其中使5x 1 (mod12)成立的最小數(shù)，經(jīng)計(jì)算知：x=6。三、證明題1、試證13|(54m+46n+2000)。(提示：可取模13進(jìn)行計(jì)算性證明) 證明：54m+46n+2000252m+642n+2000（-1）2m+（-1）2n+200020020(mod 13)。2、證明Wilson定理的逆定理：若n1，并且(n- 1)! -1(mod n)，則n是素?cái)?shù)

9、。證明：假設(shè)n是合數(shù)，即n = n1n2，1 n1 n，由題設(shè)易知(n- 1)! -1(mod n1)，得0 -1(mod n1)，矛盾。故n是素?cái)?shù)。3、證明：設(shè)ps表示全部由1組成的s位十進(jìn)制數(shù)，若ps是素?cái)?shù)，則s也是一個(gè)素?cái)?shù)。 證明：假設(shè)s是合數(shù)，即s=ab，1a，b1，且(n-1)!+10(mod n)，則n為素?cái)?shù)。6、3103被11除所得余數(shù)是_5_。7、=_-1_。三、計(jì)算題1、判定() 2x3-x2+ 3x-1 0 (mod 5)是否有三個(gè)解；() x6+2x5- 4x2+ 3 0 (mod 5)是否有六個(gè)解？解：() 2x3-x2+ 3x-1 0 (mod 5)等價(jià)于x3-3x2

10、+ 4x-3 0 (mod 5)，又x5-x = (x3-3x2+ 4x-3)(x2+ 3x+5) + (6x2-12x+ 15)，其中r(x) = 6x2-12x+ 15的系數(shù)不都是5的倍數(shù)，故原方程沒(méi)有三個(gè)解。 () 因?yàn)檫@是對(duì)模5的同余方程，故原方程不可能有六個(gè)解。2、設(shè)n是正整數(shù)，求的最大公約數(shù)。 解：設(shè)知d22n-1，設(shè)2k|n且2k+1n，即2k +1|n ，則由2k +1|，i = 3， 5，L， 2n - 1得d = 2k + 1。3、已知a=18，m=77，求使ax 1 (mod m)成立的最小自然數(shù)x。 解：因?yàn)椋?8，77）=1，所以有歐拉定理知18j(77)1(mod

11、77)。 又由于j(77)=60，所以x|60，而60的所有正因數(shù)為1，2，3，4，5，6，10，12，15，20，30， 60。于是x應(yīng)為其中使18x 1 (mod77)成立的最小數(shù)，經(jīng)計(jì)算知：x=30。四、證明題1、若質(zhì)數(shù)p5，且2p+1是質(zhì)數(shù)，證明：4p+1必是合數(shù)。 證明：因?yàn)橘|(zhì)數(shù)p5，所以（3，p）=1，可設(shè)p=3k+1或p=3k+2。 當(dāng)p=3k+1時(shí)，2p+1=6k+3是合數(shù)，與題設(shè)矛盾，從而p=3k+2，此時(shí)2p+1是形如6k+5的質(zhì)數(shù)，而4p+1=12k+9=3(4k+3)是合數(shù)。注：也可設(shè)p=6k+r，r=0，1，2，3，4，5。再分類討論。2、設(shè)p、q是兩個(gè)大于3的質(zhì)數(shù)，

12、證明：p2q2(mod 24)。 證明：因?yàn)?4=38，（3，8）=1，所以只需證明：p2q2(mod 3) p2q2(mod 8)同時(shí)成立。事實(shí)上， 由于（p，3）=1，（q，3）=1，所以p21(mod 3) ， q21(mod 3)， 于是p2q2(mod 3)，由于p，q都是奇數(shù)，所以p21(mod 8) ， q21(mod 8)，于是p2q2(mod 8)。故p2q2(mod 24)。3、若x，yR+ ，（1）證明：xyxy；（2）試討論xy與xy的大小關(guān)系。注：我們知道，x+yx+y，x+yx+y。此題把加法換成乘法又如何呢？ 證明：（1）設(shè)x=x+，01，y=y+，01。于是xy

13、=xy+x+y+所以xy=xy+x+y+xy。（2）xy與xy之間等于、大于、小于三種關(guān)系都有可能出現(xiàn)。當(dāng)x=y=時(shí)，xy=xy=；當(dāng)x=，y=時(shí)，xy=，xy=，此時(shí)xyxy； 當(dāng)x=-，y=-時(shí)，xy=，xy=，此時(shí)xyxy。4、證明：存在一個(gè)有理數(shù)，其中d 100，能使=對(duì)于k=1，2，.，99均成立。證明：由（73，100）=1以及裴蜀恒等式可知：存在整數(shù)c，d，使得 73d-100c=1從而-=，由k 0是偶數(shù)，a1， a2，L，am與b1，b2，L，bm都是模m的完全剩余系，證明：a1+b1，a2+b2，L，am+bm不是模m的完全剩余系。證明：因?yàn)?， 2，L，m與a1， a2，

14、L，am都是模m的完全剩余系，所以(mod m)。 (1)同理(mod m)。 (2)如果a1+b1，a2+b2，L，am+bm是模m的完全剩余系，那么也有(mod m)。聯(lián)合上式與式(1)和式(2)，得到0(mod m)，這是不可能的，所以a1+b1，a2+b2，L，am+bm不能是模m的完全剩余系。4、證明：（1）2730x13-x；（2）24x(x+2)(25x2-1)；（3）504x9-x3；（4）設(shè)質(zhì)數(shù)p3，證明：6pxp-x。證明：（1）因?yàn)?730=235713，2，3，5，7，13兩兩互質(zhì)，所以：由x13-x=x(x12-1)0 (mod 2)知：2x13-x；13x13-x；

15、由x13-x=x(x12-1)=x(x2-1)(x2+1)(x8+x4+1)0 (mod 3)知：3x13-x；由x13-x=x(x12-1)=x(x4-1)(x8+x4+1)0 (mod 5)知：5x13-x；由x13-x=x(x12-1)=x(x6-1)(x6+1)0 (mod 7)知：7x13-x。故有2730x13-x。同理可證（2）、（3）、（4）。初等數(shù)論練習(xí)題五一、單項(xiàng)選擇題1、設(shè)x、y分別通過(guò)模m、n的完全剩余系，若（C）通過(guò)模mn的完全剩余系。A.m、n都是質(zhì)數(shù)，則my +nxB.mn，則my +nxC.（m，n）=1，則my +nx D.（m，n）=1，則mx+ny2、13

16、520032005200720092011規(guī)范分解式中11的冪指數(shù)是( A )。A.100 B.101 C.99 D.1023、n為正整數(shù)，若2n-1為質(zhì)數(shù)，則n是(A )。A.質(zhì)數(shù) B.合數(shù) C.3 D.2k(k為正整數(shù))4、從100到500的自然數(shù)中，能被11整除的數(shù)的個(gè)數(shù)是(B )。A.33 B.34 C.35 D.365、模100的最小非負(fù)簡(jiǎn)化剩余系中元素的個(gè)數(shù)是(C )。A.100 B.10 C.40 D.4二、填空題1、同余方程ax+b0(modm)有解的充分必要條件是(a，m)b。2、高斯稱反轉(zhuǎn)定律是數(shù)論的酵母，反轉(zhuǎn)定律是指設(shè)p與q是不相同的兩個(gè)奇質(zhì)數(shù)，3、20122012被3除

17、所得的余數(shù)為_(kāi)1_。4、設(shè)n是大于2的整數(shù)，則(-1)(n)=_1_。5、單位圓上的有理點(diǎn)的坐標(biāo)是，其中a與b是不全為零的整數(shù)。6、若3258a恰好是一個(gè)正整數(shù)的平方，則a的最小值為362。7、已知2011是一素?cái)?shù)，則=_-1_。三、計(jì)算題1、求3200872009132010的個(gè)位數(shù)字。解：320087200913201032008（-3）200932010-32008+2009+2010-36027 -3（32）30133(mod 10)。2、求滿足j(mn)=j(m)+j(n)的互質(zhì)的正整數(shù)m和n的值。 解：由（m，n）=1知，j(mn)=j(m)j(n)。于是有：j(m)+j(n)=j

18、(m)j(n) 設(shè)j(m)=a，j(n)=b，即有：a+b=ab。 顯然ab，且ba，因此a=b。 于是由2a=a2得a=2，即j(m)=j(n)=2。故 m=3，n=4或m=4，n=3。3、甲物每斤5元，乙物每斤3元，丙物每三斤1元，現(xiàn)在用100元買(mǎi)這三樣?xùn)|西共100斤，問(wèn)各買(mǎi)幾斤?解：設(shè)買(mǎi)甲物x斤，乙物y斤，丙物z斤，則5x+ 3y+z = 100，x+y+z = 100。消去z，得到7x+ 4y = 100。 (1)顯然x = 0，y = 25是方程(1)的解，因此，方程(1)的一般解是 ， tZ因?yàn)閤0，y0，所以0t 3。即t可以取值t1 = 1，t2 = 2，t3 = 3。相應(yīng)的x

19、，y，z的值是(x，y，z) = (4， 18， 78)，(8， 11， 81)，(12， 4， 84)。四、證明題1、已知2011是質(zhì)數(shù)，則有2011|。 證明：=102011-10 (mod 2011)。2、設(shè)p是4n+1型的質(zhì)數(shù)，證明若a是p的平方剩余，則p-a也是p的平方剩余。 證明：因?yàn)橘|(zhì)數(shù)p=4n+1，a是p的平方剩余，所以=1 即：p-a也是p的平方剩余。3、已知p，q是兩個(gè)不同的質(zhì)數(shù)，且ap-11 (mod q)，aq-11 (mod p)，證明：apqa (mod pq)。證明：由p，q是兩個(gè)不同的質(zhì)數(shù)知（p，q）=1。于是由Fermat定理 apa (mod p)，又由題設(shè)

20、aq-11 (mod p)得到：apq(aq)pap (aq-1)papa (mod p)。同理可證：apqa (mod q)。故：apqa (mod pq)。4、證明：若m，n都是正整數(shù)，則j(mn)=（m，n）j(m，n)。 證明：易知mn與m，n有完全相同的質(zhì)因數(shù)，設(shè)它們?yōu)閜i(1ik)，則又mn=（m，n）m，n故。 類似的題：設(shè)m=m1m2，m1與m由相同的質(zhì)因數(shù)，證明：j(m)=m2j(m1)。初等數(shù)論練習(xí)題六一、填空題1、為了驗(yàn)明2011是質(zhì)數(shù)，只需逐個(gè)驗(yàn)算質(zhì)數(shù)2，3，5，p都不能整除2011，此時(shí)，質(zhì)數(shù)p至少是_43_。2、最大公因數(shù)(4n+3，5n+2)的可能值是_1，7_。

21、3、設(shè)340!，而3+140!，即340!，則=_18_。4、形如3n+1的自然數(shù)中，構(gòu)成模8的一個(gè)完全系的最小那些數(shù)是1，4，7，10，13，16，19，22。5、不定方程x2+y2=z2，2|x， (x，y)=1， x，y，z0的整數(shù)解是且僅是x = 2ab，y = a2-b2，z = a2+b2，其中ab0，(a，b) = 1，a與b有不同的奇偶性。6、21x9 (mod 43)的解是x25 (mod 43)。7、 =-1。二、計(jì)算題1、將寫(xiě)成三個(gè)既約分?jǐn)?shù)之和，它們的分母分別是3，5和7。解：設(shè)，即35x+ 21y+ 15z = 17，因(35， 21) = 7，(7， 15) = 1，

22、117，故有解。分別解5x+ 3y = t7t+ 15z = 17得x = -t+ 3u，y = 2t- 5u，uZ，t = 11 + 15v，z = -4 - 7v，vZ， 消去t得x = -11 - 15v+ 3u，y = 22 + 30v- 5u，z = -4 - 7v，u，vZ。令u =0，v =-1得到：x =4，y =-8，z=3。即：2、若3是質(zhì)數(shù)p的平方剩余，問(wèn)p是什么形式的質(zhì)數(shù)？解：由二次互反律，注意到p3，p只能為p1(mod 3)且只能下列情況或。3、判斷不定方程x2+23y=17是否有解？解：只要判斷x217(mod 23)是否有解即可。 171(mod 4)x217(

23、mod 23)無(wú)解，即原方程無(wú)解。三、論證題1、試證對(duì)任何實(shí)數(shù)x，恒有x+x+=2x證明：設(shè)x=x+，01當(dāng)0時(shí)， x+=x， 2x=2x等式成立當(dāng) 0，v 0，41 - 3v- 2u 0。2、有一隊(duì)士兵，若三人一組，則余1人；若五人一組，則缺2人；若十一人一組，則余3人。已知這隊(duì)士兵不超過(guò)170人，問(wèn)這隊(duì)士兵有幾人？ 解：設(shè)士兵有x人，由題意得x 1 (mod 3)，x-2 (mod 5)，x 3 (mod 11)。在孫子定理中，取m1 = 3，m2 = 5，m3 = 11，m = 3511 = 165，M1 = 55，M2 = 33，M3 = 15，M1 =1，M2 = 2，M3 = 3，

24、則x1551+（-2）332+ 3153 58 (mod 165)，因此所求的整數(shù)x = 52 + 165t，tZ。由于這隊(duì)士兵不超過(guò)170人，所以這隊(duì)士兵有58人。3、判斷同余方程是否有解?解：286=2143，433是質(zhì)數(shù)，(143，443)=1奇數(shù)143不是質(zhì)數(shù)，但可用判定雅可比符號(hào)計(jì)算的勒讓德符號(hào)原方程有解。四、證明題 1、設(shè)(a，m) = 1，d0是使ad1 (mod m)成立的最小正整數(shù)，則() d0j(m)；()對(duì)于任意的i，j，0 i，j d0- 1，ij，有aiaj (mod m)。 （1）證明：() 由Euler定理，d0j(m)，因此，由帶余數(shù)除法，有j(m) = qd0

25、+r，qZ，q0，0 r d0。因此，由上式及d0的定義，利用歐拉定理得到1 (mod m)，即整數(shù)r滿足ar 1(mod m)，0 r j。因?yàn)?a，m) = 1，所以ai-j 0 (mod m)，0 i-j 1，(b，m) = 1，并且ba 1(mod m)，bc 1(mod m) （1）記d = (a，c)，則bd 1 (mod m)。證明：由裴蜀恒等式知，存在整數(shù)x，y，使得ax+cy = d，顯然xy0，y0，由式(1)知：1bax = bdb-cy = bd(bc)-ybd (mod m)。若x0，由式(1)知：1bcy = bdb-ax = bd(ba)-xbd (mod m)。

26、3、設(shè)p是素?cái)?shù)，pbn-1，nN，則下面的兩個(gè)結(jié)論中至少有一個(gè)成立：() pbd-1對(duì)于n的某個(gè)因數(shù)d2，則()中的mod n可以改為mod 2n。證明：記d = (n，p- 1)，由bn 1，bp- 1 1(mod p)，及第2題有bd1 (mod p)。若d 2，則p 1 (mod 2)。由此及結(jié)論()，并利用同余的基本性質(zhì)，得到p 1 (mod 2n)。初等數(shù)論練習(xí)題八一、單項(xiàng)選擇題 1、設(shè)n1，則n為素?cái)?shù)是(n- 1)! -1(mod n)的（ C）。 A.必要但非充分條件 B.充分但非必要條件C.充要條件 D.既非充分又非必要條件2、小于545的正整數(shù)中，15的倍數(shù)的個(gè)數(shù)是（ C）A

27、.34 B.35 C.36 D.373、500!的規(guī)范分解式中7的冪指數(shù)是（ D ）A.79 B.80 C.81 D.824、以下各組數(shù)中，成為模10的簡(jiǎn)化剩余系的是（ D ）A.1，9，3，1 B.1，1，7，9C.5，7，11，13 D.1，1，3，35、設(shè)n是正整數(shù)，下列選項(xiàng)為既約分?jǐn)?shù)的是（ A ）A.B.C.D.二、填空題1、（120）=360。2、7355的個(gè)位數(shù)字是3。3、同余方程3x5(mod14)的解是x11(mod14)。4、（）=-1。5、-2。6、如果一個(gè)正整數(shù)具有6個(gè)正因數(shù)，問(wèn)這個(gè)正整數(shù)最小是12。7、同余方程x3+x2-x-10(mod 5)的解是x1(mod5)。三

28、、計(jì)算題 1、已知563是素?cái)?shù)，判定方程x2 429 (mod 563)是否有解。解：把看成Jacobi符號(hào)，我們有-），故方程x2 429 (mod 563)有解。2、求出模23的所有的二次剩余和二次非剩余。 解：模23的所有的二次剩余為x1，2，3，4，6，8，9，12，13，16，18 (mod 23)；模23的所有的二次非剩余為x5，7，10，11，14，15，17，19，20，21，22 (mod 23)。3、試求出所有正整數(shù)n ，使得1n2n3n4n 能被5整除。 解：若n為奇數(shù)，則1n2n3n4n1n2n（-2）n（-1）n0 (mod 5)； 若n=2m，mZ，則1n2n3n4n12m22m（-2）2m（-1）2m2+222m=2+24m=2+2(-1)m(mod 5)； 當(dāng)m為奇數(shù)時(shí)，1n2n3n4n0(mod 5)； 當(dāng)m為偶數(shù)時(shí)，1n2n3n4n4(mod 5)。 故當(dāng)4n時(shí)，51n2n3n4n。四、證明題 1、證明：若質(zhì)數(shù)p2，則2P-1的質(zhì)因數(shù)一定是2pk+1形。證明：設(shè)q是2-1的質(zhì)因數(shù)，由于2-1為奇數(shù)，q2，（2，q）=1。由條件q|2p-1，即21（mod