初等數(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 tÎZ。.6、分母是正整數(shù)m的既約真分?jǐn)?shù)的個(gè)數(shù)為_j(m)_。7、18100被172除的余數(shù)是_256 。8、 = -1 。9、若p是素?cái)?shù)，則同余方程x p - 1 º1(mod p)的解數(shù)為 p-1 。二、計(jì)算題1、

2、解同余方程：3x2+11x-20 º 0 (mod 105)。解：因105 = 3×5×7，同余方程3x2+11x-20 º 0 (mod 3)的解為x º 1 (mod 3)，同余方程3x2+11x-38 º 0 (mod 5)的解為x º 0，3 (mod 5)，同余方程3x2+11x-20 º 0 (mod 7)的解為x º 2，6 (mod 7)，故原同余方程有4解。作同余方程組：x º b1 (mod 3)，x º b2 (mod 5)，x º b3 (mod 7)

3、，其中b1 = 1，b2 = 0，3，b3 = 2，6，由孫子定理得原同余方程的解為x º 13，55，58，100 (mod 105)。2、判斷同余方程x242(mod 107)是否有解？ 故同余方程x242(mod 107)有解。3、求（127156+34）28除以111的最小非負(fù)余數(shù)。 解：易知127150（mod 111）。由502 58（mod 111）， 503 58×5014（mod 111），50914380（mod 111）知5028 （509）3×50803×50803×5068×5070（mod 111）從而50

4、56 16（mod 111）。故（127156+34）28（16+34）28 502870（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 (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) + 1 º 1 (mod 23)，即原

5、式成立。設(shè)原式對(duì)于n = k成立，則有 º 1 (mod 2k + 2) Þ= 1 + q2k + 2，其中qÎZ，所以 = (1 + q2k + 2)2 = 1 + q ¢2k + 3 º 1 (mod 2k + 3)，其中q ¢是某個(gè)整數(shù)。這說明式(1)當(dāng)n = k + 1也成立。由歸納法知原式對(duì)所有正整數(shù)n成立。3、設(shè)p是一個(gè)素?cái)?shù)，且1kp-1。證明： º （-1 ）k(mod p)。 證明：設(shè)A= 得： k!·A =（p-1）(p-2)（p-k）（-1）(-2)（-k）(mod p) 又（k!，p）=1，故

6、A = º （-1 ）k(mod p)4、設(shè)p是不等于3和7的奇質(zhì)數(shù)，證明：p61(mod 84)。 說明：因?yàn)?4=4×3×7，所以，只需證明： p61(mod 4) p61(mod3) p61(mod 7) 同時(shí)成立即可。 證明：因?yàn)?4=4×3×7及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的奇質(zhì)數(shù)，證明：p61(mod 1

7、68)。（見趙繼源p86）初等數(shù)論練習(xí)題二一、填空題1、(1000)=_16_；（除數(shù)函數(shù)：因數(shù)的個(gè)數(shù)）(1000)=_2340_.（和函數(shù)：所有因數(shù)的和）2、2010!的標(biāo)準(zhǔn)分解式中，質(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無非負(fù)整數(shù)解的最大正整數(shù)C=_559_.8、=_1_.9、若p是質(zhì)數(shù)，n½p - 1，則同

8、余方程x n º 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)n×20027(mod 19)2、解同余方程3x14 + 4x10 + 6x - 18 º 0 (mod 5)。 解：由Fermat定理，x5 º x (mod 5)，因此，原同余方程等價(jià)于2x2 + x - 3 º 0 (mod 5)將x º 0

9、，±1，±2 (mod 5)分別代入上式進(jìn)行驗(yàn)證，可知這個(gè)同余方程解是x º 1 (mod 5)。3、已知a=5，m=21，求使a x º 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)為其中使 5 x º 1 (mod 12)成立的最小數(shù)，經(jīng)計(jì)算知：x=6。三、證明題1、試證13|(54m+46n+2000)。(提示：可取模13進(jìn)行計(jì)算性證明) 證明：54m+46n+2000

