信息安全数学基础习题答案(陈恭亮版)

信息安全数学基础习题答案(陈恭亮版) ,1．证明：因为2|n 所以n=2k , kZ 5|n 所以5|2k ， 又（5，2）=1，所以5|k 即k=5 k, ，kZ 11 7|n 所以7|2*5 k, ,又（7，10）=1，所以7| k 即k=7 k，kZ 11122 所以n=2*5*7 k, 即n=70 k, kZ 222 因此70|n 32．证明：因为a-a=(a-1)a(a+1) 3 当a=3k，k,Z 3|a 则3|a-a 3 当a=3k-1，k,Z 3|a+1 则3|a-a 3 当a=3k+1，k,Z 3|a-1 则3|a-a 3 所以a-a能被3整除。 3．证明：任意奇整数可 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示为2 k,+1， kZ 0022 （2 k+1）＝4 k+4 k+1=4 k (k+1)+1 00000 由于k与k+1为两连续整数，必有一个为偶数，所以k (k+1)=2k 00002 所以（2 k+1）=8k+1 得证。 034．证明：设三个连续整数为a-1,a,a+1 则(a-1)a(a+1)= a-a 3 由第二题结论3|（a-a） 即3|(a-1)a(a+1) 又三个连续整数中必有至少一个为偶数，则2|(a-1)a(a+1) 又（3，2）=1 所以6|(a-1)a(a+1) 得证。 5．证明：构造下列k个连续正整数列： (k+1)！+2, (k+1)！+3, (k+1)！+4,……, (k+1)！+(k+1), k,Z 对数列中任一数 (k+1)！+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为合数 所以此k个连续正整数都是合数。 1/26．证明：因为191＜14 ,小于14的素数有2，3，5，7，11，13 经验算都不能整除191 所以191为素数。 1/2 因为547＜24 ,小于24的素数有2，3，5，7，11，13，17，19，23 经验算都不能整除547 所以547为素数。 由737=11*67 ,747=3*249 知737与747都为合数。 8．解：存在。eg：a=6,b=2,c=9 +10．证明：p, p p|n， 则n= p p pk，kN 1231231/33 3 又p? p ?p，所以n= p p pk?p 即p?n 111231232 p为素数 则p?2，又p? p ?p，所以n= p p pk?2 p p?2p111223123231/2 即p?(n/2) 得证。 21/211．解：小于等于500的所有素数为2，3，5，7，11，13，17，19，依次删除这些素数的 倍数可得所求素数： 12．证明：反证法 假设3k+1没有相同形式的素因数，则它一定只能表示成若干形如3k-1的素数相 乘。 (3 k+1)(3 k+1)=[( 3 k+1) k+ k]*3+1 显然若干个3k+1的素数相乘，得12121 1 到的还是3k+1的形式，不能得出3k-1的数，因此假设不成立，结论得证。 同理可证其他。 13．证明：反证法 假设形如4k+3的素数只有有限个，记为p, p,…, p12n 因为4k+3=4k`-1=4k-1 构造N=4*p*p*…*p-1?3*p*p*…*p12n12n 所以N＞p (i=1,2,…,n) i N为4k-1形式的素数，即为4k+3的形式，所以假设不成立。 原结论正确，形如4k+3的素数有无穷多个。 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）=2 29．（1）解：2t+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)）=2 32．（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*(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) 2 =951*2947+(-743)*3772 所以s=951 t=-743 36．证明：因为（a，4）=2 所以a=2*(2m+1) m,Z 所以a+b=4m+2+4n+2=4(m+n)+4=4(m+n+1) 即4|a+b 所以（a+b,4）=4 37．证明：反证法 22 假设n为素数，则n| a- b=(a+b)(a-b) 由1.4定理2知n|a+b或n|a-b,与已知条件矛盾 所以假设不成立，原结论正确，n为合数。 1/21/240．证明：（1）假设是2有理数，则存在正整数p，q，使得2=p/q,且（p, q）=1 222 平方得：p,=2q, 即2|p，所以p=2m, mN 22222 因此p,=4m=2q q=2m q=2n, nN 则（p, q）=(2m,2n)=2(m, n)?2与（p, q）=1矛盾 1/2 所以假设不成立，原结论正确，2不是有理数。 1/21/2 （2）假设是7有理数，则存在正整数m，n，使得7=p/q,且（m, n）=1 222 平方得：m=2n, 即7|m 将m表示成n个素数p的乘积，m= p p p ……p， p为素数。 i123n i 因为7为素数，假设7 !| m，则7 !?｛p ，p，p ，……p｝ 123n2222 2 所以m= p p p ……p=( p p p ……p)( p p p ……p) 123n123n123n22 所以7 !| m，与7|m矛盾，故7|m, m=7k 同理可知：7|n, n=7 k 0 所以(m, n)=(7k,7 k)=7(k, k)?7 与已知矛盾 001/2 故原结论正确，7不是有理数。 1/2（3）同理可证17不是有理数。 41．证明：假设log10是有理数，则存在正整数p, q,使得log10=p/q,且（p, q）=1 22 又log10=ln10/ln2=p/q 2qpqp Ln10=ln2 10=2 qpqp-q (2*5)=2 5=2 所以只有当q=p=0是成立，所以假设不成立 故原结论正确，log10是无理数。2 同理可证log7，log21都是无理数。 3153250．（1）解：因为8=2, 60=2*3*5 3 所以[8,60]=2*3*5=120 1111100111111100000001000100051．（4）解：(4779101,4183101)= 41477983101=101 1111100111111100011111111111001 [4779101,4183101]= 41477983101 3 1．解：（1）其中之一为9，19，11，21，13，23，15，25，17 （2）其中之一为0，10，20，30，40，50，60，70，80 （3）.（1）或（2）中的要求对模10不能实现。 222．证明：当m>2时，因为(m-1)=m-2m+1=m(m-2)+1 2 所以(m-1)?1(mod m) 2222 即1与(m-1)在同一个剩余类中，故0,1,…,(m-1)一定不是模m的完全剩余系。 1236．解：2?2(mod7), 2?4(mod7), 2?1(mod7) 又20080509=6693503*3 200805093 所以2=(2)6693503?1(mod7) 20080509 故2是星期六。 7．证明：（i）因为a? b (modm),1?i?k 所以a=b+km iiiii 又a+a+… +a=?a=?(b+km)=?b+m*?k 12kiiiii 所以有?a??b (mod m) ii 即a+a+… +a=b+b+… +b (mod m) 12k12k （ii）因为a? b (mod m),1?i?k 所以a(mod m)=b (mod m) iiii 所以（aa…a）mod m?[(amod m)( amod m)…(amod m)]mod m 12k12k ?[(bmod m)( bmod m)…(bmod m)]mod m 12k ?（bb…b）mod m 12k 所以 aa…a?aa…a(mod m) 12k12k22228．证明：如果a,?b(mod p) 则a= b+kp , kZ 22 即kp=a-b=(a+b)(a-b) 所以p|(a+b)(a-b) 又p为素数，根据1.4定理2知p|a+b或p|a-b 得证。 22229．证明：如果a,?b(mod n) 则a= b+kn , kZ 22即kn=a-b=(a+b)(a-b) 所以n|(a+b)(a-b) 22由n=pq知kpq=a-b=(a+b)(a-b) 因为n!|a-b, n!|a+b，所以p,q不能同时为a-b或a+b的素因数。 不妨设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)=p>1 (n, a+b)=(pq, a+b)=(q, a+b)=q>1 故原命题成立。 10．证明：因为a?b (mod c) 则a=cq+b , q,Z 根据1.3定理3知(a, c)=(b, c) 17．解：（1）a+a+… +a=1+8+4+3+5+8+1=30 kk-10 因为3|30 ,9!|30 所以1843581能被3整除，不能被9整除。 （2）a+a+… +a=1+8+4+2+3+4+0+8+1=31 kk-10 因为3!|31 , 9!|31 所以184234081不能被3整除，也不能被9整除。 （3）a+a+… +a=8+9+3+7+7+5+2+7+4+4=56 kk-10 因为3!|56 , 9!|56 所以8937752744不能被3整除，也不能被9整除。 （4）a+a+… +a=4+1+5+3+7+6+8+9+1+2+2+4+6=58 kk-10 因为3!|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 即未知数字为6。 4 21．解：（1）因为875961*2753?[(36mod9)(17mod9)]mod9 ?0(mod9) 2410520633?26(mod9) ?8(mod9) 所以等式875961*2753=2410520633不成立 （2）因为14789*23567?[(29mod9)(23mod9)]mod9 ?1(mod9) 348532367?41(mod9) ?5(mod9) 所以等式14789*23567=348532367不成立 （3）因为24789*43717?[(30mod9)(22mod9)]mod9 ?3(mod9) 1092700713?30(mod9) ?3(mod9) 所以等式24789*43717=1092700713可能成立 （4）这种判断对于判断等式不成立时简单明了，但对于判断等式成立时，可能会较 复杂。 22．解：因为7为素数，由Wilso定理知：(7-1)! ?-1(mod7) 即6！?-1（mod7） 所以8*9*10*11*12*13?1*2*3*4*5*6(mod7) ?6!(mod7) ?-1(mod7) 31．证明：因为c ,c,…,c是模m的简化剩余系 12(m), 对于任一c，有m-c也属于模m的简化剩余系 ii 所以c+(m-c)?0(modm) ii 因此c+c+…+c?0(modm) 12(m),(m)(m),,32．证明：因为a?1(modm) 所以a-1?0(modm) (m)2(m)-1,, a-1=(a-1)(1+a+ a+…+ a) ?0(modm) 又（a-1,m）=1 2(m)-1, 所以1+a+ a+…+ a ?0(modm) 733．证明：因为7为素数，由Fermat定理知a ?a(mod7) (9)67, 又（a，3）=1 所以(a,9)=1 由Euler定理知a?a?1(mod9) 即a?a(mod9) 7 又(7,9)=1, 所以a?a(mod7*9) 7 即a?a(mod63) 3234．证明：因为32760=2*3*5*7*13 又(a,32760)=1 所以(a,2)=(a,3)=(a,5)=(a,7)=(a,13)=1 (13)12, 有：a?1(mod13) 即a?1(mod13) (8)412, a?a?1(mod8) 即a?1(mod8) (5)412, a?a?1(mod5) 即a?1(mod5) (7)612, a?a?1(mod7) 即a?1(mod7) (9)612, a?a?1(mod9) 即a?1(mod9) 又因为[5,7,8,9,13]=32760 12 所以a?1(mod32760) 35．证明：因为(p,q)=1 p,q都为素数 所以(p)=p-1, (q)=q-1 ,,(q)(p),, 由Euler定理知：p?1(modq) q?1(modp) q-1p-1 即p?1(modq) q?1(modp) p-1q-1 又 q?0(modq) p?0(modp) q-1p-1p-1q-1 所以p+q?1(modq) q+p?1(modp) q-1p-1 又[p,q]=pq 所以p+q?1(modpq) 36．证明：因为(m,n)=1 (n)(m),, 由Euler定理知：m?1(modn) n?1(modm) (n)(m)(n)(m),,,, 所以m+n?(mmodn)+ (nmodn)?1+0?1(modn) (n)(m),, 同理有：m+n ?1(modm) 5 (n)(m),, 又[m,n]=mn 所以m+n ?1(modmn) 1．（1）解：因为（3，7）=1 | 2 故原同余式有解 又3x?1（mod7） 所以 特解x`?5（mod7） 0 ` 同余式3x?2（mod7）的一个特解x?2* x=2*5?3（mod7） 00 所有解为：x?3（mod7） （3）解：因为（17，21）=1 | 14 故原同余式有解 ` 又17x?1（mod21） 所以 特解x?5（mod21） 0 ` 同余式17x?14（mod21）的一个特解x?14* x=14*5?7（mod21） 00 所有解为：x?7（mod21） 2．（1）解：因为（127，1012）=1 | 833 故原同余式有解 ` 又127x?1（mod1012） 所以 特解x?255（mod1012） 0 ` 同余式127x?833（mod1012）的一个特解x?833* x=833*255?907（mod1012） 00 所有解为：x?907（mod1012） 3．见课本3.2例1 7．（1）解：因为（5，14）=1 由Euler定理知，同余方程5x?3（mod14）的解为： (14)-1, x?5*3?9（mod14） （2）解：因为（4，15）=1 由Euler定理知，同余方程4x?7（mod15）的解为： (15)-1, x?4*7?13（mod15） （3）解：因为（3，16）=1 由Euler定理知，同余方程3x?5（mod16）的解为： (16)-1, x?3*5?7（mod16） 11．证明：由中国剩余定理知方程解为： x?aMM`+ aMM`+……+ aMM`（mod m） 111222kkk 因为m两两互素，又中国剩余定理知：MM`?1（mod m） iiii 又M=m/m 所以（m，M）?1（mod m） iiii(mi), 所以MM`=M?（mod m） iiii(m1)(m2)(mk),,, 代入方程解为x?a M+ a M+……+ a M(mod m) 得证。 1122kk12．（1）解：由方程组得：3x+3y?2(mod7) 6x+6y?4(mod7) x+y?-4(mod7) X?5(mod 7) y?5 (mod 7) （2）解：由方程组得：2x+6y?2(mod7) 2x-y?2(mod7) 6x+8y?4(mod7) x-y?-4(mod7) X?6(mod 7) y?3 (mod 7) 13．见课本3.2例4 14．同课本3.2例3 21000000?562（mod1309） 15．（1）解：等价同余式组为： 23x?1（mod4） 6 23x?1（mod5） 23x?1（mod7） 所以 x?3（mod4） x?2（mod5） x?4（mod7） 所以x?3*35*3 + 2*28*2 + 4*20*6?67（mod140） （2）解：等价同余式组为： 17x?1（mod4） 17x?1（mod5） 17x?1（mod7） 17x?1（mod11） 所以 x?1（mod4） x?2（mod5） x?-3（mod7） x?7（mod11） 所以x?1*385*1 + 2*308*2 + (-3)*220*5 + 7*140*7 ?557（mod1540） 141311963219．解：3x+4x+2x+x+x+x+12x+x?0（mod7） 776426522 左边=(x-x)( 3x+4x+2x+x+3x+4)+ x+2x+2x+15x+5x 6522 所以原同余式可化简为：x+2x+2x+15x+5x?0（mod7） 直接验算得解为：x?0（mod7） x?6（mod7） 320．解：f`(x) ? 4x+7（mod243） 直接验算的同余式f（x）?0(mod3)有一解：x?1（mod3） 13-1 f`(x) ?4*1*7=-1(mod3) f`(x)?-1(mod3) 11-11 所以t?-f（x）*( f`(x)(mod3))/3?1(mod 3) 111 x? x+3 t?4(mod 9) 211-12 t?-f（x）*( f`(x)(mod3))/3?2(mod 3) 2212 x? x+3 t?22(mod 27) 322-13 t?-f（x）*( f`(x)(mod3))/3?0(mod 3) 3313 x? x+3 t?22(mod 81) 433-14 t?-f（x）*( f`(x)(mod3))/3?2(mod 3) 5414 x? x+3 t?184(mod 243) 544 所以同余式f（x）?0(mod243)的解为：x ?184(mod 243) 5 2．解：对x=0,1,2,3,4,5,6时，分别求出y x=0,y2?1(mod7),y?1,6(mod7) 2 x=4,y?4(mod7),y?2,5(mod7) 当x=1,2,3,5,6时均无解 5．解：对x=0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16时，分别求出y 2 x=0,y?1(mod17),y?1,16(mod17) 2 x=1,y?3(mod17),无解 2 x=2,y?11(mod17),无解 2 x=3,y?14(mod17),无解 2 x=4,y?1(mod17),y?1,16(mod17) 2 x=5,y?12(mod17),无解 2 x=6,y?2(mod17),y?6,11(mod17) 7 2 x=7,y?11(mod17),无解 2 x=8,y?11(mod17),无解 2 x=9,y?8(mod17),y?5,12(mod17) 2 x=10,y?8(mod17),y?5,12(mod17) 2 x=11,y?0(mod17),y?0(mod17) 2 x=12,y?7(mod17),无解 2 x=13,y?1(mod17),y?1,16(mod17) 2 x=14,y?5(mod17),无解 2 x=15,y?8(mod17),y?5,12(mod17) 2 x=16,y?16(mod17),y?4,13(mod17) (17-1)(37-1)/(2*2)10．解：(1）.（17/37）=(-1)*(37/17)=-1 (2003-1)(911-1)/(2*2) (4）.（911/2003）=(-1)*(2003/911)=1/3=1 (7-1)(20040803-1)/(2*2) (6）.（7/20040803）=(-1)*(20040803/7)=1 12．解：（1）.因为（-2/67）=(65/67)=1 所以-2是67的平方剩余 2 所以x?-2(mod67)有2个解。 (37*37-1)/8 （4）.因为（2/37）=(-1)=-1 所以2是37的平方非剩余 2 所以x?2(mod37)无解。 14．证明：（1）因为p为其素数，模p的所有二次剩余个数为(p-1)/2个， 设为a, a, a, …a 123(p-1)/22222则a*a*a…a?1*2*3…((p-1)/2)(mod p) 123(p-1)/2 ?1*2*3…((p-1)/2)*(-(p-1))*(-(p-2))*…(-(p-(p-1)/2))(mod p) (p-1)/2?1*2*3…((p-1)/2)*(p-(p-1)/2)…*(p-2)*(p-1)(-1)(mod p) (p-1)/2?(p-1)!*(-1)(mod p) (p-1)/2?(-1)*(-1)(mod p) （2.4定理3） (p+1)/2?(-1)(mod p) (p+1)/2所以模p的所有二次剩余乘积模p的剩余为(-1)得证。 （2）1，2，3,…p-1为p的一个完全剩余系 (p+1)/2(p-1)/21*2*2…*(p-1)?-1(mod p) ?(-1)(-1)(mod p) (p+1)/2因为模p的所有二次剩余乘积模p的剩余为(-1) (p－1)/2所以模p的所有非二次剩余乘积模p的剩余为(-1) （3）当p=3时，其二次剩余只有1，所以p=3时，模p的所有二次剩余之和模p 的剩余为1 当p>3时，由（1）得a+a+a…+a?p(p-1)(p+1)/24(mod p) 123(p-1)/2 因为p为奇素数，所以p只能取3k-1或3k+1形式，代入上式得0 所以当p>3时，模p的所有二次剩余之和模p的剩余为0。 （4）因为模p的所有二次非剩余之和与所有二次剩余之和的和可以被p整除 所以由(3)得，当p=3时，模p的所有二次非剩余之和模p的剩余为-1; 当p>3时，模p的所有二次非剩余之和模p的剩余为0。 (227-1)(7-1)/(2*2)16．解：(1）.因为（7/227）=(-1)*(227/7)= 1 所以7是227的二次剩余 2 所以x?7(mod227)有解 (3）.因为11对91的逆元是58 8 2 所以原同余方程等价于x?16(mod91) 又16是91的平方剩余 2 所以11x?-6(mod91)有解 21．证明：应用模重复平方法 013 11=2+2+2 令x=23,b=2,a=1 2 (1)x=1 a=a*b?2(mod23) b=b?4(mod23) 0012 (2)x=1 a=a*b?8(mod23) b=b?16(mod23) 11012102 (3)x=0 a=a*b?8(mod23) b=b?3(mod23) 221232 (4)x=1 a=a*b?1(mod23) 33231111 所以2?1(mod23) 即23|2-1 23251 47|2-1与503|2-1 应用同样的方法得证。 1．解：因为d(13)=12,所以只需对12的因数d=1,2,3,4,6,12,计算a(mod12) , 1234612 因为2?2, 2?4, 2?8, 2?3, 2?-1, 2?1(mod13) 所以2模13的指数为12； 同理可得：5模13的指数为4，10模13的指数为6。 d2．解：因为(19)=18,所以只需对18的因数d=1,2,3,6,9,18计算a(mod12) , 1236918 因为3?3, 3?9, 3?8, 3?7, 3?-1, 2?1(mod13) 所以3模19的指数为18； 同理可得：7模19的指数为3，10模19的指数为18。 33．解：因为(m)=(81)=54=2*3,所以(m)的素因数为q=2,q=3,进而 ,,,12 (m)/q=27, (m)/q=18 ,,12 2718 这样，只需验证：g,g模m是否同余于1。对2，4，5，6…逐个验算： 2718 因为2,,1(mod81) 21(mod81) 根据5.2定理8得 所以2是模81的原根 stst7．证明：因为（a, m）=1, 故由ord(a)=st知：a?1(mod m) 即(a)?1(mod m) mssr 不妨令ord(a)=r 则a?1(mod m) 所以st|sr mst由(a,)?1(mod m)得r|t 即t＝k*r kN?1 r?t 所以sr?st 所以sr=st 所以r=t s所以ord(a)=t m 8．解：存在 举例：如n=7,d=3 因为(7)=6 d=3|6 ,(7)3, 存在a=2 (2,7)=1, 2?1(mod 7) 又2?1(mod 7) 所以ord(2)=3 满足条件。 7 10．证明：因为p为一个奇素数，p-1/2也是一个奇素数 所以(p)=p-1=2*(p-1)/2 即(p)的不同素因数为2，p-1/2 ,,(p)/2p-1/2(p)/[(p-1)/2]2,, 又因为a,,=a1(mod p) a=a1(mod p) 根据5.2定理8得a是模p的原根。 9 15．证明：反证法 m 假设n是一个合数，令ord(a)=m 则a?1(mod n) nn-1 因为a?1(mod n) 所以由5.1定理1得m|n-1 即n-1=k*m 对n-1的所有素因数q，必可找到一个q使m|((n-1)/q) 11n-1/qm*t 所以a=a?1(mod n) 与已知条件矛盾，故假设不成立，原结论得证。 16．解：因为d=(n,(m))=(22,(41))=(22,40)=2 ind5=22 ,, 所以(n,(m))|ind5，同余式有解 , 等价同余式为22indx?ind5(mod40) 即11indx?11(mod20) 解得：indx=1,21(mod40) 所以原同余式解为x=6,35(mod41) 17．解：因为d=(n,(m))=(22,(41))=(22,40)=2 ind29=7 ,, (2,7)=1 所以原同余式无解。 1．证明：因为91=13*7是奇合数， (3,91)=1 又3691-190615=729?1(mod91) 则3=3?(3)?1(mod91) 则91是对于基3的拟素数。 2．证明：因为45=5*3*3是奇合数， (17,45)=1 42 由Euler定理：17?1(mod5) 17?1(mod3) 44 所以17?1(mod3) 所以17?1(mod45) 45-144411 则17=17?(17)?1(mod45) 则45是对于基17的拟素数。 同理45是对于基19的拟素数。 310．证明：25=5*5是奇素数 设n=25 n-1=24=2*3 则t=3 (7,25)=1 32*3 7?18(mod25) 7?-1(mod25) 所以25是基于7的强拟素数。 15．证明：n=561=3*11*17 为奇素数 （561,2）=1 (n-1)/2(561-1)/2280 b?2?2?1(mod561) (561*561-1)/8 (b/n)=(2/561)=(-1)=1 280 所以2?(2/561)(mod561) 所以561是对于基2的Euler拟素数。 10 222()abab,2. 证明：群是交换群的充要条件是对任意，有。 abG,,G 证明：必要性：若是交换群，则对任意，有，从而 abG,,Gabba,, 222()abababaabbab,,,。 222()abab,充分性：若对任意，有。那么 abG,,, ,,,,1211221baebaeaabbaabbeabeab,,,,,()。 因此群是交换群。 G n4. 设n是阶有限群。证明：对任意元，有ae,。 GaG, 证明：任取a，考虑生成的循环群。不妨设aq,。根据拉格朗日定理，有qn|，aaG, nqkkq从而存在正整数aaee,,,()，使得nqk,。因为（否则aq,），所以。 ae,k 6. 设centGaGbGabba(){|()},,,,,centG()是一个群。记。证明：是的正规GG 子群。 证明：首先证明aacentG,(),centG()是的子群。任取，。计算 GbG,12 ,,,,,,,,,,,,,1111111111111baaabaabaaababaaabaab,,,,,,()()()()。 12121212121212 ,1因此，aacentG,()centG()，从而是的子群。 G12 ,1再证明aGxaGa,,, cent() centG()是的正规子群。任取。那么存在G ,1,,11xaya,xayaaayeyyG,,,,,cent()yG,cent()，使得。由的交换性，有。y ,1从而aGaG cent() cent(),centG()，是的正规子群。 G ,17. 设a是群的一个元素。证明：映射,:xaxa,是到自身的自同构。 GG证明：（1）任取xyG,,。计算 ,,,,1111,,,()()()()xyaxyaaxeyaaxaayaxy,,,, 11 ,因此是同态映射。 ,,11（2）若axaaya,，且。那么，从而 xyG,,,,()()xy, ,,,,1111xaaxaaaayaay,,,， 因此,是单射。 ,,,111（3）任取,,()()acaaacaaecec,,,。由于，故是满射。 cG, ,1综上所述，映射是到自身的自同构。 ,:xaxa,G ,18. 设是群的子群。在中定义关系。证明： RaRbbaH:,,HGG （i）是等价关系。 R （ii）的充要条件是。 aRbaHbH, ,1证明：（i）任取。既然是群的子群，那么。因此，这说明，aaeH,,HaG,GeH,aRa 即满足自反性。 R ,1取满足。那么。根据是群的子群以及逆元的性质，我们有abG,,baH,HaRbG,,,111abbaH,,()，这说明，即满足对称性。 RbRa ,1,1取abcG,,,满足，。那么，。根据是群的子群，baH,cbH,HaRbbRcG ,,,111我们有cacbbaH,,()()。 从而成立，即满足传递性。 RaRc 综上所述是等价关系。 R ,1（ii）即要证明：。 baHaHbH,,, 充分性：设，则，于是存在使得，左右aHbH,aaeaHbH,,,hH,abh,, ,1,,11两边同乘，得。 bbabbhhH,,, ,1hH,cah,必要性：如果。对任意，存在使得。进而， baH,caH,,22 ,1cbbahbhhbH,,,()， 212 因此，。 aHbH, ,,,111 同样，对任意cabahahhaH,,,()hH,cbh,，存在使得，进而。cbH,31233因此，故。 bHaH,aHbH, 12 2007 3a1 证明：如果是整数，则能被3整除。 aa, 2 用广义欧几里德算法求最大公因子 (4655,12075) m3 设是一个正整数，，如果，证明：。 abm,(mod)dm|abd,(mod) 4 解方程 987610(mod2668)x, x,2(mod3),,x,1(mod5)5 解方程组 , ,x,1(mod7), 6 计算3模19的指数。 6,,7 计算的Legendre符号 ,,53,, 8 证明：91是对基3的拟素数。 ,,,,9 设f是群到的一个同态，，其中是的单位GGeGker|,()faaGfae,,,,,元。证明：kerf是的子群。 G ,1a10 设是群的一个元素。证明：映射是到自身的自同构。 ,:xaxa,GG 2007 31 证明：因为a-a=(a-1)a(a+1) 3, 当a=3k，kZ 3|a 则3|a-a 3, 当a=3k-1，kZ 3|a+1 则3|a-a 3, 当a=3k+1，kZ 3|a-1 则3|a-a 3 所以a-a能被3整除。 12075=2*4655+2765 4655=1*2765+1890 2765=1*1890+875 1890=2*875+140 875=6*140+35 140=4*35 (4655,12075)所以=35 13 ,3. 因为d|m，所以存在整数使得。又因为，所以存在整abm,(mod)m'mdm, ,数使得。该式又可以写成。故。 abdmk,，()abd,(mod)kabmk,， 4. 987610(mod2668)x, 计算最大公因式(987,2668)=1，所以原同余式有解且只有一个解。利用广义欧几 ,x,2495(mod2668)里德除法，求同余式的解为。再写出同余9871(mod2668)x,0 ,xx,,,610*610*24951190(mod2668)式的解为。 987610(mod2668)x,00 mmm,,,3,5,75 令， ，m,,3*5*7105123 MMM,,,,,,5*735,3*721,3*515。 123 ,MMm,1(mod)分别求解同余式（i=1,2,3） iii ,,,M,2M,1M,1得到，，。故同余式的解为 123 ,,,xMMMMMM,，，*2*1*1(mod105)112233 ,，，2*35*21*21*11*15*1(mod105) ,71(mod105) d6 解：因为(19)=18,所以只需对18的因数d=1,2,3,6,9,18计算a(mod12) , 1236918 因为3?3, 3?9, 3?8, 3?7, 3?-1, 2?1(mod13) 所以3模19的指数为18； 7 623,,,,,,,,,,,,,535353,,,,,, 253,,(531)/8(31)(531)/4,,, (1)(1) ,,,,,,3,, 22,,(31)/8,,,,,,,,,,111(1)1,,3,, 8 证明：因为91=13*7是奇合数， (3,91)=1 691-190615 又3=729?1(mod91) 则3=3?(3)?1(mod91) 则91是对于基3的拟素数。 9 对任意,,abf,ker,，有faefbe(),(),,，从而， ,,,,1111,fabfafbfafbfafae()()()()()()(),,,,。 14 ,1abf,ker因此，，是群的子群。 kerfG 10 证明：（1）任取。计算 xyG,, ,,,,1111,,,()()()()xyaxyaaxeyaaxaayaxy,,,, 因此,是同态映射。 ,,11（2）若axaaya,，且。那么，从而 xyG,,,,()()xy, ,,,,1111xaaxaaaayaay,,,， 因此,是单射。 ,,,111（3）任取,,()()acaaacaaecec,,,。由于，故是满射。 cG, ,1综上所述，映射是到自身的自同构。 ,:xaxa,G 15