信息安全数学基础课后答案(陈恭亮著)清华大学出版社.pdf

1 信息安全数学基础习题答案 第一章整数的可除性 1证明因为 2|n所以 n=2k , kZ 5| n所以 5| 2k 又52=1所以 5| k即 k=5 k1k1Z 7| n所以 7| 2* 5 k1, 又710=1所以 7| k1即 k1=7 k2k2Z 所以 n=2* 5* 7 k2即 n=70 k2,k2Z 因此 70| n 2证明因为 a3- a=( a- 1) a( a+1) 当 a=3kkZ3| a则 3| a3- a 当 a=3k- 1kZ3| a+1则 3| a3- a 当 a=3k+1kZ3| a- 1则 3| a3- a 所以 a3- a 能被 3 整除。 3证明任意奇整数可表示为 2 k0+1 k0Z 2 k0+124 k02+4 k0+1=4 k0( k0+1) +1 由于 k0与 k0+1 为两连续整数必有一个为偶数所以 k0( k0+1) =2k 所以2 k0+12=8k+1得证。 4证明设三个连续整数为 a- 1, a, a+1则( a- 1) a( a+1) = a3- a 由第二题结论 3| a3- a即 3| ( a- 1) a( a+1) 又三个连续整数中必有至少一个为偶数则 2| ( a- 1) a( a+1) 又32=1所以 6| ( a- 1) a( a+1)得证。 5证明构造下列 k 个连续正整数列 ( k+1) +2,( k+1) +3,( k+1) +4, ,( k+1) +( k+1) ,kZ 对数列中任一数 ( 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 个连续正整数都是合数。 6证明因为 1911/ 214, 小于 14 的素数有 23571113 经验算都不能整除 191所以 191 为素数。 因为 5471/ 224, 小于 24 的素数有 23571113171923 经验算都不能整除 547所以 547 为素数。 由 737=11* 67 , 747=3* 249 知 737 与 747 都为合数。 8解存在。ega=6, b=2, c=9 10证明p1p2p3|n 则 n= p1p2p3kkN+ 又 p1 p2p3所以 n= p1p2p3kp13即 p13n1/ 3 p1为素数则 p12又 p1 p2p3所以 n= p1p2p3k2 p2p32p22 即 p2( n/2)1/ 2得证。 11解小于等于 5001/ 2的所有素数为 235711131719依次删除这些素数 的倍数可得所求素数 12证明反证法 假设 3k+1 没有相同形式的素因数 则它一定只能表示成若干形如 3k- 1 的素数相 乘。 ( 3 k1+1) ( 3 k2+1) = (3 k1+1) k2+ k1 * 3+1显然若干个 3k+1 的素数相乘得 2 到的还是 3k+1 的形式不能得出 3k- 1 的数因此假设不成立结论得证。 同理可证其他。 13证明反证法 假设形如 4k+3 的素数只有有限个记为 p1, p2, ,pn 因为 4k+3=4k-1=4k-1构造 N=4*p1* p2* * pn-13*p1* p2* * pn 所以 Npi( i =1, 2, , n) 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=- 1226t =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) 3 =951* 2947+( - 743) * 3772 所以 s=951t =- 743 36证明因为a4=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=4 37证明反证法 假设 n 为素数则 n|a2-b2=( a+b) ( a- b) 由 1. 4 定理 2 知 n| a+b 或 n| a- b, 与已知条件矛盾 所以假设不成立原结论正确n 为合数。 40证明 1假设是 21/ 2有理数则存在正整数 pq使得 21/ 2=p/ q, 且p,q=1 平方得p2=2q2,即 2| p2所以 p=2m,mN 因此 p2=4m2=2q2q2=2m2q=2n,nN 则p,q=( 2m, 2n) =2( m,n) 2 与p,q=1 矛盾 所以假设不成立原结论正确21/ 2不是有理数。 2假设是 71/ 2有理数则存在正整数 mn使得 71/ 2=p/ q, 且m,n=1 平方得m2=2n2,即 7| m2 将 m 表示成 n 个素数 pi的乘积m= p1p2p3pnpi为素数。 因为 7 为素数假设 7 !| m则 7 ! p1p2p3pn 所以 m2= p12p22p32pn 2=( p1p2p3pn) ( p1p2p3pn) 所以 7 ! |m2与 7| m2矛盾故 7| m,m=7k 同理可知7| n,n=7 k0 所以( m,n) =( 7k, 7 k0) =7( k, k0) 7与已知矛盾 故原结论正确71/ 2不是有理数。 3同理可证 171/ 2不是有理数。 41证明假设 l og210 是有理数则存在正整数 p,q, 使得 l og210=p/ q, 且p,q=1 又 l og210=l n10/ l n2=p/ q Ln10q=l n2p10q=2p ( 2* 5) q=2p 5q=2p- q 所以只有当 q=p=0 是成立所以假设不成立 故原结论正确l og210 是无理数。 同理可证 l og37l og1521 都是无理数。 50 1解因为 8=23,60=2 2* 3* 5 所以 8, 60 =23* 3* 5=120 51 4解( 471179111011001, 4111831111011000) = 4104707908301011000=1011000 471179111011001, 4111831111011000 = 4111471179111831111011001 第二章同余 4 1解 1其中之一为 91911211323152517 2其中之一为 01020304050607080 3. 1或2中的要求对模 10 不能实现。 2证明当 m2 时因为( m- 1) 2=m2- 2m+1=m( m- 2) +1 所以( m- 1) 21( mod m) 即 1 与( m- 1) 2在同一个剩余类中 故02, 12, , ( m- 1)2一定不是模m的完全剩余系。 6解212( mod7) ,224( mod7) ,231( mod7) 又 20080509=6693503* 3 所以 220080509=( 23) 66935031( mod7) 故 220080509是星期六。 7证明 i 因为 ai bi( modm) , 1i k所以 ai=bi+kim 又 a1+a2+ +ak=ai=( bi+kim) =bi+m* ki 所以有aibi( mod m) 即 a1+a2+ +ak=b1+b2+ +bk( mod m) i i 因为 ai bi( mod m) , 1i k所以 ai( mod m) =bi( mod m) 所以a1a2akmod m ( a1mod m) ( a2mod m) ( akmod m) mod m ( b1mod m) ( b2mod m) ( bkmod m) mod m b1b2bkmod m 所以 a1a2aka1a2ak( mod m) 8证明如果 a2b2( mod p)则 a2= b2+kp,kZ 即 kp=a2- b2=( a+b) ( a- b)所以 p| ( a+b) ( a- b) 又 p 为素数根据 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) 因为 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) =p1 ( n,a+b) =( pq,a+b) =( q,a+b) =q1 故原命题成立。 10证明因为 ab ( mod c)则 a=cq+b ,qZ 根据 1. 3 定理 3 知( a,c) =( b,c) 17解 1ak+ak-1+ +a0=1+8+4+3+5+8+1=30 因为 3| 30 , 9! | 30所以 1843581 能被 3 整除不能被 9 整除。 2ak+ak-1+ +a0=1+8+4+2+3+4+0+8+1=31 因为 3! | 31 ,9! | 31所以 184234081 不能被 3 整除也不能被 9 整除。 3ak+ak-1+ +a0=8+9+3+7+7+5+2+7+4+4=56 因为 3! | 56 ,9! | 56所以 8937752744 不能被 3 整除也不能被 9 整除。 4ak+ak-1+ +a0=4+1+5+3+7+6+8+9+1+2+2+4+6=58 因为 3! | 58 ,9! | 58所以 4153768912246 不能被 3 整除也不能被 9 整除。 20解 89878* 58965mod9 ( 89878mod9) * ( 58965mod9) mod9( 4* 6) mod9 6( mod9)5299?56270( mod9) 又 5299?56270( 45+?) mod9?( mod9) 所以?=6即未知数字为 6。 5 21解 1因为 875961* 2753 ( 36mod9) ( 17mod9) mod9 0( mod9) 241052063326( mod9) 8( mod9) 所以等式 875961* 2753=2410520633 不成立 2因为 14789* 23567 ( 29mod9) ( 23mod9) mod9 1( mod9) 34853236741( mod9) 5( mod9) 所以等式 14789* 23567=348532367 不成立 3因为 24789* 43717 ( 30mod9) ( 22mod9) mod9 3( mod9) 109270071330( mod9) 3( mod9) 所以等式 24789* 43717=1092700713 可能成立 4这种判断对于判断等式不成立时简单明了但对于判断等式成立时可能会较 复杂。 22解因为 7 为素数由 Wi l so 定理知( 7- 1) !- 1( mod7)即 6- 1mod7 所以 8* 9* 10* 11* 12* 131* 2* 3* 4* 5* 6( mod7)6! ( mod7) - 1( mod7) 31证明因为 c1, c2, , c ( m)是模 m 的简化剩余系 对于任一 ci有 m- ci也属于模 m 的简化剩余系 所以 ci+( m- ci) 0( modm) 因此 c1+c2+c ( m)0( modm) 32证明因为 a ( 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证明因为 7 为素数由 Fer mat 定理知 a7a( mod7) 又a 3 =1所以( a, 9) =1由 Eul er 定理知 a ( 9)a61( mod9) 即 a7 a( mod9) 又( 7, 9) =1,所以 a7a( mod7* 9) 即 a7a( mod63) 34证明因为 32760=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( mod9) 即 a121( mod9) 又因为 5, 7, 8, 9, 13 =32760 所以 a121( mod32760) 35证明因为( p, q) =1p, q 都为素数所以( p) =p- 1,( q) =q- 1 由 Eul er 定理知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证明因为( m, n) =1 由 Eul er 定理知m ( n)1( modn) n ( m)1( modm) 所以 m ( n)+n( m)( m( n)modn) + ( n( m)modn) 1+01( modn) 6 同理有m ( n)+n( m) 1( modm) 又 m, n =mn所以 m ( n)+n( m) 1( modmn) 第三章. 同余式 1 1解因为37=1 | 2 故原同余式有解 又 3x1mod7所以 特解 x05mod7 同余式 3x2mod7的一个特解 x02* x0=2*53mod7 所有解为x3mod7 3解因为1721=1 | 14 故原同余式有解 又 17x1mod21所以 特解 x05mod21 同余式 17x14mod21的一个特解 x014* x0=14*57mod21 所有解为x7mod21 2 1解因为1271012=1 | 833 故原同余式有解 又 127x1mod1012所以 特解 x0255mod1012 同余式 127x833 mod1012 的一个特解 x0833* x0=833*255907 mod1012 所有解为x907mod1012 3见课本 3.2 例 1 7 1解因为514=1 由 Euler 定理知同余方程 5x3mod14的解为 x5 ( 14) - 1* 39mod14 2解因为415=1 由 Euler 定理知同余方程 4x7mod15的解为 x4 ( 15) - 1* 713mod15 3解因为316=1 由 Euler 定理知同余方程 3x5mod16的解为 x3 ( 16) - 1* 57mod16 11证明由中国剩余定理知方程解为 xa1M1M1 + a2M2M2 + akMkMk mod m 因为 mi两两互素又中国剩余定理知MiMi 1mod mi 又 Mi=m/ mi所以mMi1mod mi 所以 MiMi =Mi ( mi )mod mi 代入方程解为 xa1M1 ( m1)+ a 2M2 ( m2)+ a kMk ( mk)( mod m) 得证。 12 1解由方程组得3x+3y2( mod7) 6x+6y4( mod7)x+y- 4( mod7) X5( mod 7)y5 ( mod 7) 2解由方程组得2x+6y2( mod7)2x- y2( mod7) 6x+8y4( mod7)x- y- 4( mod7) X6( mod 7)y3 ( mod 7) 13见课本 3. 2 例 4 14同课本 3. 2 例 321000000562mod1309 15 1解等价同余式组为 7 23x1mod4 23x1mod5 23x1mod7 所以 x3mod4x2mod5x4mod7 所以 x3* 35* 3 + 2* 28* 2 + 4* 20* 667mod140 2解等价同余式组为 17x1mod4 17x1mod5 17x1mod7 17x1mod11 所以 x1mod4x2mod5x- 3mod7x7mod11 所以 x1* 385* 1 + 2* 308* 2 + ( - 3) * 220* 5 + 7* 140* 7 557mod1540 19解3x14+4x13+2x11+x9+x6+x3+12x2+x0mod7 左边=( x7- x) (3x7+4x6+2x4+x2+3x+4) + x6+2x5+2x2+15x2+5x 所以原同余式可化简为x6+2x5+2x2+15x 2+5x0mod7 直接验算得解为x0mod7x6mod7 20解f ( x) 4x3+7mod243 直接验算的同余式 f x0( mod3) 有一解x11mod3 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+32t222(mod 27) t3-f x3* ( f ( x1) - 1( mod3) ) / 330( mod 3) x4 x3+33t322(mod 81) t5-f x4* ( f ( x1) - 1( mod3) ) / 342( mod 3) x5 x4+34t4184(mod 243) 所以同余式 f x0( mod243) 的解为x5184(mod 243) 第四章二次同余式与平方剩余 2解对 x=0, 1, 2, 3, 4, 5, 6 时分别求出 y x=0, y 21( mod7) , y1, 6( mod7) x=4, y 24( mod7) , y2, 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 x=0, y 21( mod17) , y1, 16( mod17) x=1, y 23( mod17) , 无解 x=2, y211( mod17) , 无解 x=3, y214( mod17) , 无解 x=4, y21( mod17) , y1, 16( mod17) x=5, y212( mod17) , 无解 8 x=6, y 22( mod17) , y6, 11( mod17) x=7, y 211( mod17) , 无解 x=8, y 211( mod17) , 无解 x=9, y 28( mod17) , y5, 12( mod17) x=10, y28( mod17) , y5, 12( mod17) x=11, y20( mod17) , y0( mod17) x=12, y27( mod17) , 无解 x=13, y21( mod17) , y1, 16( mod17) x=14, y25( mod17) , 无解 x=15, y28( mod17) , y5, 12( mod17) x=16, y216( mod17) , y4, 13( mod17) 10解( 1. 17/ 37=( - 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) ( 200408 03- 1) / ( 2* 2 )* ( 20040803/ 7) =1 12解 1. 因为- 2/ 67=( 65/ 67) =1 所以- 2 是 67 的平方剩余 所以 x2- 2( mod67) 有 2 个解。 4. 因为2/ 37=( - 1) ( 37* 37- 1) / 8=- 1 所以 2 是 37 的平方非剩余 所以 x22( mod37) 无解。 14证明 1因为 p 为其素数模 p 的所有二次剩余个数为( p- 1) / 2 个 设为 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得证。 2123, p- 1 为 p 的一个完全剩余系 1* 2* 2* ( p- 1) - 1( mod p)( - 1) ( p+1) / 2( - 1)( p- 1) / 2( mod p) 因为模 p 的所有二次剩余乘积模 p 的剩余为( - 1) ( p+1) / 2 所以模 p 的所有非二次剩余乘积模 p 的剩余为( - 1) ( p1) / 2 3 当p=3 时 其二次剩余只有1 所以p=3 时 模p 的所有二次剩余之和模p的 剩余为 1 当 p3 时由1得 a1+a2+a3+a(p-1)/2p( p- 1) ( p+1) / 24( mod p) 因为 p 为奇素数所以 p 只能取 3k- 1 或 3k+1 形式代入上式得 0 所以当 p3 时模 p 的所有二次剩余之和模 p 的剩余为 0。 4因为模 p 的所有二次非剩余之和与所有二次剩余之和的和可以被 p 整除 所以由( 3) 得当 p=3 时模 p 的所有二次非剩余之和模 p 的剩余为- 1; 当 p3 时模 p 的所有二次非剩余之和模 p 的剩余为 0。 16解( 1. 因为7/ 227=( - 1) ( 227- 1) ( 7- 1) / ( 2* 2 )* ( 227/ 7) = 1 所以 7 是 227 的二次剩余 所以 x27( mod227) 有解 9 ( 3. 因为 11 对 91 的逆元是 58 所以原同余方程等价于 x216( mod91) 又 16 是 91 的平方剩余 所以 11x2- 6( mod91) 有解 21证明应用模重复平方法 11=20+21+23 令 x=23, b=2, a=1 ( 1) x0=1a0=a* b2( mod23)b1=b24( mod23) ( 2) x1=1a1=a0* b18( mod23)b2=b1216( mod23) ( 3) x2=0a2=a1* b208( mod23)b3=b223( mod23) ( 4) x3=1a3=a2* b31( mod23) 所以 2111( mod23)即 23| 211- 1 47| 2 23- 1 与 503| 2251- 1 应用同样的方法得证。 第五章原根与指标 1解因为( 13) =12, 所以只需对 12 的因数 d=1, 2, 3, 4, 6, 12, 计算 ad( mod12) 因为 212,224,238,243,26- 1,2121( mod13) 所以 2 模 13 的指数为 12 同理可得5 模 13 的指数为 410 模 13 的指数为 6。 2解因为( 19) =18, 所以只需对 18 的因数 d=1, 2, 3, 6, 9, 18 计算 ad( mod12) 因为 313,329,338,367,39- 1,2181( mod13) 所以 3 模 19 的指数为 18 同理可得7 模 19 的指数为 310 模 19 的指数为 18。 3解因为( m) =( 81) =54=2* 33, 所以( m) 的素因数为 q1=2, q2=3, 进而 ( m) / q1=27,( m) / q2=18 这样只需验证g27, g18模 m 是否同余于 1。对 2456逐个验算 因为 2271( mod81)2181( mod81)根据 5. 2 定理 8 得 所以 2 是模 81 的原根 7证明因为a,m=1,故由 or dm( a) =st 知ast1( mod m)即( as) t1( mod m) 不妨令 or dm( as) =r则 asr1( mod m)所以 st | sr 由( as) t1( mod m) 得 r | t 即 t k* rkN1r t所以 sr st 所以 sr =st所以 r =t 所以 or dm( as) =t 8解存在 举例如 n=7, d=3因为( 7) =6d=3| 6 存在 a=2( 2, 7) =1,2 ( 7)1( mod 7) 又 231( mod 7) 所以 or d7( 2) =3满足条件。 10证明因为 p 为一个奇素数p- 1/ 2 也是一个奇素数 所以( p) =p- 1=2* ( p- 1) / 2即( p) 的不同素因数为 2p- 1/ 2 又因为 a ( p) / 2=ap- 1/ 2 1( mod p)a ( p) / ( p- 1) / 2 =a2 1( mod p) 10 根据 5. 2 定理 8 得 a 是模 p 的原根。 15证明反证法 假设 n 是一个合数令 or dn( a) =m则 am1( mod n) 因为 an- 11( mod n)所以由 5. 1 定理 1 得 m| n- 1即 n- 1=k* m 对 n- 1 的所有素因数 q必可找到一个 q1使 m| ( ( n- 1) / q1) 所以 an- 1/ q=am* t1( mod n)与已知条件矛盾故假设不成立原结论得证。 16解因为 d=( n,( m) ) =( 22,( 41) ) =( 22, 40) =2i nd5=22 所以( n,( m) ) | i nd5同余式有解 等价同余式为 22i ndxi nd5( mod40)即 11i ndx11( mod20) 解得i ndx=1, 21( mod40) 所以原同余式解为 x=6, 35( mod41) 17解因为 d=( n,( m) ) =( 22,( 41) ) =( 22, 40) =2i nd29=7 ( 2, 7) =1所以原同余式无解。 第六章素性检验 1证明因为 91=13* 7 是奇合数( 3, 91) =1 又 36=7291( mod91)则 391- 1=390( 36) 151( mod91) 则 91 是对于基 3 的拟素数。 2证明因为 45=5* 3* 3 是奇合数( 17, 45) =1 由 Eul er 定理1741( mod5)1721( mod3) 所以 1741( mod3)所以 1741( mod45) 则 1745- 1=1744( 174) 111( mod45) 则 45 是对于基 17 的拟素数。 同理 45 是对于基 19 的拟素数。 10证明25=5* 5 是奇素数设 n=25n- 1=24=23* 3则 t =3( 7, 25) =1 7318( mod25)72* 3- 1( mod25) 所以 25 是基于 7 的强拟素数。 15证明n=561=3* 11* 17为奇素数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 是对于基 2 的 Eul er 拟素数。 11 第八章群 2.证明群是交换群的充要条件是对任意有。G, a bG 222 ()aba b= 证明必要性若是交换群则对任意有从而G, a bGabba= 。 222 ()abababaabba b= 充分性若对任意有。那么, a bG 222 ()aba b= 。 1211221 ()baebaeaab ba a b beabeab = 因此群是交换群。G 4. 设是阶有限群。证明对任意元有。GnaG n ae= 证明任取考虑生成的循环群。不妨设。根据拉格朗日定理有aGaaaq= 从 而 存 在 正 整 数使 得。因 为否 则 所 以|q nknqk= q ae=aq 。() nqkk aaee= 6. 设是一个群。记。证明是的正规G( )|()cent GaGbG abba= =( )cent GG 子群。 证明首先证明是的子群。任取。计算( )cent GG 12 ,( )a acent GbG 。 1111111111111 12121212121212 ()()()()ba aabaa baa a ba b aa aba a b = 因此从而是的子群。 1 12 ( )a acent G ( )cent GG 再证 明是的正 规 子 群。 任 取。那 么存 在( )cent GG 1 , cent( ) aG xaG a 使得。由的交换性有。cent( )yG 1 xaya=y 11 cent( )xayaaa yeyyG = 从而是的正规子群。 1 cent( ) cent( )aG aG ( )cent GG 7. 设是群的一个元素。证明映射是到自身的自同构。aG 1 : xaxa G 证明 1任取。计算, x yG 12 1111 ()()( ) ( )xya xy aaxeyaaxa ayaxy = 因此是同态映射。 2若且。那么从而, x yG( )( )xy= 11 axaaya = 1111 xa axa aa aya ay = 因此是单射。 3任取。由于故是满射。cG 111 ()()a caa a ca aecec = 综上所述映射是到自身的自同构。 1 : xaxa G 8. 设是群的子群。在中定义关系。证明HGG 1 :R aRbb aH i是等价关系。R ii的充要条件是。aRbaHbH= 证明 i任取。既然是群的子群那么。因此这说明aGHGeH 1 a aeH = 即满足自反性。aRaR 取满足。那么。根据是群的子群以及逆元的性质我们有, a bGaRb 1 b aH HG 这说明即满足对称性。 111 ()a bb aH =bRaR 取满足。那么。根据是群的子群, ,a b cGaRbbRc 1 b aH 1 c bH HG 我们有。 从而成立即满足传递性。 111 ()()c ac b b aH =aRcR 综上所述是等价关系。R ii即要证明。 1 b aHaHbH = 充分性设则于是存在使得左右aHbH=aaeaHbH=hHabh= 两边同乘得。 1 b 11 b ab bhhH = 必要性如果。对任意存在使得。进而 1 b aH caH 2 hH 2 cah= 1 21 2 ()cb b a hbhhbH = 因此。aHbH 同样对任意存在使得进而。cbH 3 hH 3 cbh= 111 312 ()ca b ahah haH = 因此故。bHaHaHbH= 13 2007 年试题 1证明如果是整数则能被 3 整除。a 3 aa 2 用广义欧几里德算法求最大公因子(4655,12075) 3 设是一个正整数如果证明。m(mod