10、86; 252m+642n+2000 º（-1）2m+（-1）2n+2000 º 2002º 0(mod 13)。2、證明Wilson定理的逆定理：若n > 1，并且(n - 1)! º -1 (mod n)，則n是素?cái)?shù)。證明：假設(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，1<a，b

11、<s。則 ，其中M1是正整數(shù)。由pa1也是正整數(shù)知ps是合數(shù)，這與題設(shè)矛盾。故s也是一個(gè)素?cái)?shù)。4、證明：若2p + 1是奇素?cái)?shù)，則 (p!)2 + (-1)p º 0 (mod 2p + 1)。證明：由威爾遜定理知 -1 º (2p)! = p!(p + 1)L(2p) º (-1)p(p!)2(mod 2p + 1)，由此得(p!)2 + (-1)p º 0 (mod 2p + 1)。5、設(shè)p是大于5的質(zhì)數(shù)，證明：p41(mod 240)。（提示：可由歐拉定理證明） 證明：因?yàn)?40=23×3×5，所以只需證：p41(mod

12、8)，p41(mod 3)，p41(mod 5)即可。事實(shí)上，由j(8)=4，j(3)=2，j(5)=4以及歐拉定理立得結(jié)論。初等數(shù)論練習(xí)題三一、單項(xiàng)選擇題1、若n1，j(n)=n-1是n為質(zhì)數(shù)的（ C ）條件。 A.必要但非充分條件 B.充分但非必要條件 C.充要條件 D.既非充分又非必要條件2、設(shè)n是正整數(shù)，以下各組a，b使為既約分?jǐn)?shù)的一組數(shù)是（D）。A.a=n+1，b=2n-1 B.a=2n-1，b=5n+2 C.a=n+1，b=3n+1 D.a=3n+1，b=5n+23、使方程6x+5y=C無非負(fù)整數(shù)解的最大整數(shù)C是（A）。A.19B.24 C.25D.304、不是同余方程28x21(

13、mod 35)的解為（D）。 A.x2(mod 35) B. x7(mod 35) C. x17(mod 35)D. x29(mod 35)5、設(shè)a是整數(shù)，(1)a0(mod9) (2)a2010(mod9)(3)a的十進(jìn)位表示的各位數(shù)字之和可被9整除(4)劃去a的十進(jìn)位表示中所有的數(shù)字9，所得的新數(shù)被9整除以上各條件中，成為9|a的充要條件的共有（C）。A.1個(gè)B.2個(gè) C.3個(gè) D.4個(gè)二、填空題1、(2010)=_4896_；(2010)=528。2、數(shù)的標(biāo)準(zhǔn)分解式中，質(zhì)因數(shù)7的指數(shù)是_3。3、每個(gè)數(shù)都有一個(gè)最小質(zhì)因數(shù)。所有不大于10000的合數(shù)的最小質(zhì)因數(shù)中，最大者是97。4、同余方程

14、24x6(mod34)的解是x113(mod34) x230(mod34)_。5、整數(shù)n>1，且(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 + 4x - 3 º 0 (mod 5)，又x5 - x = (x3 - 3x2 + 4

15、x - 3)(x2 + 3x + 5) + (6x2 - 12x + 15)，其中r(x) = 6x2 - 12x + 15的系數(shù)不都是5的倍數(shù)，故原方程沒有三個(gè)解。 () 因?yàn)檫@是對(duì)模5的同余方程，故原方程不可能有六個(gè)解。2、設(shè)n是正整數(shù)，求 的最大公約數(shù)。 解：設(shè)知d½22n-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 77)。 又由于j

16、(77)=60，所以x|60，而60的所有正因數(shù)為1，2，3，4，5，6，10，12，15，20，30， 60。于是x應(yīng)為其中使18x º 1 (mod 77)成立的最小數(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ù)，

17、證明：p2q2(mod 24)。 證明：因?yàn)?4=3×8，（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 + y x+ y，x+yx+y。此題把加法換成乘法又如何呢？ 證明：（1）設(shè)x=x+，0<

18、;1，y=y+，0<1。于是xy=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< 100可知：0-設(shè)=n，則n+1=，于是=n+1，故 = n =。初等數(shù)論練習(xí)題四一、單項(xiàng)選擇題 1、若Fn=是合

