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

1、初等數(shù)論練習(xí)題、填空題1、d(2420)=12;(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+12m0(mod 37)的解是x三11(mod 37)。5、不定方程 18x-23y=100 的通解是 x=900+23t, y=700+18t t Z。6、分母是正整數(shù)m的既約真分?jǐn)?shù)的個(gè)數(shù)為 (n)07、18100被172除的余數(shù)是256。8、65103=-1 09、若p是素?cái)?shù)，則同余方程xp 1 1(mod p)的解數(shù)為p-1。、計(jì)算題1、解同余方程：3x2 11

2、x 200 (mod 105)。解：因 105 = 3 57, 同余方程3x2 11x 20同余方程3x2 11x 38同余方程3x2 11x 200 (mod 3)的解為x0 (mod 5)的解為x0 (mod 7)的解為x1 (mod 3),0 , 3 (mod 5),2 , 6 (mod 7),故原同余方程有4解作同余方程組：xb1 (mod 3) , xb2 (mod 5) , xba (mod 7),其中 b1 = 1 , b2 = 0 , 3, b3 = 2,6,由孫子定理得原同余方程的解為x13 , 55, 58, 100 (mod 105)。2、判斷同余方程x2m42(mod

3、107)是否有解?解：(烏)107()107, 42 、(一)107故同余方程/ 2 3 7、 / 2、 / 3、()(一)(一)107107107-3 1 107 1/3 、/、v?-/ 107、1,()(1) 22 ()1073(2)3_7 1 107 1 _/ 7 、/、?-107、/ 2、1,()(1) 22 ()(-)110777x2=42(mod 107)W 解。3、求( 127156+34) 28除以111的最小非負(fù)余數(shù)解：易知 1271 m50 (mod 111)。由 502 三58 (mod 111) , 50 3 m58X50m 14 (mod 111), 509三 143

4、三80 (mod 111)知 5028 三(509) 3X50m803X50m803X 50m68X 50m70 (mod 111)從而 5056 m 16 (mod 111)。故(127156+34) 28三( 16+34) 28 三5028三70 (mod 111)三、證明題1、已知p是質(zhì)數(shù)，(a,p) =1,證明：(1)當(dāng) a 為奇數(shù)時(shí)，ap-1+(p-1) a=0 (mod p)；(2)當(dāng) a 為偶數(shù)時(shí)，ap-1-(p-1) a=0 (mod p)。證明：由歐拉定理知ap-1 = 1 (mod p)及(p-1) am-1 (mod p)立得(1)和(2)成立。2 n2、設(shè)a為正奇數(shù)，n

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

6、1)(p 2) (p k)得： pk!k! - A = (p-1) (p-2)(p-k)三(-1) (-2)(-k) (mod p)又(k! , p) =1,故 A = Cp 1(-1 ) k(mod p)4、設(shè)p是不等于3和7的奇質(zhì)數(shù)，證明：p6m1(mod 84)。說(shuō)明：因?yàn)?4=4X3X7,所以，只需證明：p6= 1(mod 4)p6= 1(mod3)p6= 1(mod 7)同時(shí)成立即可。證明：因?yàn)?4=4X3X7及p是不等于3和7的奇質(zhì)數(shù)，所以(p, 4) =1 , (p, 3) =1, (p, 7) =1。由歐拉定理知：p (4) = p2=1(mod 4),從而p6三1(mod 4

7、)。同理可證：p6m 1(mod3)p6= 1(mod 7)。 故有 p6三 1(mod 84)。注：設(shè)p是不等于3和7的奇質(zhì)數(shù)，證明：p6三1(mod 168)。(見(jiàn)趙繼源p86)初等數(shù)論練習(xí)題二一、填空題1、d(1000)=16; (T (1000)=2340.2、2010!的標(biāo)準(zhǔn)分解式中，質(zhì)數(shù)11的次數(shù)是199 .3、費(fèi)爾馬(Fermat)數(shù)是指Fn=2*+1,這種數(shù)中最小的合數(shù)Fn中的n=5。4、同余方程13xm5(mod 31)的解I是xm29(mod 31)5、分母不大于 m的既約真分?jǐn)?shù)的個(gè)數(shù)為 (2)+(3)+ + (m)。6、設(shè)7 I (80n-1),則最小的正整數(shù)n=6.7、

