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

1、初等數(shù)論練習(xí)題一、填空題1、(2420)=27;(2420)= 8802、設(shè)a, n是大于1的整數(shù)，若an-1是質(zhì)數(shù)，則a=_2.3、模9的絕對最小完全剩余系是 -4, -3,-2, -1, 0, 1, 2, 3, 4.4、同余方程9x+12三0(mod 37)的前犁是xm11(mod 37)。5、不定方程 18x-23y=100的通解是 x=900+23t, y=700+18t tZ。.6、分母是正整數(shù)m的既約真分?jǐn)?shù)的個數(shù)為(m)。7、18100被172除的余數(shù)是256。8、65103=-1 o9、若p是素數(shù)，則同余方程xp "(mod p)的解數(shù)為p-1二、計算題1、解同余方程：

2、3x211x200 (mod 105>解：因 105 = 357,同余方程 3x211x200 (mod 3)的解為 x1 (mod 3),同余方程 3x211x38 0 (mod 5)的解為 x0, 3 (mod 5), 同余方程 3x211x200 (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、判斷同余方程x2m42

3、(mod 107)是否有解解：(為107()107/ 42、(一)1 107/ 2 3 7、()1071,()1072、 / 3、 一)(一)1071073 1 107 1、丁F / 107、D 2 2()3)10727j絲J 1072(2) 1, ( ) ( 1) 2 2 (107)(-)310777故同余方程x2m42(mod 107)有解。3、求(127156+34) 28除以111的最小非負余數(shù) 解：易知 1271 m50 (mod 111)。由 502三58 (mod 111), 503m58X50m 14 (mod 111), 509三 143三80 (mod 111)知 5028

4、三(509) 3X50m803X50m803X 50m68X50m70 (mod 111)從而 5056m 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ù)時，ap-1+(p-1)am0 (mod p)；(2)當(dāng) a 為偶數(shù)時，ap-1-(p-1)am 0 (mod p)。證明：由歐拉定理知ap-1 = 1 (mod p)及(p-1)am-1 (mod p)立得(1)和(2)成立。2n2、設(shè)a為正奇數(shù)，n為正整數(shù)，試證am1(mod 2n+2)。 (1

5、)證明設(shè)a = 2m1,當(dāng)n = 1時，有a2 = (2m 1)2 = 4m(m1)11 (mod 23),即原式成立。一 ,，2kkjc設(shè)原式對于n = k成立，則有a 1 (mod 2k 2) a = 1q2k 2,k 1其中 qZ,所以 a= (1q2k+2)2 = 1q2k+31 (mod 2k+3),其中q是某個整數(shù)。這說明式(1)當(dāng)n = k1也成立。由歸納法知原式對所有正整數(shù)n成立。3、設(shè) p 是一個素數(shù)，且 1&k&p-1。證明：Cp 1(-1 ) k(mod p)京口日A ck (p 1)(p 2) (p k)小證明：設(shè)A=Cp 1得：k! A = (p-1)

6、 (p-2)(p-k)三(-1) (-2)(-k) (mod p)又(k!, p) =1,故人=或1(-1 ) k(mod p) 4、設(shè)p是不等于3和7的奇質(zhì)數(shù)，證明：p6m1(mod 84)。說明：因為84=4X3X7,所以，只需證明：p6= 1(mod 4)p6=1(mod3)p6 = 1(mod 7) 同時成立即可。證明：因為84=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)。同理可證：p6 = 1(mod3)p6=1(mod 7)。故有 p6= 1(

7、mod 84)。注：設(shè)p是不等于3和7的奇質(zhì)數(shù)，證明：p6三1(mod 168)。(見趙繼源p86)初等數(shù)論練習(xí)題二一、填空題1、(1000)=16;(除數(shù)函數(shù)：因數(shù)的個數(shù))(T (1000)=2340 .(和函數(shù):所有因數(shù)的和)2、2010!的規(guī)范分解式中，質(zhì)數(shù)11的次數(shù)是199 .3、費爾馬(Fermat)數(shù)是指Fn=220+1,這種數(shù)中最小的合數(shù) Fn中的n=5。4、同余方程13xm5(mod 31)的解是x三29(mod 31)5、分母不大于m的既約真分?jǐn)?shù)的個數(shù)為(2)+(3)+ -+(m)。6、設(shè)7 I (80n-1),則最小的正整數(shù)n= 6 .7、使41x+15y=C無非負整數(shù)解白