19、數(shù)，則最小的n是( D )。A. 2 B. 3 C. 4 D. 52、記號(hào)baa表示baa，但ba+1a. 以下各式中錯(cuò)誤的一個(gè)是( B )。A. 21820! B. 10550! C. 119100! D. 1316200!3、對(duì)于任意整數(shù)n，最大公因數(shù)(2n+1，6n-1)的所有可能值是( A )。A. 1 B. 4 C. 1或2 D. 1，2或44、設(shè)a是整數(shù)，下面同余式有可能成立的是( C )。A. a22 (mod 4) B. a25 (mod 7) C. a25 (mod 11) D. a26 (mod 13)5、如果ab(mod m)，c是任意整數(shù)，則下列錯(cuò)誤的是（A）Aacbc

20、(mod mc)Bm|a-b C(a，m)=(b，m) Da=b+mt，tZ二、填空題 1、d(10010)=_32_，(10010)=_2880_。2、對(duì)于任意一個(gè)自然數(shù)n，為使自N起的n個(gè)相繼自然數(shù)都是合數(shù)，可取N=（n+1）！3、為使3n-1與5n+7的最大公因數(shù)達(dá)到最大可能值，整數(shù)n應(yīng)滿足條件n=26k+9，kZ。4、在5的倍數(shù)中，選擇盡可能小的正整數(shù)來構(gòu)成模12的一個(gè)簡化系，則這組數(shù)是5，25，35，555、同余方程26x+133 (mod 74)的解是x124(mod74) x261(mod74)_。6、不定方程5x+9y=86的正整數(shù)解是_x=1，y=9或x=10，y=4。7、=

21、_-1_。三、計(jì)算題1、設(shè)n的十進(jìn)制表示是，若792½n，求x，y，z。 解：因?yàn)?92 = 8×9×11，故792½n Û 8½n，9½n及11½n。我們有8½n Û 8½ Þ z = 6，以及9½n Û 9½1 + 3 + x + y + 4 + 5 + z = 19 + x + y Û 9½x + y + 1， (1)11½n Û 11½z - 5 + 4 - y + x - 3 + 1 =

22、 3 - y + x Û 11½3 - y + x。 (2)由于0 £ x， y £ 9，所以由式(1)與式(2)分別得出x + y + 1 = 9或18，3 - y + x = 0或11。這樣得到四個(gè)方程組：其中a取值9或18，b取值0或11。在0 £ x， y £ 9的條件下解這四個(gè)方程組，得到：x = 8，y = 0，z = 6。2、求3406的末二位數(shù)。解： （3，100）=1，3(100)1（mod 100），而(100)= (22·52)=40， 3401(mod 100) 3406=(340)10·3

23、6(32)2·32-19×9-17129(mod 100) 末二位數(shù)為29。3、求(214928+40)35被73除所得余數(shù)。 解：(214928+40)35(3228+40)35(32×32)14+4035 (102414+40)35 (214+40)35 (210×24+40)35 (25+40)35 7235 -172(mod 73)四、證明題1、設(shè)a1， a2， L， am是模m的完全剩余系，證明： （1）當(dāng)m為奇數(shù)時(shí)，a1+ a2+ L+ am 0（mod m）；（2）當(dāng)m為偶數(shù)時(shí)，a1+ a2+ L+ am （mod m）。 證明：因?yàn)?，

24、2， L， m與a1， a2， L， am都是模m的完全剩余系，所以 (mod m)。（1）當(dāng)m為奇數(shù)時(shí)，即得：，故(mod m)。（2）當(dāng)m為偶數(shù)時(shí)，由（m，m+1）=1即得：(mod m)。2、證明：若m2，a1， a2， L， aj(m)是模m的任一簡化剩余系，則 證明：若a1， a2， L， aj(m)是模m的一個(gè)簡化剩余系，則m-a1， m-a2， L， m-aj(m) 也是模m的一個(gè)簡化剩余系，于是： 從而： 又由于m2，j(m)是偶數(shù)。故：3、設(shè)m > 0是偶數(shù)，a1， a2， L， am與b1， b2， L， bm都是模m的完全剩余系，證明：a1 + b1， a2 + b

25、2， L， am + bm不是模m的完全剩余系。 證明：因?yàn)?， 2， L， m與a1， a2， 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）