8、使41x+15y=C無(wú)非負(fù)整數(shù)解的最大正整數(shù) C=_559_.8、也=1 .1019、若p是質(zhì)數(shù)，n p 1 ,則同余方程x n 1 (mod p)的解數(shù)為n二、計(jì)算題1、試求200220032004被19除所得的余數(shù)。解：由 2002三 7 (mod 19) 2002 2 m 11(mod 19) 2002 3m 1 (mod 19)又由 20032004三 22004三(22) 1002m 1 (mod 3)可得：200220032004 三20023n+1 三(20023)nX2002m7(mod 19)2、解同余方程 3x14 4x10 6x 180 (mod 5)。0 (mod1 (

9、mod解：由Fermat定理，x5 x (mod 5),因此，原同余方程等價(jià)于 2x2x 35)將x 0, 1, 2 (mod 5)分別代入上式進(jìn)行驗(yàn)證，可知這個(gè)同余方程解是x5) o3、已知a=5, m=21，求使a x 1 (mod m)成立的最小自然數(shù)x。解：因?yàn)?5,21) =1,所以有歐拉定理知5(21)三1(mod 21)。又由于(21)=12 ,所以x|12,而12的所有正因數(shù)為1,2,3,4,6,12。于是x應(yīng)為其中使 5x 1 (mod 12)成立的最小數(shù)，經(jīng)計(jì)算知：x=6。三、證明題1、試證13|(54m+46n+2000)。(提示：可取模13進(jìn)行計(jì)算性證明)證明：54m+

10、46n+2000 2 52m+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)，行01 (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<s。則Ps 11 1山8J M,其中g(shù)1是正整數(shù)。 s 999由

11、Pa> 1也是正整數(shù)知Ps是合數(shù)，這與題設(shè)矛盾。故s也是一個(gè)素?cái)?shù)。4、證明：若 2P 1 是奇素?cái)?shù)，則(p!) 2( 1)P 0 (mod 2 P 1)。證明：由威爾遜定理知1(2 p)! = p!(P 1)(2 p) ( 1)p(p!)2(mod2P 1),由此得(P!)2(1)p 0 (mod 2 p 1)。5、設(shè)p是大于5的質(zhì)數(shù)，證明：p4m1(mod 240)。(提示：可由歐拉定理證明)證明：因?yàn)?240=23X3X 5,所以只需證：p4= 1(mod 8), p4=1(mod 3), p4=1(mod 5)即可。事實(shí)上，由(8)=4 , (3)=2 , (5)=4以及歐拉定理立

12、得結(jié)論。初等數(shù)論練習(xí)題三一、單項(xiàng)選擇題1、若n>1,(n)=n-1是n為質(zhì)數(shù)的( C )條件。A.必要但非充分條件 B.充分但非必要條件 C.充要條件D.既非充分又非必要條件2、設(shè)n是正整數(shù)，以下各組a, b使b為既約分?jǐn)?shù)的一組數(shù)是( D )。 aA.a=n+1,b=2n-1 B.a=2n-1,b=5n+2C.a=n+1,b=3n+1D.a=3n+1,b=5n+23、使方程6x+5y=C無(wú)非負(fù)整數(shù)解的最大整數(shù) C是(A )。A.19B.24C.25D.30A.x三2(mod 35)B. x 三7(mod 35) C. x 三 17(mod 35) D. x 三29(mod 35)5、設(shè)

13、a 是整數(shù)，(1)am0(mod9)(2)a三2010(mod9)(3)a的十進(jìn)位表示的各位數(shù)字之和可被 9整除(4)劃去a的十進(jìn)位表示中所有的數(shù)字9,所得的新數(shù)被9整除以上各條件中，成為91a的充要條件的共有( C )。A.1個(gè) B.2個(gè) C.3個(gè) D.4個(gè)二、填空題1、(T (2010)=4896;(2010)=528o2、數(shù)C2J0的標(biāo)準(zhǔn)分解式中，質(zhì)因數(shù)7的指數(shù)是_33、每個(gè)數(shù)都有一個(gè)最小質(zhì)因數(shù)。所有不大于 10000的合數(shù)的最小質(zhì)因數(shù)中，最大者是 974、同余方程 24x三6(mod34)的解是 xi 三 13(mod34) x2三30(mod34)5、整數(shù) n>1,且(n-1)

14、!+1 =0(mod n),則 n 為素?cái)?shù)。6、7、3103被11除所得余數(shù)是 5.60 _ .=-1 O97三、計(jì)算題1、判定(i ) 2 x3 x2 3x 10 (mod 5)是否有三個(gè)解;(ii) x6 2x5 4 x230 (mod 5)是否有六個(gè)解?解：(i ) 2 x3 x2 3x 1又x50 (mod 5)等價(jià)于 x3 3 x2 4x 30 (mod 5), x = ( x3 3x2 4x 3)( x2 3x 5) + (6 x2 12x 15),其中 r(x) = 6x212x15的系數(shù)不都是5的倍數(shù)，故原方程沒(méi)有三個(gè)解。(ii)因?yàn)檫@是對(duì)模5的同余方程，故原方程不可能有六個(gè)解

