信息安全數(shù)學(xué)基礎(chǔ)習(xí)題答案

1、信息安全數(shù)學(xué)基礎(chǔ)習(xí)題答案第一章 整數(shù)的可除性1證明：因?yàn)?|n 所以n=2k , kz 5|n 所以5|2k ， 又（5，2）=1，所以5|k 即k=5 k1 ，k1z 7|n 所以7|2*5 k1 ,又（7，10）=1，所以7| k1 即k1=7 k2，k2z 所以n=2*5*7 k2 即n=70 k2, k2z 因此70|n2證明：因?yàn)閍3-a=(a-1)a(a+1) 當(dāng)a=3k，kz 3|a 則3|a3-a 當(dāng)a=3k-1，kz 3|a+1 則3|a3-a 當(dāng)a=3k+1，kz 3|a-1 則3|a3-a 所以a3-a能被3整除。3證明：任意奇整數(shù)可表示為2 k0+1， k0z （2 k

2、0+1）24 k02+4 k0+1=4 k0 (k0+1)+1 由于k0與k0+1為兩連續(xù)整數(shù)，必有一個(gè)為偶數(shù)，所以k0 (k0+1)=2k 所以（2 k0+1）2=8k+1 得證。4證明：設(shè)三個(gè)連續(xù)整數(shù)為a-1,a,a+1 則(a-1)a(a+1)= a3-a 由第二題結(jié)論3|（a3-a） 即3|(a-1)a(a+1) 又三個(gè)連續(xù)整數(shù)中必有至少一個(gè)為偶數(shù)，則2|(a-1)a(a+1) 又（3，2）=1 所以6|(a-1)a(a+1) 得證。5證明：構(gòu)造下列k個(gè)連續(xù)正整數(shù)列： (k+1)！+2, (k+1)！+3, (k+1)！+4, (k+1)！+(k+1), kz 對(duì)數(shù)列中任一數(shù) (k+1

3、)！+i=i(k+1)k(i+1)(i-1)2*1+1, i=2,3,4,(k+1) 所以i|(k+1)！+i 即(k+1)！+i為合數(shù) 所以此k個(gè)連續(xù)正整數(shù)都是合數(shù)。6證明：因?yàn)?911/214 ,小于14的素?cái)?shù)有2，3，5，7，11，13 經(jīng)驗(yàn)算都不能整除191 所以191為素?cái)?shù)。 因?yàn)?471/224 ,小于24的素?cái)?shù)有2，3，5，7，11，13，17，19，23 經(jīng)驗(yàn)算都不能整除547 所以547為素?cái)?shù)。 由737=11*67 ,747=3*249 知737與747都為合數(shù)。8解：存在。eg：a=6,b=2,c=910證明：p1 p2 p3|n， 則n= p1 p2 p3k，kn+ 又

4、p1 p2 p3，所以n= p1 p2 p3kp13 即p13n1/3 p1為素?cái)?shù) 則p12，又p1 p2 p3，所以n= p1 p2 p3k2 p2 p32p22 即p2(n/2)1/2 得證。11解：小于等于5001/2的所有素?cái)?shù)為2，3，5，7，11，13，17，19，依次刪除這些素?cái)?shù)的倍數(shù)可得所求素?cái)?shù)：12證明：反證法 假設(shè)3k+1沒(méi)有相同形式的素因數(shù)，則它一定只能表示成若干形如3k-1的素?cái)?shù)相乘。 (3 k1+1)(3 k2+1)=( 3 k1+1) k2+ k1*3+1 顯然若干個(gè)3k+1的素?cái)?shù)相乘，得到的還是3k+1的形式，不能得出3k-1的數(shù)，因此假設(shè)不成立，結(jié)論得證。 同理可