26、因?yàn)?730=2×3×5×7×13，2，3，5，7，13兩兩互質(zhì)，所以：由x13-x=x (x12-1)0 (mod 2)知：2x13-x；13x13-x；由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、

27、設(shè)x、y分別通過模m、n的完全剩余系，若（ C ）通過模mn的完全剩余系。A. m、n都是質(zhì)數(shù)，則my + nx B. mn，則my + nx C. （m，n）=1，則my + nx D. （m，n）=1，則mx + ny2、1×3×5××2003×2005×2007×2009×2011標(biāo)準(zhǔn)分解式中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ù)

28、的個(gè)數(shù)是( B )。A.33 B.34 C.35 D.365、模100的最小非負(fù)簡化剩余系中元素的個(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除所得的余數(shù)為_1_。4、設(shè)n是大于2的整數(shù)，則(-1)(n)=_1_。5、單位圓上的有理點(diǎn)的坐標(biāo)是，其中a與b是不全為零的整數(shù)。6、若3258×a恰好是一個(gè)正整數(shù)的平方，則a的最小值為362。7、已知2011是一素?cái)?shù)，則=_-1_。三、計(jì)算題 1、求32

29、008×72009×132010的個(gè)位數(shù)字。 解：32008×72009×#215;（-3）2009×32010 -32008+2009+2010 -36027 -3×（32）3013 3(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(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

30、。 故 m=3，n=4或m=4，n=3。3、甲物每斤5元，乙物每斤3元，丙物每三斤1元，現(xiàn)在用100元買這三樣?xùn)|西共100斤，問各買幾斤? 解：設(shè)買甲物x斤，乙物y斤，丙物z斤，則5x + 3y +z = 100，x + y + z = 100。消去z，得到 7x + 4y = 100。 (1)顯然x = 0，y = 25是方程(1)的解，因此，方程(1)的一般解是 ， tÎZ因?yàn)閤0，y0，所以 0t £ 3。即t可以取值t1 = 1，t2 = 2，t3 = 3。相應(yīng)的x，y，z的值是(x， y， z) = (4， 18， 78)，(8， 11， 81)，(12， 4，

31、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è)aq-11 (mod p)得到：apq(aq)pap (aq-1)papa (mod p)

32、。同理可證：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_。3、設(shè)340!，而3+140!，即340!，則=_18_。4、形如3n+1的自然數(shù)中

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

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

35、) 是否有解即可。 171(mod 4) x217(mod 23)無解，即原方程無解。三、論證題1、試證對(duì)任何實(shí)數(shù)x，恒有x+x+=2x證明：設(shè)x=x+，0<1當(dāng)0< 時(shí)， x +=x， 2x=2x 等式成立當(dāng)< 1時(shí)， x +=x+1， 2x=2x+1 等式成立故對(duì)任何實(shí)數(shù)x，恒有x+x+=2x。2、證明：（1）當(dāng)n為奇數(shù)時(shí)，3（2n+1）； （2）當(dāng)n為偶數(shù)時(shí)，3（2n+1）。 證明：由2n+1（-1）n+1（mod 3）立得結(jié)論。3、證明：（1）當(dāng)3n（n為正整數(shù)）時(shí)，7（2n-1）； （2）無論n為任何正整數(shù)，7（2n+1）。 證明：（1）設(shè)n=3m，則2n-1=8m

36、 -10（mod 7），即：7（2n-1）； （2）由于23m 1（mod 7）得 23m +12（mod 7），23m+1 +13（mod 7），23m+2 +15（mod 7）。 故無論n為任何正整數(shù)，7（2n+1）。4、設(shè)m0，n0，且m為奇數(shù)，證明：（2m-1，2n+1）=1。 證明一：由m為奇數(shù)可知：2n+12mn+1，又有2m-12mn-1，于是存在整數(shù)x，y使得：（2n+1）x=2mn+1， (2m-1)y=2mn-1。從而（2n+1）x-(2m-1)y=2。這表明：（2m-1，2n+1）2由于2n+1，2m-1均為奇數(shù)可知：（2m-1，2n+1）=1。證明二：設(shè)（2m-1，2n