15、2、設(shè)n是正整數(shù)，求C2n,C2n, ,C2n 1的最大公約數(shù)。解：設(shè)(C2nCn,噫 1) d,由 C2n C3n 噫122n 1 知 d*,設(shè) 2k|n 且 2k+1|n,即 2k +1| n ,則由 2k +1| C12n 及 2 k 1 | C i2n午C i2n1 1 , i = 3, 5, 2 n 1 得 d = 2103、已知a=18,m=77，求使ax 1 (mod m)成立的最小自然數(shù) x。解：因?yàn)?18,77) =1,所以有歐拉定理知18(77)三1(mod 77)又由于(77)=60 ,所以 x|60,而 60 的所有正因數(shù)為 1,2,3,4,5,6,10,12,15,2

16、0,30, 60 于是x應(yīng)為其中使18x 1 (mod 77)成立的最小數(shù)，經(jīng)計(jì)算知：x=30o四、證明題1、若質(zhì)數(shù)p>5,且2p+1是質(zhì)數(shù)，證明：4p+1必是合數(shù)。證明：因?yàn)橘|(zhì)數(shù)p> 5,所以(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ù)，證明：p2=q2(mod 24)。證明：因?yàn)?4=3X8, (3,8) =1,所以只需

17、證明：p2=q2(mod 3)p2=q2(mod 8)同時(shí)成立。事實(shí)上， 由于(p, 3) =1, (q, 3) =1,所以 p2=1(mod 3) , q2m 1(mod 3), 于是p2三q2(mod 3),由于p, q都是奇數(shù)，所以p2m1(mod 8) , q2m1(mod 8), 于是 p2=q2(mod 8)。故 p2 = q2(mod 24)。3、若 x,y C K ,(1)證明：xy > xy;(2)試討論xy與xy的大小關(guān)系。注：我們知道，x y刁x+ y, x+y &x+y。此題把加法換成乘法又如何呢？ 證明：(1)設(shè) x=x+ a ,0 < a <

18、;1, y=y+ B ,0 & B <1。于是xy=xy+B x+ a y+ a B1 .一二，止匕時(shí)xy >xy;411 ,止匕時(shí)xy <xy3k9=k 0d100所以xy=岡y+ B x+ a y+ a B > 岡y。(2) xy與xy之間等于、大于、小于三種關(guān)系都有可能出現(xiàn)。當(dāng) x=y=1 時(shí)，xy=xy=-;24當(dāng) x= ： , y= 1 時(shí)，xy= 3， xy=224當(dāng) x=- 1, y=-1 時(shí)，xy= 1 , xy= 2364、證明：存在一個(gè)有理數(shù)-c ,其中d < 100,能使對(duì)于k=1, 2, ., 99均成立。證明：由(73, 100)

19、 =1以及裴蜀恒等式可知：存在整數(shù) c, d,使得73d-100c=1從而受k-3=k(73d 100c)二上,由k< ©可知:100 d 100d100d0V100 d d®k =n,則卜<n+1=d,于是ddd100-1 d =n+1, d啕=n "kF。初等數(shù)論練習(xí)題四一、單項(xiàng)選擇題，一0n1、若Fn=22 1是合數(shù)，則最小的口是(D )。A. 2 B. 3 C. 4 D. 52、記號(hào)ba IIa表示ba |a,但ba+1|a.以下各式中錯(cuò)誤的一個(gè)是(B )。A. 2 18 | 20! B. 105 | 50! C. 119 | 100! D.

20、1316 11 200!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 ) oA. a 2= 2 (mod 4) B. a2=5 (mod 7) C. a2三 5 (mod 11) D. a2= 6 (mod 13)5、如果amb(mod m), c是任意整數(shù)，則下列錯(cuò)誤的是( A )A. ac= bc(mod mc) B. m|a-b C . (a,m)=(b,m) D . a=b+mt,t CZ二、填空題1、d(10010)= 32, 1 (10010)=

21、 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, kCZ。4、在5的倍數(shù)中，選擇盡可能小的正整數(shù)來(lái)構(gòu)成模12的一個(gè)簡(jiǎn)化系，則這組數(shù)是5,25,35,55 5、同余方程 26x+1 m 33 (mod 74)的解是 x尸24(mod74) x 2三 61(mod74)6、不定方程5x+9y=86的正整數(shù)解是_x=1,y=9或x=10,y=4。7、54 =1 -1 089 一三、計(jì)算題1、設(shè)n的十進(jìn)制表示是13xy45z ,若792 n,求x, y, z。解：