8、最大正整數(shù) C=_559_.8、也=1 .10119、若p是質(zhì)數(shù)，np1,則同余方程xn 1 (mod p)的解數(shù)為n_二、計算題1、試求200220032004被19除所得的余數(shù)。解：由 2002 三 7 (mod 19)20022三 11(mod 19)20023m 1 (mod 19)又由三22004三(22) 1002m1 (mod 3)可得：200420022003三 20023n+1 三(20023)nx 2002m 7(mod 19)2、解同余方程 3x144x10 6x18 0 (mod 5)。解：由Fermat定理，x5x (mod 5),因此，原同余方程等價于 2x2x 3

9、0 (mod 5)將x 0, 1, 2 (mod 5歷別代入上式進行驗證，可知這個同余方程解是x 1 (mod 5)。3、已知a=5, m=21,求使ax 1 (mod m)成立的最小自然數(shù)x。解：因為(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 (mod12)成立的最小數(shù)，經(jīng)計算知：x=6o三、證明題1、試證13|(54m+46n+2000)。(提示：可取模13進行計算性證明)證明：54m+46n+2000252m+642n+2000 (-1) 2m

10、+ (-1) 2n+0(mod 13)。2、證明 Wilson定理的逆定理：若n>1,并且(n 1)! 1(mod n),則n是素數(shù)。證明：假設(shè)n是合數(shù)，即n = mn2, 1 < n1 < n,由題設(shè)易知(n 1)! 1(mod m),得0 1(mod m),矛盾。故n是素數(shù)。3、證明：設(shè)ps表示全部由1組成的s位十進制數(shù)，若ps是素數(shù)，則s也是一個素數(shù)。證明：假設(shè)s是合數(shù)，即s=ab, 1<a, b<s。則Ps 11 1也(O-M,其中M>1是正整數(shù)。s 999由Pa>1也是正整數(shù)知ps是合數(shù)，這與題設(shè)矛盾。故s也是一個素數(shù)。4、證明：若 2p 1

11、 是奇素數(shù)，則(p!)2 (1)p 0(mod 2p 1)。證明：由威爾遜定理知 1 (2p)! = p!(p 1)(2p) (1)p(p!)2(mod 2p 1), 由此得(p!)2 (1)p 0(mod 2p 1)。5、設(shè)p是大于5的質(zhì)數(shù)，證明：p4m1(mod 240)。(提示：可由歐拉定理證明)證明：因為 240=23X3X5,所以只需證：p4=1(mod 8), p4= 1(mod 3), p4=1(mod 5)即可。事實上，由(8)=4, (3)=2, (5)=4以及歐拉定理立得結(jié)論。初等數(shù)論練習(xí)題三一、單項選擇題1、若n>1, (n)=n-1是n為質(zhì)數(shù)的( C )條件。A.

12、必要但非充分條件B.充分但非必要條件C充要條件D既非充分又非必要條件2、設(shè)n是正整數(shù)，以下各組a, b使臺為既約分?jǐn)?shù)的一組數(shù)是(D)。a=n+1, b=2n-1=2n-1, b=5n+2C.a=n+1 b=3n+1=3n+1, b=5n+23、使方程6x+5y=C無非負整數(shù)解的最大整數(shù)C是(A )。.24 C4、不是同余方程28x三21(mod 35)的解為(D )。三 2(mod 35) B. x 7(mod 35)C.2 17(mod 35) D. x 29(mod 35)5、設(shè) a 是整數(shù)，(1)am0(mod9)(2)a三2010(mod9)(3)a的十進位表示的各位數(shù)字之和可被 9整

13、除劃去a的十進位表示中所有的數(shù)字9,所得的新數(shù)被9整除以上各條件中，成為91a的充要條件的共有( C )。個個個個、填空題1、(r(2010)= 4896;(2010)=528 2、數(shù)C200的規(guī)范分解式中，質(zhì)因數(shù)7的指數(shù)是_3 3、每個數(shù)都有一個最小質(zhì)因數(shù)。所有不大于 10000的合數(shù)的最小質(zhì)因數(shù)中，最大者是 974、同余方程 24xm6(mod34)的解是 xi三 13(mod34)也三30(mod34)。5、整數(shù)n>1,且(n-1)!+1m0(mod n),則n為素數(shù)。6、3103被11除所得余數(shù)是57、6097三、計算題1、判定(i ) 2x3x2 3x1 0 (mod 5混否有

14、三個解；(ii) x62x5 4x2 3 0 (mod 5)是否有六個解解：(i ) 2x3x2 3x1 0 (mod 5)等價于 x33x2 4x3 0 (mod 5),又 x5x = (x33x2 4x3)(x2 3x5) +(6x212x 15),其中r(x) = &212x 15的系數(shù)不都是5的倍數(shù)，故原方程沒有三個解。(ii)因為這是對模5的同余方程，故原方程不可能有六個解。2、設(shè)n是正整數(shù)，求C12n,C2n, ,C2n 1的最大公約數(shù)。解：設(shè)(C2n,C2n,C2n 1) d,由 C2n C2n/22n 1 知 d22n1 ,設(shè) 2k|n 且 2k+1| n,即 2k +

15、1| n ,2 n則由 2k +1| C12n 及 2k 1 | Ci2n丁 C i2 n1 1 , i = 3, 5, 2n 1 得d = 2k + 1。3、已知a=18, m=77,求使ax 1 (mod m)成立的最小自然數(shù)x。解：因為(18, 77) =1,所以有歐拉定理知18(77)三1(mod 77)。又由于(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)計算知：x=30。四、證明題1、若質(zhì)數(shù)p>5,且2p+1是質(zhì)數(shù)，證明：4p+1必是

16、合數(shù)。證明：因為質(zhì)數(shù)p>5,所以(3, p) =1,可設(shè)p=3k+1或p=3k+2。當(dāng)p=3k+1時，2p+1=6k+3是合數(shù)，與題設(shè)矛盾，從而 p=3k+2, 此時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是兩個大于3的質(zhì)數(shù)，證明：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) ,

17、 q2m 1(mod 3), 于是p2三q2(mod 3),由于p, q都是奇數(shù),所以p2=1(mod 8) , q2m1(mod 8), 于是 p2=q2(mod 8)。故 p2三q2(mod 24)。3、若 x, yC R+ ,(1)證明：xy)xy;(2)試討論xypf xy的大小關(guān)系。注：我們知道，xy > x+y, x+y<x+y0此題把加法換成乘法又如何呢證明：(1)設(shè) x=x+a , 0& a <1, y=y+B ， 0< B <1。于是xy=xy+ b x+ a y+ a p所以xy=xy+ B x+ a y+ a ?>> xy

18、。(2) xypfxy之間等于、大于、小于三種關(guān)系都有可能出現(xiàn)。,1 一1當(dāng) x=y=一時，xy=xy=-;24當(dāng) x=3, y=1 時，xy=W , xy=1 ,此時xy>xy;2244當(dāng) x=-1 , y=-1 時，xy=1 , xy=1 ,此時xy< xy。23634、證明：存在一個有理數(shù) ,其中d< 100,能使k&=k迫dd100對于k=1, 2, ., 99均成立。證明：由(73, 100) =1以及裴蜀恒等式可知：存在整數(shù) c, d,使得73d-100c=1從而正k上= k(73d 100c)=上,由k< 100可知:100 d 100d100d0

19、<追k&<2100 d d設(shè)k-c- =n,貝(J 蛆 <n+1=n-Id ,于是ddd100-d =n+1, d故啕=n=k?。初等數(shù)論練習(xí)題四、單項選擇題,2n1、若Fn=21是合數(shù)，則最小的門是(D )。A. 2B. 3C. 4D. 52、記號ball a表示ba | a,但ba+1|a.以下各式中錯誤的一個是(B )。A. 21M 20! B. 1C5 II 50! C. 119 11100! D. 1316 II 200!3、對于任意整數(shù)n,最大公因數(shù)(2n+1, 6n-1)的所有可能值是( A )。A. 1 B. 4C. 1 或 2D. 1, 2 或 44

20、、設(shè)a是整數(shù)，下面同余式有可能成立的是(C )。A. a2 m 2 (mod 4)B.孑三 5 (mod 7) C. 3三 5 (mod 11) D. a2 m 6 (mod 13)5、如果amb(mod m), c是任意整數(shù)，則下列錯誤的是(A)A. ac= bc(mod mc) B. m|a-bC. (a, m)=(b, m) D. a=b+mt, tCZ 二、填空題1、d(10010)=_32_ M10010)=_2880一2、對于任意一個自然數(shù)n,為使自N起的n個相繼自然數(shù)都是合數(shù)，可取 N= (n+1)!3、為使3n-1與5n+7的最大公因數(shù)達到最大可能值，整數(shù) n應(yīng)滿足條件n=26

21、k+9, kC乙4、在5的倍數(shù)中，選擇盡可能小的正整數(shù)來構(gòu)成模12的一個簡化系，則這組數(shù)是5. 25.35, 555、同余方程 26x+1 m 33 (mod 74)的解是 X1 三24(mod74) X2三 61(mod74)6、不定方程5x+9y=86的正整數(shù)解是_x=1, y=9或x=10, y=4。7、54,=-189 三、計算題1、設(shè)n的十進制表示是I3xy45z,若792n,求x, y, z。解：因為 792 = 8911,故 792n 8n, 9n 及 11n。我們有8n845zz = 6,以及9n913xy45z = 19Xy9xy1,(1)11n11 z54yx31 = 3y

22、x113yx0(2)由于0 x, y9,所以由式(1)與式(2)分別得出xy1 = 9 或 18,3yx = 0 或 11。這樣得到四個方程組:其中a取值9或18, b取值0或11。在0x, y9的條件下解這四個方程組，得到：x = 8, y = 0, z = 6。2、求3406的末二位數(shù)。解：V(3, 100) =1, .3W00)三 1 (mod 100),而 帕00)= M22 52)=40,.二 340三 1(mod 100)； 3406=(340)10 36三(32)2 32m-19X 關(guān)-171 m29(mod 100)末二位數(shù)為29。3、求(214928+40)35被73除所得余

