1、初等數論練習題一、填空題1、d(2420)=12;(2420)=_880_2、設a,n是大于1的整數，假設an-1是質數，則a=_2.3、模9的絕對最小完全剩余系是-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、分母是正整數m的既約真分數的個數為 (n)07、18100被172除的余數是256。8、強=-1。1039、假設p是素數，則同余方程xp 1 1(mod p)的解數為p-1。、計算題1、解同余方程：3x2 11

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

3、否有解？解：(衛)107)107/ 42、(一)1 1071,2 3 7)107)107(衛)(2)1071073_2?山 107(1) 22 (107)3107 )(馬)37L?10j 10721,()(1) 22 ()(-)10777故同余方程x2 三 42(mod 107)W 解。3、求127156+3428除以111的最小非負余數解：易知 1271 三50mod 111。由 502 三58mod 111, 50 3 m58X50三 14mod 111，509=143=80 mod 111知 5028 三5093X50m803X50m803X 50m68X 50三70mod 111從而

4、5056 三 16mod 111。故：127156+34 28三16+3428 三5028三70mod 111三、證明題1、已知p是質數,a,p二1,證明：1當 a 為奇數時，ap-1+(p-1)am0 (mod p)；2當 a 為偶數時，ap-1-(p-1)am0 (mod p)。證明：由歐拉定理知ap-1 = 1 (mod p)及(p-1) am-1 (mod p)立得1和2成立。2n2、設a為正奇數，n為正整數，試證am1(mod 2n+2)。 1證明設a = 2m 1,當n = 1時，有a2 = (2m 1)2 = 4m(m 1) 1 1 (mod 23),即原式成立。.2kk設原式對