22、因?yàn)?792 - 8 9 11,故 792 n 8 n, 9 n及 11 n。我們有8 n 8 45Z9 13 x y 45 z - 19 x y11 n 11 z 54 y x 31 - 3 y x9 xy1 ,11 3yx。由于0 x, y 9 ,所以由式與式(2)分別得出x y 1 - 9 或 18,3 yx - 0 或 11。這樣得到四個(gè)方程組:其中a取值9或18, b取值0或11。在0 x, y 9的條件下解這四個(gè)方程組，得到：x - 8 , y - 0 , z - 6。2、求3406的末二位數(shù)。解：V (3, 100) -1,.3"100)三 1 (mod 100),而

23、小(100)-小(22 52)-40, .二 34°三 1(mod 100) .二 34°6-(340) 1° 36三(3 2)2 . 32m-19X 9m-171 三29(mod 100)末二位數(shù)為29。3、求(2149 28+40)35被73除所得余數(shù)。解：(214928+40)35 三(3228+40)35 三(32 X 32) 14+4035 三(102414+40)35 三(214+40)35 三(2 X 24+40)35 三(2 5+40)35 三 7235 三-1 三 72(mod 73)四、證明題1、設(shè)a1, a 2, am是模m的完全剩余系，證明

24、：(1)當(dāng) m為奇數(shù)時(shí)，a1+ a2+ + am = 0 (mod m；(2)當(dāng) m為偶數(shù)時(shí)，a1+ a2+ + am = m (mod m。2證明：因?yàn)?,2,mmai ii 1i 1(1)當(dāng)m為奇數(shù)時(shí),由亭Z即得：m，故i1am(m 1)- 0 (mod m)n與ai, a 2, , am)都是模m的完全剩余系，所以m(m 1) /-(mod m) o2m(m 1) m /(mod m)22m(2)當(dāng)m為偶數(shù)時(shí)，由(m,m+1 =1即得：aii 1(m)2、證明：若m>2, a1, a 2, a (m)是模m的任一簡(jiǎn)化剩余系，則 40(mod m).i 1證明：若a1, a 2,a

25、(m)是模m的一個(gè)簡(jiǎn)化剩余系，則 m-a, m-a2, m-a.也是模(m)(m)(m)m的一個(gè)簡(jiǎn)化剩余系，于是： ai (m )(mod m).從而：2 ai m (m)(mod m).i 1 i 1i 1又由于m>2, (m是偶數(shù)。故:(m)ai i 1m 0(mod m).23、設(shè)m> 0是偶數(shù), a1, a 2, an)與b1,b2, , bm)都是模m的完全剩余系，證明：a1b1, a2b2,am bm)不是模m的完全剩余系。證明：因?yàn)?,2,同理如果a1mai i 1mbi i 1b1, a2m(aii 1,n)與&, a 2,m i m(m 1)i 12m(m

26、od m 。2b2, am,am)都是模m的完全剩余系，所以m (mod m。 2b2是模m的完全剩余系，那么也有.、m /bi) (mod m)。聯(lián)合上式與式(1)和式(2),得到0這是不可能的，所以日2b1, a2b2,amm /一 (mod m),2bm不能是模m的完全剩余系。4、證明：(1) 2730 I x13-x ;(2) 24 I x(x+2)(25x 2-1);(3) 504 I x9-x3;(4)設(shè)質(zhì)數(shù) p>3,證明：6Pl xp-x。13 I x13-x ;證明：(1)因?yàn)?2730=2X 3X5X7X13, 2,3,5 , 7,13 兩兩互質(zhì)，所以:由 x13-x=

27、x (x 12-1)三 0 (mod 2)知：2 I x13-x ;由 x13-x=x (x 12-1)= x(x 2-1) (x2+1)(x 8+x4+1)三0 (mod 3)知：3 I x13-x ;由 x13-x=x (x 12-1)= x(x 4-1) (x8+x4+1)三0 (mod 5)知：5 I x13-x ;由 x13-x=x (x 12-1)= x(x 6-1) (x6+1)三0 (mod 7)知：7 I x13-x 0故有 2730 I x13-x。同理可證(2)、(3)、(4)。初等數(shù)論練習(xí)題五一、單項(xiàng)選擇題1、設(shè)x、y分別通過(guò)模m n的完全剩余系，若(C )通過(guò)模mn的

28、完全剩余系。A. m、 n者B是質(zhì)數(shù)，則 my nx B. mwn,則 my nxC. (m, n) =1,貝U my nx D. (m, n) =1,貝U mx ny2、1X3X5X - X 2003X 2005X 2007X2009X2011 標(biāo)準(zhǔn)分解式中 11 的幕指數(shù)是( A )。A.100B.101C.99D.1023、n為正整數(shù)，若2n-1為質(zhì)數(shù)，則口是(A )。A.質(zhì)數(shù) B.合數(shù) C.3D.2k(k為正整數(shù))4、從100到500的自然數(shù)中，能被11整除的數(shù)的個(gè)數(shù)是(B )。A.33 B.34C.35D.365、模100的最小非負(fù)簡(jiǎn)化剩余系中元素的個(gè)數(shù)是(C ) oA.100B.1