23、數(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 三-1 三 72(mod73)四、證明題1、設(shè)a1，a2, am是模m的完全剩余系，證明:(1)當(dāng)m為奇數(shù)時,(2)當(dāng)m為偶數(shù)時,a1 + a2+am=0 (mod m)；a1+ a2+am= m (mod m)。證明：因為1, 2,m a1,2a2, am都是模m的完全剩余系，所以maii 1mi mm) (mod m)。i 12(D當(dāng)m為奇數(shù)時，由寸Z即得：m嗎故：，汕尸0 (

24、mod m)0當(dāng) m 為偶數(shù)時，由(m, m+1) =1 即得：ai m(m_1) m(mod m)。i i22(m)2、證明：若m>2, ai, a2, a(m)是模m的任一簡化剩余系，則ai 0(mod m).i 1證明：若 ai, a2, a(m)是模 m的一個簡化剩余系，則 m-ai, m-a2, m-a(m)也是模 m(m)(m)(m)的一個簡化剩余系，于是：ai(m ai)(modm).從而：2 ai m (m)(modm).又i 1 i 1i 1.一 (m(m)由于 m>2, (m)是偶數(shù)。故：ai m 0(mod m).i 123、設(shè)m > 0是偶數(shù)，a1，

25、a2, ampf b1，b2, bm都是模m的完全剩余系，證明：a1b1, a2b2, ambm不是模m的完全剩余系。證明：因為1,m同理bii 12, m與a1,m aii 1m /一(mod m)0a2, am都是模m的完全剩余系，所以mi 嗎 m(mod m)。(1)如果ab1, a2b2, ambm是*Km的完全剩余系，那么也有(ai bi) m(mod m)。聯(lián)合上式與式和式，得到°三三mw卒這是不可能的，所以a1b1, a2b2, ambm不能是模m的完全剩余系。4、證明：(1) 2730 I x13-x;(2) 24 I x(x+2)(25X-1);初等數(shù)論練習(xí)題五一、

26、單項選擇題1、設(shè)x、y分別通過模m、n的完全剩余系，若(C)通過模mn的完全剩余系。、n都是質(zhì)數(shù)，則 my w n,則 my nxC. (m, n) =1,貝U my nxD. (m, n) =1,貝U mxny2、1X3X5X - X 2003X 2005X 2007X2009X 2011 規(guī)范分解式中 11 的幕指數(shù)是(A )。 .101C3、n為正整數(shù)，若2n-1為質(zhì)數(shù)，則n是(A )。A.質(zhì)數(shù)B.合數(shù)(k為正整數(shù))4、從100至IJ 500的自然數(shù)中，能被11整除的數(shù)的個數(shù)是(B )。.34 C5、模100的最小非負簡化剩余系中元素的個數(shù)是(C )。.10C二、填空題1、同余方程ax+

27、bm0(modm)有解的充分必要條件是(a, m) I b。 p 1q 12、高斯稱反轉(zhuǎn)定律是數(shù)論的酵母，反轉(zhuǎn)定律是指設(shè)p與q是不相同的兩個奇質(zhì)數(shù).(q) ( 1產(chǎn)至(p)3、被3除所得的余數(shù)為_1_。4、設(shè)n是大于2的整數(shù)，則(-1) (n)=_1_02, 22, 25、單位圓上的有理點的坐標(biāo)是(二0工 匚)或(烏二)，其中a與b是不全為 22 ,2222 ,22abab abab零的整數(shù)。6、若3258X a恰好是一個正整數(shù)的平方，則 a的最小值為36207、已知2011是一素數(shù)，則 =-1 02011 一一三、計算題1、求 32008X 72009X 132010 的個位數(shù)字。解. 32

28、008 X 72009 X 132010= 32008 乂 ( -3) 2009 x 32010= -32008+2009+2010=-36027 =-3X ( 32) 3013m3(mod 10)。2、求滿足(mn)=(m)+(n)的互質(zhì)的正整數(shù)m和n的值解：由(m, n) =1 知,(mn)=(m)(n)。于是有：(m)+(n)=(m)(n)設(shè)(m)=a, (n)=b,即有：a+b=abo 顯然 a I b, H b I a,因止匕 a=b。于是由 2a=a2 得 a=2,即(m)=(n)=2。故 m=3, n=4或 m=4, n=3。3、甲物每斤5元，乙物每斤3元，內(nèi)物每三斤1元，現(xiàn)在用

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

30、9=102011-1 m 0 (mod 2011)。2010 個2、設(shè)p是4n+1型的質(zhì)數(shù)，證明若a是p的平方剩余，則p-a也是p的平方剩余 證明：因為質(zhì)數(shù)p=4n+1, a是p的平方剩余，所以p 1a 1 a z a .=(1) =1p p pp即：p-a也是p的平方剩余。3、已知p, q是兩個不同的質(zhì)數(shù)，且 ap-1 = 1 (mod q), aq-1 = 1 (mod p),證明：apq=a (mod pq)。證明：由p, q是兩個不同的質(zhì)數(shù)知(p, q) =1。于是由Fermat定理ap=a (mod p), 又由題設(shè) aq-1= 1 (mod p)得到：apq= (aq)p=ap (

31、aq-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)?pi(1<i<k),則/、111(mn) mn(1 )(1 )(1 ) PiP2Pk/、111(m,n) m,n(1)(1) (1)P1P2Pk又 mn= (m, n) m, n “111 、故 (mn) (m,n)m,n(1 一)(1 一) (1 )(m,n) (m,n)。 P1P2Pk類似的題：設(shè)m=m1m2, m1與m由相同的質(zhì)因數(shù)，

32、證明：(m)=m2(m。初等數(shù)論練習(xí)題六一、填空題1、為了驗明2011是質(zhì)數(shù)，只需逐個驗算質(zhì)數(shù)2, 3, 5,書都不能整除2011,此時，質(zhì) 數(shù)p至少是43。2、最大公因數(shù)(4n+3, 5n+2)的可能值是_1/_。3、設(shè) 3a I 40!,而 3a+1| 40!,即 3alI 40!,貝U a =18。4、形如3n+1的自然數(shù)中，構(gòu)成模 8的一個完全系的最小那些數(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 = a2b2, z = a2b2,其中 a&

33、gt;b>0, (a, b) = 1, a 與 b 有不同的奇偶性。6、21x三 9 (mod 43)的解是 x三 25 (mod 43)。737、1991、將 區(qū)寫成三個既約分?jǐn)?shù)之和，它們的分母分別是3, 5和7。105一、117 x y z解：設(shè)右 o 7 二，即 35x 21y 15z = 17,因(35, 21) = 7，(7, 15) = 1,117,故有 105357解。分別解 5x 3y = 17t 15z = 17得 x = t 3u, y = 2t 5u, uZ,t = 11 15v, z = 4 7V vZ,消去 t 得 x = 11 15v 3u,y = 22 30

34、v 5u,z = 4 7v,u, vZo令 u =0, v =-1 得到：x =4,y =-8, z=3o 即：-171052、若3是質(zhì)數(shù)p的平方剩余,問p是什么形式的質(zhì)數(shù)解：由二次互反律 3p注意至p>3, p只能為p p1(mod 3)且-31(mod 4)1(mod 4)31只能下列情況p1(mod 3) p1(mod 4) p1(mod3)1(mod 4)p 1(mod12)或 p 1(mod 12)03、判斷不定方程x2+23y=17是否有解解：只要判斷x2m17(mod 23)是否有解即可17236 17三1(mod 4)； 23行行17 17317173,.x2=17(mo

35、d 23)無解，即原方程無解。三、論證題1、試證對任何實數(shù)x,包有x+ Cx+- =2x 2證明：設(shè) x=x+a , 0< a <1當(dāng) 0& a <:時，x+-1 =x, 2x=2岡.等式成立當(dāng)工 & a <1 時，x+-=x+1 , 2x=2x+1.等式成立22故對任何實數(shù)x,恒有岡+x+1=2x。22、證明：(1)當(dāng)n為奇數(shù)時，3 I (2n+1);(2)當(dāng)n為偶數(shù)時，3| (2n+1)0證明：由2n+1三(-1) n+1 (mod 3)立得結(jié)論3、證明：(1)當(dāng)3 1n (n為正整數(shù))時，7 1 (2n-1);(2)無論n為任何正整數(shù)，7| (2n

36、+1)0證明：(1)設(shè) n=3m,則 2n-1=8m-1 三0 (mod 7),即：7 I (2n-1);(2)由于 23mm 1 (mod 7)得23m+1 m2 (mod 7), 23m+1+1 三3 (mod 7), 23m+2+1 三5 (mod 7)。故無論n為任何正整數(shù)，7| (2n+1)04、設(shè) m>0, n>0,且 m 為奇數(shù)，證明：(2m-1 , 2n+1) =1。證明一：由m為奇數(shù)可知：2n+1 | 2mn+1,又有2m-1 | 2mn-1,于是存在整數(shù) x, y 使得：(2n+1) x=2mn+1, (2m-1)y=2mn-1。從而(2n+1) x-(2m-1

37、)y=2o 這表明：(2m-1, 2n+1) | 2由于2n+1, 2m-1均為奇數(shù)可知:(2m-1, 2n+1) =1。證明二：設(shè)(2m-1, 2n+1) =d,則存在 s, tCZ,使得 2m=sd+1, 2n=td-1。由此得到:2mn=(sd+1)n,2mn=(td-1)m于是 2mn=pd+ 1=qd - 1, p, qCZ。所以：(q-p) d =2。從而d I 2,就有d=1或2。由因為m為奇數(shù)，所以d=1。即(2m-1, 2n+1) =1。注：我們已證過：記Mn=2n 1,對于正整數(shù)a, b,有(Ma, Mb)= M(a, b)。顯然當(dāng)a*b, a, b為質(zhì)數(shù)時，(Ma, Mb

38、)=1。初等數(shù)論練習(xí)題七一、單項選擇題1、設(shè)a和b是正整數(shù)，則(叵旦,回以)=(A )a bA. 1B. aC. bD. (a, b)2、176至545的正整數(shù)中，13的倍數(shù)的個數(shù)是(B)A. 27B. 28C. 29D. 303、200!中末尾相繼的0的個數(shù)是(A)A. 49B. 50C. 51D. 524、從以下滿足規(guī)定要求的整數(shù)中，能選取出模20的簡化剩余系的是(B )A. 2的倍數(shù)B. 3的倍數(shù)C. 4的倍數(shù)D. 5的倍數(shù)5、設(shè)n是正整數(shù)，下列選項為既約分?jǐn)?shù)的是( A) “21n 4c n 1 仆2n1 n1A. B. C. D.14n 3 2n 15n2 3n1二、填空題1、3141

39、62被163除的余數(shù)是 1 0 (歐拉定理) 2、同余方程3x三5(mod13)的解是 x 6(mod13)。3、(逵工 1847，一4、-九=-4。5、為使n-1與3n的最大公因數(shù)達到最大的可能值，則整數(shù)n應(yīng)滿足條件n=3k+1, kCZ6、如果一個正整數(shù)具有21個正因數(shù)，問這個正整數(shù)最小是 26義32=576。7、同余方程 x3+x2-x-1=0(mod 3)的解是 x三 1, 2(mod 3)。三、計算題1、求不定方程x 2y 3z = 41的所有正整數(shù)解。解：分別解x 2y = tt 3z = 41 得 x = t 2uy = uuZ, t = 41 3v z = vvZ, 消去t得x

40、 = 41 3v 2uy = uz = vu, vZo由此得原方程的全部正整數(shù)解為(x, y, z) = (41 3v 2u, u, v), u > 0, v > 0, 41 3v 2u > 0。2、有一隊士兵，若三人一組，則余1人；若五人一組，則缺2人；若十一人一組，則余3 人。已知這隊士兵不超過170人，問這隊士兵有幾人解：設(shè)士兵有 x 人，由題意得 x 1 (mod 3), x2 (mod 5), x 3 (mod 11)。在孫子定理中，取 mi = 3, m2 = 5, m3 = 11, m = 3511 = 165Mi = 55, M2 = 33, M3 = 15,

41、M1 =1, M2 = 2, M3 = 3,則 x1551 (-2) 332 3153 58 (mod 165)因此所求的整數(shù)x = 52 + 165, tZ。由于這隊士兵不超過170人，所以這隊士兵有58人。23、判斷同余方程x 286(mod 443)是否有解解：286=2X143, 433 是質(zhì)數(shù),(143, 443)=1奇數(shù)143不是質(zhì)數(shù)，但可用判定雅可比符號計算的勒讓德符號2862143(1)4 (史3上義工443243443''''143143143 143143 17 1 143 114331(l) 8( 1)2 27鼻1；原方程有解。773四、證

42、明題1、設(shè)(a, m) = 1, do是使ad1 (mod m)成立的最小正整數(shù)，則(i ) do(m);(ii)對于任意的 i, j, 0 i, j do 1, ij,有 ai aj (mod m)。( 1)證明：(i)由Euler定理，do(m),因此，由帶余數(shù)除法，有(m) =qdor, qZ, q>0, 0 r < do。因此，由上式及do的定義，利用歐拉定理得到(m) qdo r r1 a a a (mod m),即整數(shù) r 滿足 ar 1(mod m), 0 r < do。由do的定義可知必是r = o,即do(m)。(ii)若式(1)不成立,則存在 i, j,

43、o i, j do 1, ij,使 aiaj (mod m)。 不妨設(shè) i>j。因為(a, m) = 1,所以 aij o (mod m), o < ij < do。這與do的定義矛盾，所以式(1)必成立。2、證明：設(shè)a, b, c, m是正整數(shù)，m>1, (b, m) = 1,并且ba 1(mod m), bc 1(mod m) (1)記 d = a, c),則 bd 1 (mod m)0證明：由裴蜀恒等式知，存在整數(shù) x, y,使得axcy = d,顯然xy< 0 若 x>0, y<0,由式(1)知：1 bax = bdbcy = bd(bc)yb

44、d (mod m)。 若 x<0, y>0,由式(1)知：1 bcy = bdbax = bd(ba)xbd (mod m)。3、設(shè)p是素數(shù)，pbn1, nN,則下面的兩個結(jié)論中至少有一個成立：(i ) pbd1對于n的某個因數(shù)d<n成立；(ii) p1 ( mod n )。若2|n, p>2,則(ii)中的mod n可以改為mod 2n。證明：記 d = (n, p 1),由 bn 1, bp 1 1(mod p),及第 2 題有bd1 (mod p)0若d < n,則結(jié)論(i )得證。若d = n,貝U np 1,即p 1 (mod n),這就是結(jié)論(ii )

45、。若2|n, p>2,則p 1 (mod 2)。由此及結(jié)論(ii),并利用同余的基本性質(zhì),得至U p 1 (mod 2n)。初等數(shù)論練習(xí)題八一、單項選擇題1、設(shè) n>1,則 n 為素數(shù)是(n 1)! 1(mod n)的(C)。A.必要但非充分條件B.充分但非必要條件C充要條件D既非充分又非必要條件2、小于545的正整數(shù)中，15的倍數(shù)的個數(shù)是(C).35C3、500!的規(guī)范分解式中7的幕指數(shù)是(D ).80C4、以下各組數(shù)中，成為模10的簡化剩余系的是( D ),9, 3, -1, 1, 7, 7, 11, 13 D.-1 , 1, 3, 35、設(shè)n是正整數(shù)，下列選項為既約分?jǐn)?shù)的是(

46、 A )3n 1 n 1 2n 1 n 1 5n 2 2n 15n 2 3n 11、(T ( 120) =360o 2、7355的個位數(shù)字是33、同余方程 3x= 5(mod14)的解是 x 11(mod14)。4、() =-1 o235、=-2。6、7、如果一個正整數(shù)具有6個正因數(shù)，問這個正整數(shù)最小是 同余方程x3+x2-x-1=0(mod 5)的角犁是x三± 1(mod5)。12。三、計算題1、已知563是素數(shù)，判定方程x2 429 (mod 563混否有解。解：把黑看成Jacobi符號，我們有429563429 15631-o5635631) 22429429134429242

47、9674291)4292 16784296742967 1 429 1(1)2 24296742967276727 1 67 1(1)2 267276727132727 113 11) 2 22713工131,故方程x2 429 (mod 563)有解。2、求出模23的所有的二次剩余和二次非剩余。解：模23的所有的二次剩余為18 (mod 23);x1, 2, 3, 4, 6, 8, 9, 12, 13, 16,模23的所有的二次非剩余為x5, 7, 10, 11, 14, 15, 17, 19, 20, 21, 22 (mod 23)。3、試求出所有正整數(shù)n ,使得1n + 2n+3n +

48、4n能被5整除。解：若 n 為奇數(shù)，則 1n + 2n+3n+4n1n+2n+ (-2) n+ (-1) n0 (mod 5);若 n=2m, mCZ,則 1n+2n+ 3n +4n12m+22m+ (-2) 2m+ (-1) 2m2+2X 22m=2+2X 4m=2+2X (-1)m(mod 5);當(dāng) m 為奇數(shù)時，1n + 2n+3n + 4n0(mod 5);當(dāng) m 為偶數(shù)時，1n + 2n+3n + 4n4(mod 5)。故當(dāng) 41n 時，5 I 1n+2n +3n+4n。四、證明題1、證明：若質(zhì)數(shù)p>2,則2P-1的質(zhì)因數(shù)一定是2pk+1形。證明：設(shè)q是2P-1的質(zhì)因數(shù)，由于2

49、P-1為奇數(shù)，.二qw2, (2, q) =1。由條件 q|2P-1,即 2Pm 1 (mod q)。設(shè)h是使得2xm1 (mod q)成立最小正整數(shù)，若1<h<p,則有h|p。這與p為 質(zhì)數(shù)矛盾。從而h=p,于是 p| q-1 o又= q-1為偶數(shù)，2| q-1,2p| q-1, q-1=2pk,即 q=2pk+1kCZ。2、設(shè)(m, n) =1,證明：m+n(m)三 1 (mod mn)。證明：因為(m, n) =1,所以由歐拉定理知：n(m)三1 (mod m), m(n)= 1 (mod n)于是 m+n(m)三 1 (mod m), m+n(m)三 1 (mod n)。又

50、因為(m, n) =1,所以 m+n(m)三 1 (mod mn)。注：此題也可這樣表述：若兩個正整數(shù) a, b互質(zhì)，則存在正整數(shù) m, n,使得am+bn 三 1(md ab)0a p b p3、設(shè)(a, b) =1, a+bw 0, p 為一個奇質(zhì)數(shù)，證明：(a b,) 1或p。a bp p說明：事實上，設(shè)(a b,a) d ,只需證明：d|p即可。a b證明：由 a+b4(mod a+b),即 a三b(mod a+b),知 ak汽-b)k(mod a+b)。 p p甘v a b p 1 p 2, p 2 p 1 p 1 p 1, p 1, p 1,另十 00kap-l。乂 a a b a

51、b b b b b pb (mod a b)。a bp p令(a b,a)d ,貝Ud|pbP-1。又(a,b)=1, d| (a+b)知(d,b) =1。a b(否則設(shè)(d, b) =d' >1,立即得到d' | a和d' | b,這與(a, b) =1矛盾。)于是(d , bp-1) =1 o 故 d| p,即 d=1 或 p。初等數(shù)論練習(xí)題九、單項選擇題1、以下Legendre符號等于-1的30被-1是（D）A. A1A_6、100至500的正整數(shù)中，能被17整除的個數(shù)是（B ）11111111A. 23B. 24C. 25D. 26 3、設(shè) 3 |500!

52、，但 3 1 | 500!,則 a =( C )A. .246. 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, 3n+1)=1 B. (2n-1, 2n+1) =1C. (2n, n+1) =1D. (2n + 1, n-1) =1、填空題1、25736被50除的余數(shù)是1 2、同余方程3x三5(mod16)的解是xm7

53、(mod16)3、不定方程 9x12y=15 的通解是 x = -1+4, y = -2 +3, tZ。4、32341=15、實數(shù)的小數(shù)部分記為x,則-5 = 4 一6、為使3n與4n+1的最大公因數(shù)達到最大可能值，整數(shù)n應(yīng)滿足條件n=3k+2、kC乙 7、如果一個正整數(shù)具有 35個正因數(shù)，問這個正整數(shù)最小是 26X34=5184。三、計算題1、解不定方程 9x+ 24y-5z=1000o解：解因(9, 24) =3, (3,-5) =1知原方程有解。原方程化為 9x 24y = 3t, 即fx8y = t, (1)3t-5z = 10003t-5z = 1000, (2)解（2）得5u200

54、3uuZ,再解3x8y =5u得到u 8vu 3vx u 8v故 y u 3v , u, vZ。z 200 3u2、設(shè) A = xi, x2,xm是模m的一個完全系，以x表示x的小數(shù)部分，若(a, m) = 1 ,解：當(dāng)x通過模m的完全剩余系時，axb也通過模m的完全剩余系，因此對于任意的i (1 i m), axb 一定與且只與某個整數(shù)j (1 j m)同余，即存在整數(shù)k,使得axb = kmj, (0j m-1)0 從而：mm 1m 1m 1 axibkjj j1m(m1) m_JoiJm'j0lm'jmj 1 mm 223、設(shè)整數(shù)n 2,求： i。即在數(shù)列1, 2, n中，與n互素的整數(shù)之和。1 i n (i,n) 1解：設(shè)在1, 2, n中與n互素的(n)個數(shù)是a1, a2, a(n), (a, n) = 1, 1 ain 1, 1 i(n),則