5、證其他。13證明：反證法 假設(shè)形如4k+3的素?cái)?shù)只有有限個(gè)，記為p1, p2, pn 因?yàn)?k+3=4k-1=4k-1 構(gòu)造n=4*p1*p2*pn-13*p1*p2*pn 所以npi (i=1,2,n) n為4k-1形式的素?cái)?shù)，即為4k+3的形式，所以假設(shè)不成立。原結(jié)論正確，形如4k+3的素?cái)?shù)有無(wú)窮多個(gè)。28（1）解：85=1*55+30 55=1*30+25 30=1*25+5 25=5*5 所以(55,85)=5（2）解：282=1*202+80 202=2*80+42 80=1*42+38 42=1*38+4 38=9*4+2 4=2*2 所以（202,282）=229（1）解：2t+

6、1=1*(2t-1)+2 2t-1=(t-1)*2+1 2=2*1 所以（2t+1,2t-1）=1 （2）解：2(n+1)=1*2n+2 2n=n*2 所以（2n,2(n+1)）=232（1）解：1=3-1*2 =3-1*(38-12*3) =-38+13*(41-1*38) =13*41-14*(161-3*41) =-14*161+55*(363-2*161) =55*363+(-124)*(1613-4*363) =(-124)*1613+551*(3589-2*1613) =551*3589+(-1226)*1613 所以s=-1226 t=551 （2）解：1=4-1*3 =4-1*

7、(115-28*4) =-115+29*(119-1*115) =29*119+(-30)*(353-2*119) =-30*353+89*(472-1*353) =89*472+(-119)*(825-1*472) =(-119)*825+208*(2947-3*825) =208*2947+(-743)*(3772-1*2947) =951*2947+(-743)*3772 所以s=951 t=-74336證明：因?yàn)椋╝，4）=2 所以a=2*(2m+1) mz 所以a+b=4m+2+4n+2=4(m+n)+4=4(m+n+1) 即4|a+b 所以（a+b,4）=437證明：反證法 假設(shè)n

8、為素?cái)?shù)，則n| a2- b2=(a+b)(a-b) 由1.4定理2知n|a+b或n|a-b,與已知條件矛盾 所以假設(shè)不成立，原結(jié)論正確，n為合數(shù)。40證明：（1）假設(shè)是21/2有理數(shù)，則存在正整數(shù)p，q，使得21/2=p/q,且（p, q）=1 平方得：p2=2q2, 即2|p2，所以p=2m, mn 因此p2=4m2=2q2 q2=2m2 q=2n, nn 則（p, q）=(2m,2n)=2(m, n)2與（p, q）=1矛盾 所以假設(shè)不成立，原結(jié)論正確，21/2不是有理數(shù)。 （2）假設(shè)是71/2有理數(shù)，則存在正整數(shù)m，n，使得71/2=p/q,且（m, n）=1 平方得：m2=2n2, 即

9、7|m2 將m表示成n個(gè)素?cái)?shù)pi的乘積，m= p1 p2 p3 pn ， pi為素?cái)?shù)。 因?yàn)?為素?cái)?shù)，假設(shè)7 !| m，則7 !p1 ，p2，p3 ，pn 所以m2= p12 p22 p32 pn 2=( p1 p2 p3 pn)( p1 p2 p3 pn) 所以7 !| m2，與7|m2矛盾，故7|m, m=7k 同理可知：7|n, n=7 k0 所以(m, n)=(7k,7 k0)=7(k, k0)7 與已知矛盾 故原結(jié)論正確，71/2不是有理數(shù)。（3）同理可證171/2不是有理數(shù)。41證明：假設(shè)log210是有理數(shù)，則存在正整數(shù)p, q,使得log210=p/q,且（p, q）=1 又l

10、og210=ln10/ln2=p/q ln10q=ln2p 10q=2p (2*5)q=2p 5q=2p-q 所以只有當(dāng)q=p=0是成立，所以假設(shè)不成立 故原結(jié)論正確，log210是無(wú)理數(shù)。 同理可證log37，log1521都是無(wú)理數(shù)。50（1）解：因?yàn)?=23, 60=22*3*5 所以8,60=23*3*5=12051（4）解：(471179111011001,4111831111011000)= 4104707908301011000=1011000 471179111011001,4111831111011000= 4111471179111831111011001第二章同余1解：（