29、0C.40D.4二、填空題1、同余方程ax+bm0(modm)有解的充分必要條件是(a,m) I b。p1q12、高斯稱反轉(zhuǎn)定律是數(shù)論的酵母，反轉(zhuǎn)定律是指設(shè)p與q是不相同的兩個(gè)奇質(zhì)數(shù)，(q) (1)下至(p)pq3、20122012被3除所得的余數(shù)為_(kāi)1_04、設(shè)n是大于2的整數(shù)，則(-1) (n)=1_02 22 25、單位圓上的有理點(diǎn)的坐標(biāo)是(2ab a b)成(a b 2ab),其中a與b是不全為 2 2 , 2 22 2 ,2 2a b a b a b a b零的整數(shù)。6、若3258X a恰好是一個(gè)正整數(shù)的平方，則 a的最小值為36207、已知2011是一素?cái)?shù)，則二2_ = -1 02

30、011三、計(jì)算題1、求 32008 X 72009x 132010 的個(gè)位數(shù)字。解.3200872009132010= 32008x( 3 ) 2009 x32010 = 32008+2009+2010三-3 6027 三-3 X ( 32) 3013 m 3(mod 10)。2、求滿足(mn)=(m+ (n)的互質(zhì)的正整數(shù)m和n的值。解：由(m, n) =1 知，(mn)= (m) (n)。于是有：(m)+ (n)= (n) (n)設(shè)(m=a,(n)=b,即有：a+b=abo 顯然 alb,且 b I a,因止匕 a=b。于是由 2a=a2 得 a=2,即(m)= (n)=2。 故 m=3,

31、n=4 或 m=4,n=33、甲物每斤5元，乙物每斤3元，內(nèi)物每三斤1元，現(xiàn)在用100元買這三樣?xùn)|西共100斤，問(wèn)各買幾斤？解：設(shè)買甲物x斤，乙物y斤，內(nèi)物z斤，則5x 3y -z = 100 ,3(1)(1)的一股解是t Zx y z = 100 o消去z,得到 7 x 4y = 100。顯然x = 0 , y = 25是方程(1)的解，因止匕，方程x 4t，y 25 7t因?yàn)?x>0, y>0,所以 0<t 3。即t可以取值3 = 1 , t2 = 2, t3 = 3。相應(yīng)的x, y, z的值是(x, y, z) = (4, 18, 78), (8,11,81), (12

32、,4, 84)。四、證明題1、已知2011是質(zhì)數(shù)，則有2011| 99 9。2010 個(gè)證明：999=102011-1 m 0 (mod 2011)。2010 個(gè)2、設(shè)p是4n+1型的質(zhì)數(shù)，證明若a是p的平方剩余，則p-a也是p的平方剩余 證明：因?yàn)橘|(zhì)數(shù)p=4n+1, a是p的平方剩余，所以p 1a 1 a ,八 萬(wàn) a=(1) 2 - =1p p pp即：p-a也是p的平方剩余。3、已知p,q是兩個(gè)不同的質(zhì)數(shù)，且ap-1 = 1 (mod q), a q-1 = 1 (mod p),證明：apq= a (mod pq)。證明：由p,q是兩個(gè)不同的質(zhì)數(shù)知(p, q) =1。于是由Fermat定

33、理ap=a (mod p), 又由題設(shè) aq-1 = 1 (mod p)得到：apq=(a q)p=ap (a q-1) p= ap=a (mod p)。同理可證： apq=a (mod q)。 故：apq= a (mod pq)。4、證明：若 m,n都是正整數(shù)，則 (mn)= (m,n)( m,n)證明：易知mn與m,n有完全相同的質(zhì)因數(shù)，設(shè)它們?yōu)椤?11 、(mn) mn(1 一)(1 ) (1 )p1p2pk/、111(m,n)m,n(1)(1) (1)5 p2pk又 mn= (m,n) m,n故 (mn) (m,n)m,n(1力(111-)(1 -)p2pk(m,n) (m,n)。類似

34、的題：設(shè)m=m2, m與m由相同的質(zhì)因數(shù)，證明：(m)=m (m)初等數(shù)論練習(xí)題六一、填空題1、為了驗(yàn)明2011是質(zhì)數(shù)，只需逐個(gè)驗(yàn)算質(zhì)數(shù) 2, 3, 5,書都不能整除2011,此時(shí)，質(zhì) 數(shù)p至少是43。2、最大公因數(shù)(4n+3,5n+2)的可能值是1,7 。3、設(shè) 31 40!,而 3"1 | 40!,即 3" II 40!,則 a =18 。4、形如3n+1的自然數(shù)中，構(gòu)成模8的一個(gè)完全系的最小那些數(shù)是1,4,7,10,13,16,19,22 05、不定方程 x2+y2=z2,2|x, (x,y)=1, x,y,z>0的整數(shù)解是且僅是 x = 2 ab, y = a

35、2b： z = a2b2,其中a > b > 0, (a, b) = 1 , a與b有不同的奇偶性。6、21x9 (mod 43)的解是 x 三 25 (mod 43)。7、 = -1 o199二、計(jì)算題1、將 比寫成三個(gè)既約分?jǐn)?shù)之和，它們的分母分別是3, 5和7。10517 x y z解：設(shè) 105 3 5 7，即 35x21y15z = 17 ,因(35, 21) = 71 17,故有解。，(7, 15) = 1分別解5 x得消去t得3y = t 7 t 15z = 17x = t 3u,y = 2 t 5u,uZ, t = 1115v, z = 47 v, v Z,x =11