5、于n = k成立，則有 a 1 (mod 2 ) a = 1 q2 ,k 1其中 qZ,所以 a2 = (1 q2k+2)2 = 1 q 2k + 3 1 (mod 2k + 3),其中q是某個整數。這說明式(1)當n = k 1也成立。由歸納法知原式對所有正整數n成立。3、設 p 是一個素數，且 1&k&p-1。證明：Cp 1-1k(mod p)。證明：設 A= Cp 1(p 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、設p是不等于3和7的奇質數，證明

6、：p6三1(mod 84)。說明：因為84=4X3X7,所以，只需證明：p6= 1(mod 4)p6= 1(mod3)p6= 1(mod 7)同時成立即可。證明：因為84=4X3X7及p是不等于3和7的奇質數，所以p, 4=1,p, 3=1,p, 7二1。由歐拉定理知：p (4) = p2=1(mod 4),從而p6三1(mod 4)。同理可證：p6m 1(mod3)p6= 1(mod 7)。故有 p6三 1(mod 84)。注：設p是不等于3和7的奇質數，證明：p6m1(mod 168)。見趙繼源p86初等數論練習題二、填空題1、d(1000)=16; (T (1000)=2340.2、20

7、10!的標準分解式中，質數11的次數是199 .n3、費爾馬(Fermat)數是指Fn=2 +1,這種數中最小的合數Fn中的n=54、同余方程13xm5(mod 31)的解I是xm29(mod 31)5、分母不大于 m的既約真分數的個數為(2)+(3)+ + (m)。6、設7 I (80n-1),則最小的正整數n=6.7、使41x+15y=C無非負整數解的最大正整數 C=_559.8、461019、假設p是質數，n p 1,則同余方程xn 1 (mod p)的解數為m二、計算題1、試求200220032004被19除所得的余數。解：由 2002三 7 (mod 19) 2002 2 m 11(

8、mod 19) 2002 3m 1 (mod 19)又由 20032004三 22004三221002m 1 (mod 3)可得：200220032004 三 20023n+1 三(20023)nX2002m 7(mod 19)2、解同余方程 3x14 4x10 6x 18 0 (mod 5)。解：由Fermat定理，x5 x (mod 5),因此，原同余方程等價于 2x2 x 3 0 (mod 5)將x 0, 1, 2 (mod 5)分別代入上式進行驗證，可知這個同余方程解是x 1 (mod 5)。3、已知a=5, m=21，求使a x 1 (mod m)成立的最小自然數x。解：因為5,21

9、=1,所以有歐拉定理知5(21)三1(mod 21)。又由于(21)=12 ,所以x|12,而12的所有正因數為1,2,3,4,6,12。于是x應為其中使 5 x 1 (mod 12)成立的最小數，經計算知：x=6o三、證明題1、試證13|(54m+46n+2000)。(提示：可取模13進行計算性證明)證明：54m+46n+2000 2 52m+642n+2000-12m+-12n+2000 2002 0(mod 13)。2、證明Wilson定理的逆定理：假設n > 1,并且(n 1)!1 (mod n),則n是素數。證明：假設n是合數，即n = mn2, 1 < m < n

10、,由題設易知(n 1)!1 (mod m),得01 (mod m),矛盾。故n是素數。3、證明：設Ps表示全部由1組成的s位十進制數，假設Ps是素數，則s也是一個素數證明：假設s是合數，即s=ab, 1<a, b<s。則Ps 11 1s10s 19(10a)b 1 10a 1M ,其中M> 1是正整數。由pa>1也是正整數知Ps是合數，這與題設矛盾。故s也是一個素數。4、證明：假設2P 1是奇素數，則 (p!)2 ( 1)p 0 (mod 2p 1)。證明：由威爾遜定理知1 (2p)! = p!(p 1) (2p) ( 1)P(p!)2(mod 2p 1),由此得(p!

11、)2 ( 1)p 0 (mod 2p 1)。5、設p是大于5的質數，證明：p4三1(mod 240)。提示：可由歐拉定理證明證明：因為 240=23X3X 5,所以只需證：p4= 1(mod 8), p4=1(mod 3), p4=1(mod 5)即可。事實上，由(8)=4 , (3)=2 , (5)=4以及歐拉定理立得結論。初等數論練習題三一、單項選擇題1、假設n>1, (n)=n-1是n為質數的C 條件。A.必要但非充分條件 B.充分但非必要條件 C.充要條件D.既非充分又非必要條件2、設n是正整數，以下各組a, b使b為既約分數的一組數是 D 。aA.a=n+1,b=2n-1 B.

12、a=2n-1,b=5n+2C.a=n+1,b=3n+1D.a=3n+1,b=5n+23、使方程6x+5y=C無非負整數解的最大整數 C是A 。4、不是同余方程28x三21(mod 35)的解為D A.x=2(mod 35) B. x =7(mod 35) C. x =17(mod 35) D. x =29(mod 35)5、設 a 是整數，(1)am0(mod9)(2)a三2010(mod9)(3)a的十進位表示的各位數字之和可被 9整除劃去a的十進位表示中所有的數字9,所得的新數被9整除以上各條件中，成為91a的充要條件的共有 C 。B.2個 C.3個、填空題1、(T (2010)=4896

13、;(2010)=528o 2、數C200的標準分解式中，質因數7的指數是_3 3、每個數都有一個最小質因數。所有不大于 10000的合數的最小質因數中，最大者是 97 4、同余方程 24x三6(mod34)的解是 xi 三 13(mod34) X2三30(mod34)。5、整數n>1,且(n-1)!+1m0(mod n),則n為素數。6、3103被11除所得余數是5 。7、6097=_-1Q三、計算題1、判定(i)2x3x23x10 (mod 5)是否有三個解；(ii)x62x54x230 (mod 5)是否有六個解？解：(i) 2x3 x2 3x 1 0 (mod 5)等價于 x3 3

14、x2 4x 3 0 (mod 5),又 x5 x = (x3 3x2 4x 3)(x2 3x 5) + (6x2 12x 15),其中 r(x) = 6x2 12x 15 的系數不都是 5 的倍數，故原方程沒有三個解。(ii)因為這是對模5的同余方程，故原方程不可能有六個解。2、設n是正整數，求C2n,C3n, ,C2n 1的最大公約數。解：設(UnGn,C2n 1)d,由 C12n C2n 嗡 122n 1知 d 22n ;設 2k|n 且 2k+1|n,即 2k+1|n ,則由 2k +1|C 12n 及 2klic 2n/Ci2n，i = 3, 5, 2n 1 得 d = 2k + 3、

15、已知a=18,m=77，求使ax 1 (mod m)成立的最小自然數 x。解：因為18,77=1,所以有歐拉定理知18(77)三1(mod 77)。又由于(77)=60 ,所以 x|60,而 60 的所有正因數為 1,2,3,4,5,6,10,12,15,20,30, 60于是x應為其中使18x 1 (mod 77)成立的最小數，經計算知：x=30。四、證明題1、假設質數p>5,且2p+1是質數，證明：4p+1必是合數。證明：因為質數p> 5,所以3, p=1,可設p=3k+1或p=3k+2。當p=3k+1時，2p+1=6k+3是合數，與題設矛盾，從而 p=3k+2, 此時2p+1

16、是形如6k+5的質數，而4p+1=12k+9=3(4k+3)是合數。注：也可設p=6k+r, r=0,1,2,3,4,5 。再分類討論。2、設p、q是兩個大于3的質數，證明：p2三q2(mod 24)。證明：因為24=3X8,3,8=1,所以只需證明：p2=q2(mod 3)p2=q2(mod 8)同時成立。事實上， 由于p, 3二1,q, 3二1,所以 p2=1(mod 3) , q2m 1(mod 3), 于是p2三q2(mod 3),由于p, q都是奇數，所以p2三1(mod 8) , q2三1(mod 8), 于是 p2=q2(mod 8)。故 p2 = q2(mod 24)。3、彳貿

17、設x,y C R ,1證明：xy > xy;2試討論xy與xy的大小關系。注：我們知道，x y >x+ y, x+y<x+y0此題把加法換成乘法又如何呢? 證明：1設 x二岡+ a ,0 < a <1, y=y+ B ,0 & B <1。于是xy=xy+B x+ a y+ a B所以xy二岡y+ Bx+ ay+ aB > xy。2xy與xy之間等于、大于、小于三種關系都有可能出現。當 x二y二1 時，xy=xy=1 ;1.1 ,止匕時xy >xy；411,此時xy <xy3k-=kJ324當 x= 3 , y= 1 時，xy= 3

18、, xy=224當 x=- 1, y=-1 時，xy= " , xy= 2364、證明：存在一個有理數其中d< 100，能使對于k=1, 2, ., 99均成立。證明：由73, 100=1以及裴蜀恒等式可知：存在整數 c, d,使得73d-100c=173 . kc k(73d 100c) k 從而k -=-=,由k< 100可矢口：100 d 100d100d0V23八匕100 d設k, =n,則卜口+1=n1d ,于是ddd衛k 100嚅=n = kkc 1 n 1&d =n+1, d d抖初等數論練習題四一、單項選擇題1、假設Fn=2? 1是合數，則最小的口

19、是(D )。A. 2B. 3C. 4D. 52、記號ba II a表示ba | a,但ba+1| a.以下各式中錯誤的一個是(B )。A. 218 II 20! B. 105 1150! C. 119 | 100! D. 1316 II 200!3、對于任意整數n,最大公因數(2n+1, 6n-1)的所有可能值是( A )。A. 1 B. 4C. 1 或 2D. 1, 2 或 44、設a是整數，下面同余式有可能成立的是(C )。A. a2 m 2 (mod 4)B. a2=5 (mod 7) C. a2=5 (mod 11)D. a2 m 6 (mod 13)5、如果amb(mod m), c

20、是任意整數，則以下錯誤的選項是 A A. ac= bc(mod mc) B. m|a-b C. (a,m)=(b,m) D. a=b+mt,tCZ 二、填空題1、d(10010)=_32_, (X10010)=_288G_,2、對于任意一個自然數n,為使自N起的n個相繼自然數都是合數，可取 N=n+1！ 3、為使3n-1與5n+7的最大公因數到達最大可能值，整數n應滿足條件n=26k+9. kCZ。4、在5的倍數中，選擇盡可能小的正整數來構成模12的一個簡化系，則這組數是5,25,35,555、同余方程 26x+1 m 33 (mod 74)的解星 X1 三 24(mod74) x2三61(m

21、od74)6、不定方程5x+9y=86的正整數解是_x=1,y=9或x=10,y=4。7、54 = -1 o89一三、計算題1、設n的十進制表示是I3xy45z ,假設792 n,求x, y, z解：因為 792 = 8911,故 792 n 8 n, 9 n 及 11 n。我們有8 n 8夜 z = 6,以及9 x y 1,11 3 y x。(2)9 n91 3xy45z = 19 x y11 n11z 5 4yx 3 1 = 3 y x由于0 x, y 9,所以由式(1)與式(2)分別得出x y 1 = 9 或 18,3 y x = 0 或 11。這樣得到四個方程組:其中a取值9或18,

22、b取值0或11。在0 x, y 9的條件下解這四個方程組，得至U： x = 8, y = 0, z = 6。2、求3406的末二位數。解：V3, 100=1,3100)1mod 100，而 設100)=小(22 52)=40,.二 340三 1(mod 100) .二 3406=(340)10 36三(3 2)2 32m-19X 9m-171 三29(mod 100)末二位數為29。3、求(214928+40)35被73除所得余數。解：(214928+40)35三(3228+40)35三(32X32)14+4035 三(102414+40)35 三(214+40)35 三(210X24+40)

23、35 三(25+40)35 三 7235 三-1 三 72(mod 73)四、證明題1、設a1, a2, , am是模m的完全剩余系，證明：1當 m 為奇數時，a1+ a2+ am =0mod m；12當 m 為偶數時，a1+ a2+ + am 三mmod m。2證明：因為1,2, , m與a1, a2, , am都是模m的完全剩余系，所以mai i 1m(m 1) /- (mod m)0當m為奇數時'由1 z即得：mm(m 1)2m(m 1)20 (mod m)。m(m 1) m /- 萬(mod m)0m2當m為偶數時，由m,m+1=1即得：aii 1(m)2、證明：假設m>

24、 2, a1, a2, , a (m)是*gm的任一簡化剩余系，則 ai 0(modm). i 1m-a (m)也是模證明：假設a1, a2, a (m)是模m的一個簡化剩余系，則 m-a1, m-a2,m的一個簡化剩余系，于是:(m)aii 1(m)(m)(m ai)(modm).從而：2aii 1i 1m (m)(modm).又由于m>2, (m)是偶數。故:M m 3 0(modm).i12學習文檔僅供參考3、設m > 0是偶數，a1, a2, , am與b1, b2, , bm都是模m的完全剩余系，證明：a1 b1,a2 b2, am bm不是模m的完全剩余系證明：因為1,

25、2, , m與a1, a2, , am都是模m的完全剩余系，所以mai i 1mm(m 1) m ,.、i - (mod m)。i 122 ''同理« (mod m)0i 12、，(2)如果a1 b1, a2 b2, , am bm是模m的完全剩余系，那么也有m(aii 1bi) m (mod m)0聯合上式與式(1)和式(2),得到 0 m寧 m(mod m),這是不可能的，所以a1 b1, a2 b2, , am bm不能是模m的完全剩余系4、證明：12730 I x13-x;224 I x(x+2)(25x2-1);3504 I x9-x3;4設質數 p>

26、3,證明：6Pl xp-x。證明：1因為 2730=2X3X 5X 7X 13, 2,3,5 , 7,13 兩兩互質，所以：由 x13-x=x (x12-1)=0 (mod 2)知：2 I x13-x; 13 I x13-x;由 x13-x=x (x12-1)=x(x2-1)(x2+1)(x8+x4+1)三0 (mod 3)知:3 I x13-x;由 x13-x=x (x 12-1)=x(x4-1) (x8+x4+1) = 0 (mod 5)知:5 I x13-x;由 x13-x=x (x12-1)=x(x6-1)(x6+1)三0 (mod 7)知:7 I x13-x。故有 2730 I x1

27、3-x。同理可證2、3、4。初等數論練習題五一、單項選擇題1、設x、y分別通過模m、n的完全剩余系，假設C通過模mn的完全剩余系。A.m、 n 者B是質數，則 mynx B.mwn, 則 my nxC.m, n =1,貝Umy nxD.Cm, n =1,貝U mxny2、1X3X5X-X 2003X 2005X 2007X 2009 X 2011 標準分解式中 11 的幕指數是(A )。3、n為正整數，假設2n-1為質數，則口是(A )。k(k為正整數)4、從100到500的自然數中，能被11整除的數的個數是(B )5、模100的最小非負簡化剩余系中元素的個數是(C )。、填空題1、同余方程a

28、x+bm0(modm)有解的充分必要條件是(a,m) I b。p1q12、高斯稱反轉定律是數論的酵母，反轉定律是指設p與q是不相同的兩個奇質數.(q) ( 1)2 2 (p)pq3、20 1 22012被3除所得的余數為 1 04、設n是大于2的整數，則(-1) (n)=_1_0 2. 22. 25、單位圓上的有理點的坐標是(萼, "2)或(R2,萼J),其中a與b是不全為 abab abab零的整數。6、假設3258Xa恰好是一個正整數的平方，則 a的最小值為362。7、已知2011是一素數，則二2- = -1 。2011 一一、計算題1、求 32008X 72009X 13201

29、0 的個位數字。解:2008X 72009X 132010三32008x-32009X 32010 三-32008+2009+2010=-36027 =-3X323013 三 3(mod 10)2、求滿足(mn)= (m)+ (n)的互質的正整數m和n的值。解：由m, n=1 知，(mn)= (m) (n)。于是有：(m)+ (n)= (m) (n)設 (m)=a,(n)=b,即有：a+b=ah 顯然 a I b,且 b I a,因止匕 a=b。于是由 2a=a2 得 a=2,即(m)= (n)=2。故 m=3,n=4 或 m=4,n=3。3、甲物每斤5元，乙物每斤3元，內物每三斤1元，現在用

30、100元買這三樣東西共100 斤，問各買幾斤？解：設買甲物x斤，乙物y斤，內物z斤，則5x 3y 1z = 100,3x y z = 100o消去 z,得到7x 4y = 100。(1)顯然x = 0, y = 25是方程(1)的解，因此，方程(1)的一般解是x 4ty 25 7t因為 x>0, y>0,所以0Vt 3。即t可以取值t1 = 1, t2 = 2, t3 = 3。相應的x, y, z的值是(x, y, z) = (4, 18, 78), (8,11,81), (12,4, 84)。四、證明題1、已知2011是質數，WJ有2011|99 9。2010個證明：99 9=1

31、02011-1 m 0 (mod 2011)。2010 個2、設p是4n+1型的質數，證明假設a是p的平方剩余，則p-a也是p的平方剩余 證明：因為質數p=4n+1, a是p的平方剩余，所以p 1p a a 1 a r a=(1) 2=1p pppp即：p-a也是p的平方剩余。3、已知p,q是兩個不同的質數,且ap-1三1 (mod q), sq-1 = 1 (mod p),證明：apq=a (mod pq)。證明：由p,q是兩個不同的質數知p, q二1。于是由Fermat定理ap=a (mod p), 又由題設 aq-1 m 1 (mod p*l到：apq=(aq)p = ap (aq-1)

32、p=ap=a (mod p)。同理可證：apq=a (mod q)。故：apq=a (mod pq)。4、證明：假設m,n都是正整數，則(mn)=m,n (m,n)。證明：易知mn與m,n有完全相同的質因數，設它們為 pi (1 < i < k),則,、111(mn) mn(1 )(1 )(1 )Rp2pk,、111(m,n)m, n(1 -)(1 ) (1 )p1p2pk又 mn二m,nm,n 111、,、 一 一故 (mn) (m,n)m,n(1 )(1 一) (1 一) (m,n) (m,n)。p1p2pk類似的題：設m二m1m2, m1與m由相同的質因數，證明： (m)=m

33、2 (m1)初等數論練習題六一、填空題1、為了驗明2011是質數，只需逐個驗算質數 2, 3, 5,書都不能整除2011,此時，質 數p至少是 43。2、最大公因數(4n+3,5n+2)的可能值是_17_。3、設 3個40!,而 3" 40!,即 3, 40!,則 a =18-4、形如3n+1的自然數中，構成模8的一個完全系的最小那些數是1,4,7,10,13,16,19, 22。5、不定方程 x2+y2=z2,2|x, (x,y)=1, x,y,z>0 的整數解是且僅是 x = 2ab. y = a2 b2, z = a2 b2,其中a > b > 0, (a,

34、b)二1, a與b有不同的奇偶性。6、21x9 (mod 43)的解是 x 三 25 (mod 43)。i73 _ .7、- 1 0199二、計算題1、將 比寫成三個既約分數之和，它們的分母分別是 3, 5和7。10517 x y z解：設 一 - 一，即 35x 21y 15z = 17,因(35, 21) = 7, (7, 15) = 1, 1 17,故10535 7有解。分別解5x 3y = t7t 15z = 17得消去t得x = t 3u, y = 2t 5u, u Z , t = 11 15v, z =4 7V v Z, x = 11 15v 3u, y = 22 30v 5u,

35、z =4 7v,u, v Zo令 u =0, v =-1 得到：x =4, y =-8, z=3o 即：-17 4105 3_83572、假設3是質數p的平方剩余，問p是什么形式的質數?p 1解：:由二次互反律A ( 1)- EP3、一，一,p汪息到p>3, p只能為p 1(mod 3)且 31 p 1(mod4)1 p 1(mod4)-1只能以下情況p 1(mod 3) pp 1(mod 4)p 1(mod3)p 1(mod4)p 1(mod 12)或 p 1(mod 12)。3、判斷不定方程x2+23y=17是否有解？解：只要判斷x2三17(mod 23)是否有解即可17= 1(mo

36、d 4)1723172231717171717x2=17(mod 23)無解,即原方程無解。三、論證題1、試證對任何實數x,包有x+x+1=2x 2證明：設 x=x+ a ,0< a <1等式成立等式成立當 00 a < 1時，x +-=x,2x=2x22當 1< a < 1 時，x +1 =x+1, 2x=2x+1 22故對任何實數x,恒有岡+x+ 1 =2x o 22、證明：1當n為奇數時，3 I 2n+1；2當n為偶數時，3|2n+1。證明：由2n+1三-1n+1mod 3立得結論。3、證明：1當3 1nn為正整數時，7 1 2n-1；2無論n為任何正整數，

37、7|2n+1。證明：1設 n=3mj 則 20- 1=8、-1 =0mod 7，即：7 I 20- 1；2由于 23m 三 1mod 7得23m +1=2mod 7, 23m+1+1 三3mod 7, 23m+2+1 三5mod 7。故無論n為任何正整數，7|2n+1。4、設 m>0, n>0,且 m為奇數，證明：2m-1, 2n+1=1。證明一：由m為奇數可知：2n+1 1 2mn+1,又有2m-1 1 2mn-1,于是存在整數 x,y 使得：2n+1x=2mn+1, (2m-1)y=2mn-1。從而2n+1x-(2m-1)y=2。這說明：2m-1, 2n+1| 2由于2n+1,

38、 2m-1均為奇數可知：2m-1, 2n+1=1。證明二：設2m-1, 2n+1=d,則存在 s,t C Z,使得 2m=sd+1,2 n =td-1。由此得到:2mn=(sd+1) n, 2 mn =(td-1) m于是 2mn=pd + 1 = qd - 1, p,q C Z。所以：q -pd =2。從而d I 2,就有d =1或2。由因為m為奇數，所以d =1。即2m-1, 2n+1=1。注：我們已證過：記 Mn=2n 1 ,對于正整數a, b,有(Ma, Mb) = M(a, b)。顯然當a*b, a,b為質數時，(Ma, Mb) =10初等數論練習題七一、單項選擇題1、設a和b是正整

39、數，則(叵也,回9)= a a bA. 1B. aC. bD.(a,b)2、176至545的正整數中，13的倍數的個數是A. 27B. 28C. 29D. 303、200!中末尾相繼的0的個數是A. 49B. 50C. 51D. 524、從以下滿足規定要求的整數中,能選取出模20的簡化剩余系的是B A. 2的倍數 B. 3的倍數5、設n是正整數，以下選項為既約分數的是“21n 4- n 1A. B.14n 3 2n 1、填空題c 2n 1C. D.5n 2n 13n 11、314162被163除的余數是1O歐拉定理2、同余方程3x三5(mod13)的解是xm5(mod13)。3、(逆)心184

40、74、-冗=-4。5、為使n-1與3n的最大公因數到達最大的可能值，則整數 n應滿足條件n=3k+1,kC Z。6、如果一個正整數具有21個正因數，問這個正整數最小是 26義32=576。7、同余方程 x3+x2-x-1 =0(mod 3)的解是 x三 1,2(mod 3)。三、計算題1、求不定方程x 2y 3z = 41的所有正整數解。 解：分別解x 2y = tt 3z = 41得x = t 2uy = uu Z,t = 41 3vz = vv Z ,消去t得 x = 41 3v 2uy = uz = vu, v Zo由此得原方程的全部正整數解為(x, y, z) = (41 3v 2u,

41、 u, v), u > 0, v > 0, 41 3v 2u > 0。2、有一隊士兵，假設三人一組，則余 1人；假設五人一組，則缺2人；假設十一人一組, 則余3人。已知這隊士兵不超過170人，問這隊士兵有幾人？解：設士兵有 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,WJ x 1 55 1-233 2 3153 58 (mod

42、165),因此所求的整數x = 52 + 165t, t Z。由于這隊士兵不超過170人，所以這隊士兵有58人。3、判斷同余方程x 2286(mod 443)是否有解？解：286=2X143, 433 是質數,(143, 443)=1奇數143不是質數，但可用判定雅可比符號計算的勒讓德符號4432 1143 1 443 12862143( 1)-(9二44324A443243443' '' '143143143143143 17 1 143 114331,(l) 8 ( 1) 2 2 731;原方程有解。四、證明題1、設(a, m) = 1, d0是使ad 1

43、(mod m)成立的最小正整數，則 d0(m);(ii)對于任意的 i, j, 0 i, j d0 1, i j,有 ai aj (mod m)。1證明：(i)由Euler定理，d。(m),因此，由帶余數除法，有(m) = qd。 r, q Z, q > 0, 0 r < do。因此，由上式及d0的定義，利用歐拉定理得到(m)qd0 r r1 a a a (mod m),即整數 r 滿足 ar 1 (mod m), 0 r < d0。由do的定義可知必是r = 0,即d0 (m)0(ii) 假設式(1)不成立，則存在 i, j, 0 i, j d0 1, i j,使 ai a

44、j (mod m)。不妨設 i > j0 因為(a, m) = 1,所以 ai j 0 (mod m), 0 < i j < d0。這與 d0 的定義矛盾，所以式(1)必成立。2、證明：設a， b， c， m 是正整數， m > 1， (b, m) = 1 ，并且ba 1 (mod m)， bc 1 (mod m)1記 d = (a, c) ，則bd 1 (mod m) 。證明：由裴蜀恒等式知，存在整數 x, y,使得ax cy = d,顯然xy< 0。假設x > 0， y <0，由式(1)知：1bax = bdb cy =bd(bc)ybd (mod

45、 m)。假設x < 0， y >0，由式(1)知：1bcy = bdb ax =b d(ba)xbd (mod m)。3、設p 是素數， p bn 1， n N ，則下面的兩個結論中至少有一個成立：(i ) p bd 1對于n的某個因數d < n成立；(11) p 1 ( mod n )。假設2|n, p > 2,則(ii)中的mod n可以改為mod 2n。證明：記 d = (n, p 1),由 bn 1, bp 1 1 (mod p),及第 2題有b d 1 (mod p) 。假設d < n,則結論(i)得證。假l設d = n,貝U n p 1,即p 1 (m

46、od n),這就是結論(ii)。假設2|n, p > 2,則p 1 (mod 2)。由此及結論(ii),并利用同余的基本性質,得到 p 1 (mod 2n)。初等數論練習題八一、單項選擇題1、設 n > 1，則 n 為素數是 (n 1)!1 (mod n) 的 C 。2、小于 545 的正整數中， 15 的倍數的個數是 C 3、 500!的標準分解式中 7 的冪指數是 D 4、以下各組數中，成為模 10 的簡化剩余系的是 D D. 1,1, 3,3A.1,9, 3, 1B.1, 1,7,9C.5,7,11,135、設 n 是正整數，以下選項為既約分數的是 A 學習文檔 僅供參考A.

47、3L2b.JLJc.Ud.U5n 22n 15n 23n 1二、填空題1、(T 120=360o2、7355的個位數字是33、同余方程3x三5(mod14)的解是x三11(mod14)。4、 =1 o235、-應=26、如果一個正整數具有6個正因數，問這個正整數最小是 12。7、同余方程 x3+x2-x-1 =0(mod 5)的解是 x 三 ± 1(mod5)。三、計算題1、已知563是素數，判定方程x2 429 (mod 563)是否有解。2、解：把鷲563429563674291327故方程x2看成Jacobi符號，我們有429 1 563 1lcc22-5635631) 2 2

48、42942967 1 429 1. (1)2 227 113 11) 2 22713429 (mod 563)134429242967429(1)4292 16784294296742967276727 1 67 1(1) 267276727113有解。求出模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、試求出所有正整數n ,使得1n +2n+3n+4n能被5整除。解：假設 n 為奇數，則 1n

49、+ 2n+3n + 4n 1n+ 2n+-2n +-1n0 (mod 5);假設 n=2m, mC Z,則 1n+ 2n+3n+ 4n 12m+22m+-22m+-12m2+2X 22m =2+2X 4m =2+2X(-1)m(mod 5);當 m 為奇數時，1n+2n+ 3n+4n 0(mod 5);當 m 為偶數時，1n+2n + 3n+4n 4(mod 5)。故當 41n 時，5 I 1n + 2n+3n + 4n四、證明題1、證明：假設質數p>2,則2P-1的質因數一定是2pk+1形。證明：設q是2P-1的質因數，由于2P-1為奇數， qw2,2, q=1由條件 q|2P-1,即

50、 2P 三1mod q設h是使得2x =1mod q成立最小正整數，假設1<h<p,則有h| p。這與p 為質數矛盾。從而h=p,于是 p|q-1 0又: q-1為偶數，2|q-1,2p|q-1, q-1=2pk, 即 q=2pk+1 k C Z。2、設m,n=1,證明：m +n (m) =1 (mod mn)。證明：因為m,n=1,所以由歐拉定理知：n (m) =1 (mod m), m=1 (mod n)于是 m +n (m) =1 (mod m), m +n (m) = 1 (mod n)。又因為m,n=1,所以 m +n (m) =1 (mod mn)。注：此題也可這樣表述

51、：假設兩個正整數 a,b互質，則存在正整數 m,n,使得am+bn 三 1(mod ab) p bp3、設a,b=1,a+bw0,p為一個奇質數，證明:(ap . p b,arv)說明：事實上，設(a b,久旦)d,只需證明：d | p即可。a b證明：由 a+b聲(mod a+b),即 a-b (mod a+b),知 ak/-b) k (mod a+b)。p p甘 tbcvkvcd v a b p 1 p 2, p 2 p 1 p 1, p 1, p 1, p 1,丹中 uakap-l。乂 a a b ab b b b b pb (mod a b)a bp p令(a b, a)d ,貝U d

52、 | pbp-1。 又a,b二1, d |a+b知d,b二1。a b否則設d,b=d' >1,立即得到d' I a和d' | b,這與a,b二1矛盾。于是d , bp-1=1 o 故 d | p,即 d =1 或 p。初等數論練習題九、單項選擇題A. 2111、以下Legendre符號等于-1的30被-1是(D )B.11112、100至500的正整數中，能被17整除的個數是A. 23B. 24C. 25D. 26學習文檔僅供參考3、設 3 |500!,但 3 1 | 500!,則 a =( C )D. 248A. 2454、以下數組中，成為模7的完全剩余系的是(CA. 14, 4, 0, 515, 18, 19 B.7, 10141925, 32, 40C. 4, 2, 8, 13, 32, 35, 135 D. 3, 3, 4, 4, 5, 5, 0 5、設n是正整數，則以下各式中一定成立的是(B )A. (n+1, 3n+ 1)=1B.2n1, 2n+1 =1C.2n, n+1=1D.2n+1, n1=1二、填空題1、25736被50除的余數是2、同余方程3x三5(mod16)的解是xm7(mod16)。3、不定方程 9x12y=15 的通解是