11、1）其中之一為9，19，11，21，13，23，15，25，17 （2）其中之一為0，10，20，30，40，50，60，70，80 （3）.（1）或（2）中的要求對(duì)模10不能實(shí)現(xiàn)。2證明：當(dāng)m2時(shí)，因?yàn)?m-1)2=m2-2m+1=m(m-2)+1 所以(m-1)21(mod m) 即1與(m-1)2在同一個(gè)剩余類中，故02,12,(m-1)2一定不是模m的完全剩余系。6解：212(mod7), 224(mod7), 231(mod7) 又20080509=6693503*3 所以220080509=(23)66935031(mod7) 故220080509是星期六。7證明：（i）因?yàn)閍i

12、bi (modm),1ik 所以ai=bi+kim 又a1+a2+ +ak=ai=(bi+kim)=bi+m*ki 所以有aibi (mod m) 即a1+a2+ +ak=b1+b2+ +bk (mod m) （ii）因?yàn)閍i bi (mod m),1ik 所以ai(mod m)=bi (mod m) 所以（a1a2ak）mod m(a1mod m)( a2mod m)(ak mod m)mod m (b1mod m)( b2mod m)(bk mod m)mod m （b1b2bk）mod m 所以 a1a2aka1a2ak(mod m)8證明：如果a2b2(mod p) 則a2= b2+k

13、p , kz 即kp=a2-b2=(a+b)(a-b) 所以p|(a+b)(a-b) 又p為素?cái)?shù)，根據(jù)1.4定理2知p|a+b或p|a-b 得證。9證明：如果a2b2(mod n) 則a2= b2+kn , kz 即kn=a2-b2=(a+b)(a-b) 所以n|(a+b)(a-b) 由n=pq知kpq=a2-b2=(a+b)(a-b)因?yàn)閚!|a-b, n!|a+b，所以p,q不能同時(shí)為a-b或a+b的素因數(shù)。不妨設(shè)p|a-b, q|a+b ,則q!|a-b, p!|a+b 即(q, a-b)=1,(p, a+b)=1因此(n, a-b)=(pq, a-b)=(p, a-b)=p1 (n,

14、a+b)=(pq, a+b)=(q, a+b)=q1故原命題成立。10證明：因?yàn)閍b (mod c) 則a=cq+b , qz 根據(jù)1.3定理3知(a, c)=(b, c)17解：（1）ak+ak-1+ +a0=1+8+4+3+5+8+1=30 因?yàn)?|30 ,9!|30 所以1843581能被3整除，不能被9整除。 （2）ak+ak-1+ +a0=1+8+4+2+3+4+0+8+1=31 因?yàn)?!|31 , 9!|31 所以184234081不能被3整除，也不能被9整除。（3）ak+ak-1+ +a0=8+9+3+7+7+5+2+7+4+4=56 因?yàn)?!|56 , 9!|56 所以8937

15、752744不能被3整除，也不能被9整除。（4）ak+ak-1+ +a0=4+1+5+3+7+6+8+9+1+2+2+4+6=58 因?yàn)?!|58 , 9!|58 所以4153768912246不能被3整除，也不能被9整除。20解：（89878*58965）mod9(89878mod9)*(58965mod9)mod9(4*6)mod9 6(mod9) 5299?56270(mod9) 又5299?56270(45+?)mod9?(mod9) 所以 ?=6 即未知數(shù)字為6。21解：（1）因?yàn)?75961*2753(36mod9)(17mod9)mod9 0(mod9) 241052063326

16、(mod9) 8(mod9) 所以等式875961*2753=2410520633不成立 （2）因?yàn)?4789*23567(29mod9)(23mod9)mod9 1(mod9) 34853236741(mod9) 5(mod9) 所以等式14789*23567=348532367不成立 （3）因?yàn)?4789*43717(30mod9)(22mod9)mod9 3(mod9) 109270071330(mod9) 3(mod9) 所以等式24789*43717=1092700713可能成立 （4）這種判斷對(duì)于判斷等式不成立時(shí)簡(jiǎn)單明了，但對(duì)于判斷等式成立時(shí)，可能會(huì)較復(fù)雜。22解：因?yàn)?為素?cái)?shù)，由