36、15 v 3 u,y = 2230 v 5u,z =47 v,u, v Zo令 u =o, v =-1 得至ij： x =4 , y =-8 , z=3。即:171052、若3是質(zhì)數(shù)p的平方剩余，問(wèn)p是什么形式的質(zhì)數(shù)?p 1解：:由二次互反律.3-( 1)h 坦，P3注意至U p>3, p只能為pL p1(mod 3)且1 p 1(mod4)1 p 1(mod4)1只能下列情況p 1(mod 3)p 1(mod 4)p1(mod 3)p1(mod 4)p 1(mod12)或 p 1(mod 12) 03、判斷不定方程x2+23y=17是否有解？解：只要判斷x2m17(mod 23)是否有

37、解即可 17 = 1(mod 4)17236233172317171717173x2三17(mod 23)無(wú)解,即原方程無(wú)解。三、論證題1、試證對(duì)任何實(shí)數(shù)x,包有x+x+1=2x2證明：設(shè) x=x+ a ,0 < a <1當(dāng)00 a < 1時(shí)，x +2當(dāng)工& a < 1時(shí)，x + 2f=x, 2x=2岡2-=x+1, 2x=2x+12故對(duì)任何實(shí)數(shù)x,恒有岡+x+ 1 =2x。22、證明：（1）當(dāng)n為奇數(shù)時(shí)，3 I （2n+1）;（ 2）當(dāng)n 為偶數(shù)時(shí)，3 | （ 2n+1） 。證明：由2n+1三（-1） n+1 （mod 3）立得結(jié)論。3、證明：（1）當(dāng)3 1n

38、 （n為正整數(shù)）時(shí)，7 I （2n-1）;（ 2）無(wú)論n 為任何正整數(shù)，7 | （ 2n+1） 。證明：（1）設(shè) n=3m 貝U 2n- 1=8m-1 三0 （mod 7）,即：7 I （2n-1）;（2）由于 23m m 1 （mod 7）得23m +1=2 （mod 7）, 23m+1+1 m3 （mod 7）, 23m+2+1 m5 （mod 7）。故無(wú)論 n 為任何正整數(shù)，7 | （ 2n+1） 。4、設(shè) m>0, n>0,且 m為奇數(shù)，證明：（2m-1 , 20+1） =1。證明一：由m為奇數(shù)可知：2n+1 | 2mn+1,又有2m-1 I 2m-1 ,于是存在整數(shù)x,y

39、 使得： （ 2n+1） x=2mn+1, （2 m-1）y=2 mn-1 。從而（2n+1） x-（2 m-1）y=2 。這表明：（221 , 2n+1） | 2由于2n+1， 2m-1 均為奇數(shù)可知：（ 2m-1 ， 2n+1） =1。證明二：設(shè)（2m-1 , 2n+1） =d,則存在 s,t C Z,使得 2m=sd+1,2 n =td-1 。由此得至h2mn=（sd+1） n , 2 mn =（td-1） m于是 2 mn =pd + 1 = qd - 1, p,q C Z。所以：（q -p） d =2。從而d I 2,就有d =1或2。由因?yàn)閙為奇數(shù)，所以d =1。即（2m-1 ，

40、2n+1） =1。注：我們已證過(guò)：記 M = 2n1 ,對(duì)于正整數(shù)a, b,有（M, M） = M（a, b）。顯然當(dāng)awb, a,b為質(zhì)數(shù)時(shí)，（M, M） =1。初等數(shù)論練習(xí)題七一、單項(xiàng)選擇題1、設(shè)a和b是正整數(shù)，則（a,旦,巴旦）二（A ） a bA. 1 B . a C . bD. （a,b）2、176至545的正整數(shù)中，13的倍數(shù)的個(gè)數(shù)是（B ）A. 27 B . 28 C . 29D. 303、200!中末尾相繼的0的個(gè)數(shù)是（ A ）A. 49 B . 50 C . 51D. 524、從以下滿足規(guī)定要求的整數(shù)中，能選取出模20的簡(jiǎn)化剩余系的是（B ）A. 2的倍數(shù) B . 3的倍數(shù)