37、+1）=d，則存在s，tZ，使得2m=sd+1， 2n =td-1。由此得到： 2mn=(sd+1) n， 2mn =(td-1) m 于是 2mn =pd + 1=qd 1，p，qZ。所以：（q -p）d =2。 從而 d2，就有d =1或2。由因?yàn)閙為奇數(shù)，所以d =1。即（2m-1，2n+1）=1。 注：我們已證過：記Mn = 2n - 1，對(duì)于正整數(shù)a，b，有(Ma， Mb) = M(a， b) 。顯然當(dāng)ab，a，b為質(zhì)數(shù)時(shí)，(Ma， Mb) =1。初等數(shù)論練習(xí)題七一、單項(xiàng)選擇題 1、設(shè)a和b是正整數(shù)，則=（A）A1 Ba CbD(a，b)2、176至545的正整數(shù)中，13的倍數(shù)的個(gè)數(shù)

38、是（B）A27 B28 C29D303、200!中末尾相繼的0的個(gè)數(shù)是（A）A49 B50 C51D524、從以下滿足規(guī)定要求的整數(shù)中，能選取出模20的簡化剩余系的是（ B）A2的倍數(shù) B3的倍數(shù) C4的倍數(shù)D5的倍數(shù)5、設(shè)n是正整數(shù)，下列選項(xiàng)為既約分?jǐn)?shù)的是（A）A B CD二、填空題 1、314162被163除的余數(shù)是_1_。（歐拉定理）2、同余方程3x5(mod13)的解是x6(mod13)。3、=1。4、-4。5、為使n-1與3n的最大公因數(shù)達(dá)到最大的可能值，則整數(shù)n應(yīng)滿足條件n=3k+1，kZ。6、如果一個(gè)正整數(shù)具有21個(gè)正因數(shù)，問這個(gè)正整數(shù)最小是26×32=576。7、同余

39、方程x3+x2-x-10(mod 3)的解是x1，2(mod 3)。三、計(jì)算題1、求不定方程x + 2y + 3z = 41的所有正整數(shù)解。解：分別解x + 2y = tt + 3z = 41得 x = t - 2uy = u uÎZ，t = 41 - 3vz = v vÎZ，消去t得 x = 41 - 3v - 2uy = uz = v u，vÎZ。由此得原方程的全部正整數(shù)解為(x， y， z) = (41 - 3v - 2u， u， v)，u > 0，v > 0，41 - 3v - 2u > 0。2、有一隊(duì)士兵，若三人一組，則余1人；若五人一

40、組，則缺2人；若十一人一組，則余3人。已知這隊(duì)士兵不超過170人，問這隊(duì)士兵有幾人？ 解：設(shè)士兵有x人，由題意得x º 1 (mod 3)，x º -2 (mod 5)，x º 3 (mod 11)。在孫子定理中，取 m1 = 3， m2 = 5， m3 = 11，m = 3×5×11 = 165，M1 = 55，M2 = 33，M3 = 15，M1¢ = 1，M2¢ = 2，M3¢ = 3，則 x º 1×55×1 + （-2）×33×2 + 3×15&

41、#215;3 º 58 (mod 165)，因此所求的整數(shù)x = 52 + 165t，tÎZ。由于這隊(duì)士兵不超過170人，所以這隊(duì)士兵有58人。3、判斷同余方程是否有解?解：286=2×143，433是質(zhì)數(shù)，(143，443)=1奇數(shù)143不是質(zhì)數(shù)，但可用判定雅可比符號(hào)計(jì)算的勒讓德符號(hào) 原方程有解。四、證明題 1、設(shè)(a， m) = 1，d0是使a d º 1 (mod m)成立的最小正整數(shù)，則() d0½j(m)；()對(duì)于任意的i，j，0 £ i， j £ d0 - 1，i ¹ j，有a ia j (mod m)

42、。 （1）證明：() 由Euler定理，d0 £ j(m)，因此，由帶余數(shù)除法，有j(m) = qd0 + r，qÎZ，q > 0，0 £ r < d0。因此，由上式及d0的定義，利用歐拉定理得到1 º(mod m)，即整數(shù)r滿足 a r º 1 (mod m)，0 £ r < d0 。由d0的定義可知必是r = 0，即d0½j(m)。() 若式(1)不成立，則存在i，j，0 £ i， j £ d0 - 1，i ¹ j，使a i º a j (mod m)。不妨設(shè)i