17、wilso定理知：(7-1)! -1(mod7) 即6！-1（mod7） 所以8*9*10*11*12*131*2*3*4*5*6(mod7) 6!(mod7) -1(mod7)31證明：因?yàn)閏1,c2,c(m)是模m的簡(jiǎn)化剩余系 對(duì)于任一ci，有m-ci也屬于模m的簡(jiǎn)化剩余系 所以ci+(m-ci)0(modm) 因此c1+c2+c(m)0(modm)32證明：因?yàn)閍(m)1(modm) 所以a(m)-10(modm) a(m)-1=(a-1)(1+a+ a2+ a(m)-1) 0(modm) 又（a-1,m）=1 所以1+a+ a2+ a(m)-1 0(modm)33證明：因?yàn)?為素?cái)?shù)，由

18、fermat定理知a7 a(mod7) 又（a，3）=1 所以(a,9)=1 由euler定理知a(9)a61(mod9) 即a7a(mod9) 又(7,9)=1, 所以a7a(mod7*9) 即a7a(mod63)34證明：因?yàn)?2760=23*32*5*7*13 又(a,32760)=1 所以(a,2)=(a,3)=(a,5)=(a,7)=(a,13)=1 有：a(13)1(mod13) 即a121(mod13) a(8)a41(mod8) 即a121(mod8) a(5)a41(mod5) 即a121(mod5) a(7)a61(mod7) 即a121(mod7) a(9)a61(mod

19、9) 即a121(mod9) 又因?yàn)?,7,8,9,13=32760 所以a121(mod32760)35證明：因?yàn)?p,q)=1 p,q都為素?cái)?shù) 所以(p)=p-1, (q)=q-1 由euler定理知：p(q)1(modq) q(p)1(modp) 即pq-11(modq) qp-11(modp) 又 qp-10(modq) pq-10(modp) 所以pq-1+qp-11(modq) qp-1+pq-11(modp) 又p,q=pq 所以pq-1+qp-11(modpq)36證明：因?yàn)?m,n)=1 由euler定理知：m(n)1(modn) n(m)1(modm) 所以m(n)+n(m

20、)(m(n)modn)+ (n(m)modn)1+01(modn) 同理有：m(n)+n(m) 1(modm) 又m,n=mn 所以m(n)+n(m) 1(modmn)第三章.同余式1（1）解：因?yàn)椋?，7）=1 | 2 故原同余式有解 又3x1（mod7） 所以 特解x05（mod7） 同余式3x2（mod7）的一個(gè)特解x02* x0=2*53（mod7） 所有解為：x3（mod7） （3）解：因?yàn)椋?7，21）=1 | 14 故原同余式有解 又17x1（mod21） 所以 特解x05（mod21） 同余式17x14（mod21）的一個(gè)特解x014* x0=14*57（mod21） 所有解為

21、：x7（mod21）2（1）解：因?yàn)椋?27，1012）=1 | 833 故原同余式有解 又127x1（mod1012） 所以 特解x0255（mod1012） 同余式127x833（mod1012）的一個(gè)特解x0833* x0=833*255907（mod1012） 所有解為：x907（mod1012）3見(jiàn)課本3.2例17（1）解：因?yàn)椋?，14）=1 由euler定理知，同余方程5x3（mod14）的解為： x5(14)-1*39（mod14） （2）解：因?yàn)椋?，15）=1 由euler定理知，同余方程4x7（mod15）的解為： x4(15)-1*713（mod15） （3）解：因?yàn)椋?/p>