41、C . 4的倍數(shù) D. 5的倍數(shù)5、設(shè)n是正整數(shù)，下列選項(xiàng)為既約分?jǐn)?shù)的是（A 21n 4 b n J c14n 3 2n 1、填空題Zn_J D.5n 2A ) n 1 3n 11、314162被163除的余數(shù)是。（歐拉定理）2、同余方程3x三5（mod13）的解是xm5（mod13）。3、（空）=1。18474、-九=-4。5、為使n-1與3n的最大公因數(shù)達(dá)到最大的可能值，則整數(shù)n應(yīng)滿足條件n=3k+1,k CZ。6、如果一個(gè)正整數(shù)具有21個(gè)正因數(shù)，問(wèn)這個(gè)正整數(shù)最小是 26 X 32=576。7、同余方程 x3+x2-x-1 =0(mod 3)的解是 x三 1,2(mod 3)。三、計(jì)算題1

42、、求不定方程x 2y 3z = 41的所有正整數(shù)解。 解：分別解x 2y = tt 3z = 41得x = t 2 uy = uu Z,t = 413 vz = vv Z,消去t得 x = 413 v 2 uy = uz = vu, v Zo由此得原方程的全部正整數(shù)解為(x, y, z) = (413v 2u, u, v),u > 0 , v > 0,41 3v2u > 0 o2、有一隊(duì)士兵，若三人一組，則余1人；若五人一組，則缺2人；若十一人一組，則余3 人。已知這隊(duì)士兵不超過(guò)170人，問(wèn)這隊(duì)士兵有幾人？解：設(shè)士兵有 x 人，由題意得 x 1 (mod 3) , x 2 (

43、mod 5) , x 3 (mod 11)。 在孫子定理中，取 m = 3, m2 = 5, m = 11, m= 3 511 = 165,M = 55 , M = 33 , M3 = 15 ,M = 1, M2 = 2 , M3 = 3 ,貝U x 1 55 1(-2) 33 23 15358 (mod 165),因此所求的整數(shù)x = 52 + 165 t, t Z。由于這隊(duì)士兵不超過(guò)170人，所以這隊(duì)士兵有58人。3、判斷同余方程x 2286(mod 443)是否有解？解：286=2 X 143, 433 是質(zhì)數(shù),(143, 443)=1奇數(shù)143不是質(zhì)數(shù)，但可用判定雅可比符號(hào)計(jì)算的勒讓德

44、符號(hào)2862143443243 443143 17 1143 1(1)k (產(chǎn)丁4432 1143 1 443 1(1尸(1尸二14331T73443J427143143143 1431原方程有解。四、證明題1、設(shè)(a, m) = 1 , d0是使 a1 (mod m)成立的最小正整數(shù)，則(i ) d。( m ；(ii)對(duì)于任意的 i , j , 0 i , jde 1 , i j ,有 ai aj (mod m)。(1)證明：(i)由Euler定理，de(m),因此，由帶余數(shù)除法，有(m) = qd。r, qZ, q > 0 , 0 r < dco因此，由上式及d0的定義，利用歐

45、拉定理得到1 a (m) aqd0 r ar (mod n),即整數(shù) r 滿足 ar 1 (mod m) , 0 r < d°。由d0的定義可知必是r = 0 ,即d° (m) o(ii)若式(1)不成立，則存在 i , j , 0 i , j d01, i j ,使 ai aj (modm) 。不妨設(shè) i > j 。因?yàn)?( a, m) = 1 ，所以ai j 0 (mod m) ， 0 < i j < d0。這與do的定義矛盾，所以式(1)必成立。2、證明：設(shè)a, b, c, m是正整數(shù)，m> 1 , (b, m) = 1 ,并且b a 1

46、 (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) 知：1b ax =b dbcy =b d( b c)yb d (mod m)。若x < 0 ，y > 0 ，由式(1) 知：1b cy =b dbax =b d( ba)xb d (mod m) 。3、設(shè)p是素?cái)?shù)，p bn1 , n N,則下面的兩個(gè)結(jié)論中至少有一個(gè)成立：(i ) p bd 1對(duì)于n的某個(gè)因數(shù)d < n成立；

47、(11) p 1 ( mod n )。若2 | n, p > 2 ,則(ii)中的mod n可以改為mod 2n。證明：記 d = ( n, p 1),由 b n 1 , bp 11 (mod p),及第 2題有b d 1 (mod p) 。若d < n,則結(jié)論(i )得證。若d = n，貝ij n p 1 ,即p 1 (mod n),這就是結(jié)論(ii)。若2 | n, p > 2 ,則p 1 （mod 2）。由此及結(jié)論（ii）,并利用同余的基本性質(zhì),得到 p 1 (mod 2 n)。初等數(shù)論練習(xí)題八一、單項(xiàng)選擇題1、設(shè) n > 1 ,則 n 為素?cái)?shù)是（n 1）!1 （