43、> j。因?yàn)?a， m) = 1，所以 ai - j º 0 (mod m)，0 < i - j < d0。這與d0的定義矛盾，所以式(1)必成立。2、證明：設(shè)a，b，c，m是正整數(shù)，m > 1，(b， m) = 1，并且b a º 1 (mod m)，b c º 1 (mod m) （1）記d = (a， c)，則bd º 1 (mod m)。 證明：由裴蜀恒等式知，存在整數(shù)x，y，使得ax + cy = d，顯然xy < 0。若x > 0，y < 0，由式(1)知：1 º b ax = b db -

44、cy = b d(b c) -y º b d (mod m)。若x < 0，y > 0，由式(1)知：1 º b cy = b db -ax = b d(ba) -x º b d (mod m)。3、設(shè)p是素?cái)?shù)，p½bn - 1，nÎN，則下面的兩個(gè)結(jié)論中至少有一個(gè)成立：() p½bd - 1對(duì)于n的某個(gè)因數(shù)d < n成立；() p º 1 ( mod n )。若2n，p > 2，則()中的mod n可以改為mod 2n。證明：記d = (n， p - 1)，由b n º 1，b p - 1

45、 º 1 (mod p)，及第2題有b d º 1 (mod p)。若d < n，則結(jié)論()得證。若d = n，則n½p - 1，即p º 1 (mod n)，這就是結(jié)論()。若2n，p > 2，則p º1 (mod 2)。由此及結(jié)論()，并利用同余的基本性質(zhì)，得到p º 1 (mod 2n)。初等數(shù)論練習(xí)題八一、單項(xiàng)選擇題 1、設(shè)n > 1，則n為素?cái)?shù)是(n - 1)! º -1 (mod n)的（ C ）。 A.必要但非充分條件 B.充分但非必要條件 C.充要條件 D.既非充分又非必要條件2、小于545

46、的正整數(shù)中，15的倍數(shù)的個(gè)數(shù)是（ C ）A.34 B.35 C.36 D.373、500!的標(biāo)準(zhǔn)分解式中7的冪指數(shù)是（ D ）A.79 B.80 C.81 D.824、以下各組數(shù)中，成為模10的簡化剩余系的是（ D ）A.1，9，3，1 B.1，1，7，9 C.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ù)，問這個(gè)正整數(shù)最小是12。7、同余方程x

47、3+x2-x-10(mod 5)的解是x±1(mod5)。三、計(jì)算題 1、已知563是素?cái)?shù)，判定方程x2 º 429 (mod 563)是否有解。解：把看成Jacobi符號(hào)，我們有-），故方程x2 º 429 (mod 563)有解。2、求出模23的所有的二次剩余和二次非剩余。 解：模23的所有的二次剩余為xº1，2，3，4，6，8，9，12，13，16，18 (mod 23)；模23的所有的二次非剩余為xº5，7，10，11，14，15，17，19，20，21，22 (mod 23)。3、試求出所有正整數(shù)n ，使得1n2n3n4n 能被5整除

48、。 解：若n為奇數(shù)，則1n2n3n4nº1n2n（-2）n（-1）n º 0 (mod 5)； 若n=2m，mZ，則1n2n3n4nº12m22m（-2）2m（-1）2m º2+2×22m =2+2×4m =2+2×(-1)m(mod 5)； 當(dāng)m為奇數(shù)時(shí)，1n2n3n4nº0(mod 5)； 當(dāng)m為偶數(shù)時(shí)，1n2n3n4nº4(mod 5)。 故當(dāng)4n時(shí)，51n2n3n4n 。四、證明題 1、證明：若質(zhì)數(shù)p>2，則2P-1的質(zhì)因數(shù)一定是2pk+1形。證明：設(shè)q是2-1的質(zhì)因數(shù)，由于2-1為奇數(shù)，