22、3，16）=1 由euler定理知，同余方程3x5（mod16）的解為： x3(16)-1*57（mod16）11證明：由中國(guó)剩余定理知方程解為： xa1m1m1+ a2m2m2+ akmkmk（mod m） 因?yàn)閙i兩兩互素，又中國(guó)剩余定理知：mimi1（mod mi） 又mi=m/mi 所以（m，mi）1（mod mi） 所以mimi=mi(mi)（mod mi） 代入方程解為xa1 m1(m1)+ a2 m2(m2)+ ak mk(mk)(mod m) 得證。12（1）解：由方程組得：3x+3y2(mod7) 6x+6y4(mod7) x+y-4(mod7) x5(mod 7) y5 (

23、mod 7) （2）解：由方程組得：2x+6y2(mod7) 2x-y2(mod7) 6x+8y4(mod7) x-y-4(mod7) x6(mod 7) y3 (mod 7)13見(jiàn)課本3.2例414同課本3.2例3 21000000562（mod1309）15（1）解：等價(jià)同余式組為： 23x1（mod4） 23x1（mod5） 23x1（mod7） 所以 x3（mod4） x2（mod5） x4（mod7） 所以x3*35*3 + 2*28*2 + 4*20*667（mod140） （2）解：等價(jià)同余式組為： 17x1（mod4） 17x1（mod5） 17x1（mod7） 17x1（mo

24、d11） 所以 x1（mod4） x2（mod5） x-3（mod7） x7（mod11） 所以x1*385*1 + 2*308*2 + (-3)*220*5 + 7*140*7 557（mod1540）19解：3x14+4x13+2x11+x9+x6+x3+12x2+x0（mod7） 左邊=(x7-x)( 3x7+4x6+2x4+x2+3x+4)+ x6+2x5+2x2+15x2+5x 所以原同余式可化簡(jiǎn)為：x6+2x5+2x2+15x2+5x0（mod7） 直接驗(yàn)算得解為：x0（mod7） x6（mod7）20解：f(x) 4x3+7（mod243） 直接驗(yàn)算的同余式f（x）0(mod3)