48、mod n）的（C ）0A. 必要但非充分條件B. 充分但非必要條件C. 充要條件D. 既非充分又非必要條件2、小于545 的正整數(shù)中，15 的倍數(shù)的個(gè)數(shù)是（C ）A.34B.35C.36D.373、 500!的標(biāo)準(zhǔn)分解式中7 的冪指數(shù)是（D ）A.79B.80C.81D.824、以下各組數(shù)中，成為10 的簡(jiǎn)化剩余系的是（D ）A.1,9,-3,-1B.1, 1,7,9C.5,7,11,13D. 1,1, 3,35、設(shè)n是正整數(shù)，下列選項(xiàng)為既約分?jǐn)?shù)的是( A )A.B.UC.UD.U5n 22n 15n 23n 1二、填空題1、(T ( 120) =360o2、7355的個(gè)位數(shù)字是工3、同余方

49、程3x三5(mod14)的解是x三11(mod1434、( ) =1 o235、-、'2 = -2。6、如果一個(gè)正整數(shù)具有6個(gè)正因數(shù)，問(wèn)這個(gè)正整數(shù)最小是 12。7、同余方程 x3+x2-x-1 =0(mod 5)的解是 x 三 ± 1(mod5)。三、計(jì)算題1、已知563是素?cái)?shù)，判定方程x2 429 (mod 563)是否有解。解：把鴛看成Jacobi符號(hào)，我們有563429563429 1 563 15635631)2 24294291344292429674291)4292 1-8-674292、6742967 1 429 1.(1)2 24296742967276727

50、 1 67 1.(1)2 267276727132727 113 1 -一(i)2.2 2713113故方程x2429 (mod 563)有解。1,求出模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 ,使得T +2n+ 3n+4n能被5整除。0 (mod 5);解：若 n 為奇數(shù)，則 1n+2n+3n + 4n 1n + 2n+ (-2) n+ (-1 )若 n=2m me Z

51、,則 1n+2n+3n+4n 12m+ 22m+ (-2) 2m+ (-1 ) 2m2+2X 22m=2+2X 4m=2+2X (-1) m(mod 5);當(dāng) m為奇數(shù)時(shí)，1n+2n+3n + 4n 0(mod 5);當(dāng) m為偶數(shù)時(shí)，1n+2n+3“ +4n 4(mod 5)。故當(dāng) 41n 時(shí)，5 I 1n+ 2n+3n+4n。四、證明題1、證明：若質(zhì)數(shù)p>2,則2P-1的質(zhì)因數(shù)一定是2pk+1形。證明：設(shè)q是2P-1的質(zhì)因數(shù)，由于2P-1為奇數(shù)，. qw2, (2, q) =1。由條件 q|2P-1,即 2P 三1 (mod q)。設(shè)h是使得2、三1 (modq)成立最小正整數(shù)，若1&

52、lt;h<p,則有h| p。這與p為質(zhì)數(shù)矛盾。從而h=p,于是p|q-1。又= q-1為偶數(shù)，2| q-1 ,2 p| q-1 , q-1=2pk, 即 q=2pk+1 k C Z。2、設(shè)(m,n) =1,證明：m(n)+n (m) =1 (mod mn)。證明：因?yàn)?m,n) =1,所以由歐拉定理知：n (m) =1 (mod m), m(n)三1 (mod n)于是 m (n) +n (m) = 1 (mod m), m +n (m) = 1 (mod n)。又因?yàn)?m,n) =1,所以 m(n)+n (m)三 1 (mod mn)。注：此題也可這樣表述：若兩個(gè)正整數(shù) a,b互質(zhì),則存在正整數(shù) m,n,使得an+bn = 1(mod ab)。p bp3、設(shè)(a,b) =1,a+bw0,p為一個(gè)同質(zhì)數(shù)，證明：(a b,-)1或p。 a bp p說(shuō)明：事實(shí)上，設(shè)(a b,ab-) d ,只需證明：d | p即可。 a b證明：由 a+b三0(mod a+b),即 a三-b (mod a+b),知 ak三(-b) k (mod a+b)。 p p其中 OWkWp-1。又 ap 1 ap 2babp 2 bp 1