49、q2，（2，q）=1。由條件q|2p-1，即21（mod q）。設(shè)h是使得21（mod q）成立最小正整數(shù)，若1<h<p，則有h|p。這與p為質(zhì)數(shù)矛盾。從而 h=p， 于是 p|q-1。又 q-1為偶數(shù)，2|q-1， 2p|q-1，q-1=2pk， 即q=2pk+1 kZ。2、設(shè)（m，n）=1，證明：mj(n)+n j(m) 1 (mod mn)。 證明：因?yàn)椋╩，n）=1，所以由歐拉定理知： n j(m) 1 (mod m)，mj(n) 1 (mod n) 于是 mj(n)+n j(m) 1 (mod m)， mj(n)+n j(m) 1 (mod n)。 又因?yàn)椋╩，n）=1，

50、所以 mj(n)+n j(m) 1 (mod mn)。 注：此題也可這樣表述：若兩個(gè)正整數(shù)a，b互質(zhì)，則存在正整數(shù)m，n，使得am+bn1(mod ab)。3、設(shè)（a，b）=1，a+b0，p為一個(gè)奇質(zhì)數(shù)，證明：。 說明：事實(shí)上，設(shè)，只需證明：d | p 即可。證明：由a+b0(mod a+b)，即a-b (mod a+b)，知ak(-b)k (mod a+b)。其中0kp-1。又。令，則d | pbp-1 。 又（a，b）=1，d |（a+b）知（d，b）=1。（否則設(shè)（d，b）=d1，立即得到da和db，這與（a，b）=1矛盾。）于是（d ，bp-1）=1。故d | p，即 d =1或p。初

51、等數(shù)論練習(xí)題九一、單項(xiàng)選擇題1、以下Legendre符號(hào)等于-1的30被-1是( D )A. B. C. D. 2、100至500的正整數(shù)中，能被17整除的個(gè)數(shù)是( B )A. 23B. 24C. 25D. 263、設(shè) |500!，但500！，則=( C )A. 245B.246C.247D. 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，4，4，5，5，05、設(shè)n是正整數(shù)，則以下各式中一定成立的是( B )A. (n+1，3n1)=1B.（2n

52、1，2n1）=1C.（2n，n1）=1D.（2n1，n1）=1二、填空題1、25736被50除的余數(shù)是 1 2、同余方程3x5(mod16) 的解是x7(mod16) 3、不定方程9x12y=15的通解是x = -1 + 4t，y = -2 +3t，tÎZ。4、 = 1。5、實(shí)數(shù)的小數(shù)部分記為x ，則 0.75。6、為使3n與4n1 的最大公因數(shù)達(dá)到最大可能值，整數(shù)n應(yīng)滿足條件n=3k+2，kZ。7、如果一個(gè)正整數(shù)具有35個(gè)正因數(shù)，問這個(gè)正整數(shù)最小是26×34=5184。三、計(jì)算題 1、解不定方程9x24y5z=1000。 解：解 因（9，24）=3，（3，-5）=1知原方

53、程有解。原方程化為9x + 24y = 3t， 即 3x + 8y = t， (1)3t -5z = 1000 3t -5z = 1000， (2)解(2)得 ， uÎZ，再解3x + 8y =5u得到 ， u，vÎZ。故 ， u， vÎZ。2、設(shè)A = x1， x2， L， xm是模m的一個(gè)完全系，以x表示x的小數(shù)部分，若(a， m) = 1，求。解：當(dāng)x通過模m的完全剩余系時(shí)，ax + b也通過模m的完全剩余系，因此對(duì)于任意的i（1 £ i £ m），axi + b一定與且只與某個(gè)整數(shù)j（1 £ j £ m）同余，即存在

54、整數(shù)k，使得axi + b = km + j，（0 £ j £ m-1）。從而：3、設(shè)整數(shù)n ³ 2，求：。即在數(shù)列1， 2， L， n中，與n互素的整數(shù)之和。解：設(shè)在1， 2， L， n中與n互素的j(n)個(gè)數(shù)是a1， a2， L， aj(n)，(ai， n) = 1，1 £ ai £ n - 1，1 £ i £ j(n)，則 (n - ai， n) = 1，1 £ n - ai £ n - 1，1 £ i £ j(n)，因此，集合a1， a2， L， aj(n)與集合n - a1， n - a2， L， n - aj(n)是相同的，于是a1 + a2 + L + aj(n) = (n - a1) + (n - a2) + L + (n - aj(n)，2(a1 + a2 + L + aj(n) = nj(n)， 因此：a