25、有一解：x11（mod3） f(x1) 4*13*7=-1(mod3) f(x1)-1-1(mod3) 所以t1-f（x1）*( f(x1)-1(mod3)/311(mod 3) x2 x1+3 t14(mod 9) t2-f（x2）*( f(x1)-1(mod3)/322(mod 3) x3 x2+32 t222(mod 27) t3-f（x3）*( f(x1)-1(mod3)/330(mod 3) x4 x3+33 t322(mod 81) t5-f（x4）*( f(x1)-1(mod3)/342(mod 3) x5 x4+34 t4184(mod 243) 所以同余式f（x）0(mod2

26、43)的解為：x5 184(mod 243)第四章二次同余式與平方剩余2解：對(duì)x=0,1,2,3,4,5,6時(shí)，分別求出y x=0,y21(mod7),y1,6(mod7) x=4,y24(mod7),y2,5(mod7) 當(dāng)x=1,2,3,5,6時(shí)均無(wú)解5解：對(duì)x=0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16時(shí)，分別求出y x=0,y21(mod17),y1,16(mod17) x=1,y23(mod17),無(wú)解 x=2,y211(mod17),無(wú)解 x=3,y214(mod17),無(wú)解 x=4,y21(mod17),y1,16(mod17) x=5,y2

27、12(mod17),無(wú)解 x=6,y22(mod17),y6,11(mod17) x=7,y211(mod17),無(wú)解 x=8,y211(mod17),無(wú)解 x=9,y28(mod17),y5,12(mod17) x=10,y28(mod17),y5,12(mod17) x=11,y20(mod17),y0(mod17) x=12,y27(mod17),無(wú)解 x=13,y21(mod17),y1,16(mod17) x=14,y25(mod17),無(wú)解 x=15,y28(mod17),y5,12(mod17) x=16,y216(mod17),y4,13(mod17)10解：(1）.（17/3

28、7）=(-1) (17-1)(37-1)/(2*2)*(37/17)=-1 (4）.（911/2003）=(-1) (2003-1)(911-1)/(2*2)*(2003/911)=1/3=1 (6）.（7/20040803）=(-1) (7-1)(20040803-1)/(2*2)*(20040803/7)=112解：（1）.因?yàn)椋?2/67）=(65/67)=1 所以-2是67的平方剩余 所以x2-2(mod67)有2個(gè)解。 （4）.因?yàn)椋?/37）=(-1) (37*37-1)/8=-1 所以2是37的平方非剩余 所以x22(mod37)無(wú)解。14證明：（1）因?yàn)閜為其素?cái)?shù)，模p的所有二

29、次剩余個(gè)數(shù)為(p-1)/2個(gè)，設(shè)為a1, a2, a3, a(p-1)/2 則a1*a2*a3a(p-1)/212*22*32(p-1)/2)2(mod p)1*2*3(p-1)/2)*(-(p-1)*(-(p-2)*(-(p-(p-1)/2)(mod p)1*2*3(p-1)/2)*(p-(p-1)/2)*(p-2)*(p-1)(-1)(p-1)/2(mod p)(p-1)!*(-1)(p-1)/2(mod p)(-1)*(-1)(p-1)/2(mod p) （2.4定理3）(-1)(p+1)/2(mod p)所以模p的所有二次剩余乘積模p的剩余為(-1)(p+1)/2得證。 （2）1，2，

30、3,p-1為p的一個(gè)完全剩余系1*2*2*(p-1)-1(mod p) (-1)(p+1)/2(-1)(p-1)/2(mod p)因?yàn)槟的所有二次剩余乘積模p的剩余為(-1)(p+1)/2所以模p的所有非二次剩余乘積模p的剩余為(-1)(p1)/2（3）當(dāng)p=3時(shí)，其二次剩余只有1，所以p=3時(shí)，模p的所有二次剩余之和模p 的剩余為1 當(dāng)p3時(shí)，由（1）得a1+a2+a3+a(p-1)/2p(p-1)(p+1)/24(mod p) 因?yàn)閜為奇素?cái)?shù)，所以p只能取3k-1或3k+1形式，代入上式得0 所以當(dāng)p3時(shí)，模p的所有二次剩余之和模p的剩余為0。（4）因?yàn)槟的所有二次非剩余之和與所有二次

31、剩余之和的和可以被p整除 所以由(3)得，當(dāng)p=3時(shí)，模p的所有二次非剩余之和模p的剩余為-1;當(dāng)p3時(shí)，模p的所有二次非剩余之和模p的剩余為0。16解：(1）.因?yàn)椋?/227）=(-1) (227-1)(7-1)/(2*2)*(227/7)= 1 所以7是227的二次剩余 所以x27(mod227)有解 (3）.因?yàn)?1對(duì)91的逆元是58 所以原同余方程等價(jià)于x216(mod91) 又16是91的平方剩余 所以11x2-6(mod91)有解21證明：應(yīng)用模重復(fù)平方法 11=20+21+23 令x=23,b=2,a=1 (1)x0=1 a0=a*b2(mod23) b1=b24(mod23)

32、 (2)x1=1 a1=a0*b18(mod23) b2=b1216(mod23) (3)x2=0 a2=a1*b208(mod23) b3=b223(mod23) (4)x3=1 a3=a2*b31(mod23) 所以2111(mod23) 即23|211-1 47|223-1與503|2251-1 應(yīng)用同樣的方法得證。第五章原根與指標(biāo)1解：因?yàn)?13)=12,所以只需對(duì)12的因數(shù)d=1,2,3,4,6,12,計(jì)算ad(mod12) 因?yàn)?12, 224, 238, 243, 26-1, 2121(mod13) 所以2模13的指數(shù)為12； 同理可得：5模13的指數(shù)為4，10模13的指數(shù)為6。

33、2解：因?yàn)?19)=18,所以只需對(duì)18的因數(shù)d=1,2,3,6,9,18計(jì)算ad(mod12) 因?yàn)?13, 329, 338, 367, 39-1, 2181(mod13) 所以3模19的指數(shù)為18； 同理可得：7模19的指數(shù)為3，10模19的指數(shù)為18。3解：因?yàn)?m)=(81)=54=2*33,所以(m)的素因數(shù)為q1=2,q2=3,進(jìn)而 (m)/q1=27, (m)/q2=18 這樣，只需驗(yàn)證：g27,g18模m是否同余于1。對(duì)2，4，5，6逐個(gè)驗(yàn)算： 因?yàn)?271(mod81) 2181(mod81) 根據(jù)5.2定理8得 所以2是模81的原根7證明：因?yàn)椋╝, m）=1, 故由or

34、dm(a)=st知：ast1(mod m) 即(as)t1(mod m) 不妨令ordm(as)=r 則asr1(mod m) 所以st|sr由(as)t1(mod m)得r|t 即tk*r kn1 rt 所以srst所以sr=st 所以r=t所以ordm(as)=t8解：存在 舉例：如n=7,d=3 因?yàn)?7)=6 d=3|6 存在a=2 (2,7)=1, 2(7)1(mod 7) 又231(mod 7) 所以ord7(2)=3 滿足條件。10證明：因?yàn)閜為一個(gè)奇素?cái)?shù)，p-1/2也是一個(gè)奇素?cái)?shù) 所以(p)=p-1=2*(p-1)/2 即(p)的不同素因數(shù)為2，p-1/2 又因?yàn)閍(p)/2=

35、ap-1/21(mod p) a(p)/(p-1)/2=a21(mod p) 根據(jù)5.2定理8得a是模p的原根。15證明：反證法 假設(shè)n是一個(gè)合數(shù)，令ordn(a)=m 則am1(mod n) 因?yàn)閍n-11(mod n) 所以由5.1定理1得m|n-1 即n-1=k*m 對(duì)n-1的所有素因數(shù)q，必可找到一個(gè)q1使m|(n-1)/q1) 所以an-1/q=am*t1(mod n) 與已知條件矛盾，故假設(shè)不成立，原結(jié)論得證。16解：因?yàn)閐=(n,(m)=(22,(41)=(22,40)=2 ind5=22 所以(n,(m)|ind5，同余式有解 等價(jià)同余式為22indxind5(mod40) 即

36、11indx11(mod20) 解得：indx=1,21(mod40) 所以原同余式解為x=6,35(mod41)17解：因?yàn)閐=(n,(m)=(22,(41)=(22,40)=2 ind29=7 (2,7)=1 所以原同余式無(wú)解。 第六章素性檢驗(yàn)1證明：因?yàn)?1=13*7是奇合數(shù)， (3,91)=1 又36=7291(mod91) 則391-1=390(36)151(mod91) 則91是對(duì)于基3的擬素?cái)?shù)。2證明：因?yàn)?5=5*3*3是奇合數(shù)， (17,45)=1 由euler定理：1741(mod5) 1721(mod3) 所以1741(mod3) 所以1741(mod45) 則1745-

37、1=1744(174)111(mod45) 則45是對(duì)于基17的擬素?cái)?shù)。 同理45是對(duì)于基19的擬素?cái)?shù)。10證明：25=5*5是奇素?cái)?shù) 設(shè)n=25 n-1=24=23*3 則t=3 (7,25)=1 7318(mod25) 72*3-1(mod25) 所以25是基于7的強(qiáng)擬素?cái)?shù)。15證明：n=561=3*11*17 為奇素?cái)?shù) （561,2）=1 b(n-1)/22(561-1)/222801(mod561) (b/n)=(2/561)=(-1)(561*561-1)/8=1 所以2280(2/561)(mod561) 所以561是對(duì)于基2的euler擬素?cái)?shù)。第八章群2. 證明：群是交換群的充要條件是對(duì)任意，有。證明：必要性：若是交換群，則對(duì)任意，有，從而。充分性：若對(duì)任意，有。那么。因此群是交換群。4. 設(shè)是階有限群。證明：對(duì)任意元，有。證明：任取，考慮生成的循環(huán)群。不妨設(shè)。根據(jù)拉格朗日