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

'信息安全数学基础习题答案第一章整数的可除性1．证明：因为2|n所以n=2k,kZÎ5|n所以5|2k，又（5，2）=1，所以5|k即k=5k1，k1ÎZ7|n所以7|2*5k1,又（7，10）=1，所以7|k1即k1=7k2，k2ÎZ所以n=2*5*7k2即n=70k2,k2ÎZ因此70|n2．证明：因为a3-a=(a-1)a(a+1)当a=3k，kZÎ3|a则3|a3-a当a=3k-1，kÎZ3|a+1则3|a3-a当a=3k+1，kÎZ3|a-1则3|a3-a所以a3-a能被3整除。3．证明：任意奇整数可表示为2k0+1，k0ÎZ（2k0+1）2＝4k02+4k0+1=4k0(k0+1)+1由于k0与k0+1为两连续整数，必有一个为偶数，所以k0(k0+1)=2k所以（2k0+1）2=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)又（3，2）=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/2＜14,小于14的素数有2，3，5，7，11，13经验算都不能整除191所以191为素数。因为5471/2＜24,www.hackshp.cn小于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=910．证明：p1p2p3|n，则n=p1p2p3k，kNÎ+又p1≤p2≤p3，所以n=p1p2p3k≥p13即p13≤n1/3p1为素数则p1≥2，又p1≤p2≤p3，所以n=p1p2p3k≥2p2p3≥2p22即p2≤(n/2)1/2得证。11．解：小于等于5001/2的所有素数为2，3，5，7，11，13，17，19，依次删除这些素数的倍数可得所求素数：12．证明：反证法假设3k+1没有相同形式的素因数，则它一定只能表示成若干形如3k-1的素数相乘。(3k1+1)(3k2+1)=[(3k1+1)k2+k1]*3+1显然若干个3k+1的素数相乘，得1 到的还是3k+1的形式，不能得出3k-1的数，因此假设不成立，结论得证。同理可证其他。13．证明：反证法假设形如4k+3的素数只有有限个，记为p1,p2,…,pn因为4k+3=4k`-1=4k-1构造N=4*p1*p2*…*pn-1≥3*p1*p2*…*pn所以N＞pi(i=1,2,…,n)N为4k-1形式的素数，即为4k+3的形式，所以假设不成立。原结论正确，形如4k+3的素数有无穷多个。28．（1）解：85=1*55+3055=1*30+2530=1*25+525=5*5所以(55,85)=5（2）解：282=1*202+80202=2*80+4280=1*42+3842=1*38+438=9*4+24=2*2所以（202,282）=229．（1）解：2t+1=1*(2t-1)+22t-1=(t-1)*2+12=2*1所以（2t+1,2t-1）=1（2）解：2(n+1)=1*2n+22n=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*(1www.hackshp.cn61-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)2 =951*2947+(-743)*3772所以s=951t=-74336．证明：因为（a，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．证明：反证法假设n为素数，则n|a2-b2=(a+b)(a-b)由1.4定理2知n|a+b或n|a-b,与已知条件矛盾所以假设不成立，原结论正确，n为合数。40．证明：（1）假设是21/2有理数，则存在正整数p，q，使得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有理数，则存在正整数m，n，使得71/2=p/q,且（m,n）=1平方得：m2=2n2,即7|m2将m表示成n个素数pi的乘积，m=p1p2p3……pn，pi为素数。因为7为素数，假设7!|m，则7!∈｛p1，p2，p3，……pn｝所以m2=p12p22p32……pn2=(p1p2p3……pn)(p1p2p3……pn)所以7!|m2，与7|m2矛盾，故7|m,m=7k同理可知：7|n,n=7k0所以(m,n)=(7k,7k0)=7(k,k0)≥7与已知矛盾故原结论正确，71/2不是有理数。（3）同理可证171/2不是有理数。41．证明：假设log210是有理数，则存在正整数p,q,使得log210=p/q,且（p,q）=1又log210=ln课后答案网10/ln2=p/qLn10q=ln2p10q=2p(2*5)q=2p5q=2p-q所以只有当q=p=0是成立，所以假设不成立故原结论正确，www.hackshp.cnlog210是无理数。同理可证log37，log1521都是无理数。50．（1）解：因为8=23,60=22*3*5所以[8,60]=23*3*5=12051．（4）解：(471179111011001,4111831111011000)=4104707908301011000=1011000[471179111011001,4111831111011000]=4111471179111831111011001第二章．同余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不能实现。2．证明：当m>2时，因为(m-1)2=m2-2m+1=m(m-2)+1所以(m-1)2≡1(modm)即1与(m-1)2在同一个剩余类中，故02,12,…,(m-1)2一定不是模m的完全剩余系。6．解：21≡2(mod7),22≡4(mod7),23≡1(mod7)又20080509=6693503*3所以220080509=(23)6693503≡1(mod7)故220080509是星期六。7．证明：（i）因为ai≡bi(modm),1≤i≤k所以ai=bi+kim又a1+a2+…+ak=∑ai=∑(bi+kim)=∑bi+m*∑ki所以有∑ai≡∑bi(modm)即a1+a2+…+ak=b1+b2+…+bk(modm)（ii）因为ai≡bi(modm),1≤i≤k所以ai(modm)=bi(modm)所以（a1a2…ak）modm≡[(a1modm)(a2modm)…(akmodm)]modm≡[(b1modm)(b2modm)…(bkmodm)]modm≡（b1b2…bk）modm所以a1a2…ak≡a1a2…ak(modm)8．证明：如果a2≡b2(modp)则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．证明：如果a2≡b2(modn)则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)=p>1(n,a+b)=(pq,a+b)=(q,a+b)=q>1故原命题成立。10．证明：因为a≡b(modc)www.hackshp.cn则a=cq+b,qZÎ根据1.3定理3知(a,c)=(b,c)17．解：（1）ak+ak-1+…+a0=1+8+4+3+5+8+1=30因为3|30,9!|30所以1843581能被3整除，不能被9整除。（2）ak+ak-1+…+a0=1+8+4+2+3+4+0+8+1=31因为3!|31,9!|31所以184234081不能被3整除，也不能被9整除。（3）ak+ak-1+…+a0=8+9+3+7+7+5+2+7+4+4=56因为3!|56,9!|56所以8937752744不能被3整除，也不能被9整除。（4）ak+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*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．证明：因为c1,c2,…,cj(m)是模m的简化剩余系对于任一ci，有m-ci也属于模m的简化剩余系所以ci+(m-ci)≡0(modm)因此c1+c2+…+cj(m)≡0(modm)32．证明：因为aj(m)≡1(modm)所以aj(m)-1≡0(modm)aj(m)-1=(a-1)(1+a+a2+…+aj(m)-1)≡0(modm)又（a-1,m）=1所以1+a+a2+…+aj(m)-1≡0(modm)33．证明：因为7为素数，由Fermat定理知a7≡a(mod7)又（a，3）=1所以(a,9)=1由Euler定理知aj(9)≡a6≡1(mod9)即a7≡a(mod9)又(7,9)=1,所以a7≡a(mod7*9)即a7≡a(mod63)34．证明：因为32760=23*3课后答案网2*5*7*13又(a,32760)=1所以(a,2)=(a,3)=(a,5)=(a,7)=(a,13)=1有：aj(13)≡1(mod13)即a12≡1(mod13)aj(8)≡a4≡1(mod8)即a12≡1(mod8)aj(5)≡a4≡1(mod5)即a12≡1(mod5)aj(7)≡a6≡1(www.hackshp.cnmod7)即a12≡1(mod7)aj(9)≡a6≡1(mod9)即a12≡1(mod9)又因为[5,7,8,9,13]=32760所以a12≡1(mod32760)35．证明：因为(p,q)=1p,q都为素数所以j(p)=p-1,j(q)=q-1由Euler定理知：pj(q)≡1(modq)qj(p)≡1(modp)即pq-1≡1(modq)qp-1≡1(modp)又qp-1≡0(modq)pq-1≡0(modp)所以pq-1+qp-1≡1(modq)qp-1+pq-1≡1(modp)又[p,q]=pq所以pq-1+qp-1≡1(modpq)36．证明：因为(m,n)=1由Euler定理知：mj(n)≡1(modn)nj(m)≡1(modm)所以mj(n)+nj(m)≡(mj(n)modn)+(nj(m)modn)≡1+0≡1(modn)5 同理有：mj(n)+nj(m)≡1(modm)又[m,n]=mn所以mj(n)+nj(m)≡1(modmn)第三章.同余式1．（1）解：因为（3，7）=1|2故原同余式有解又3x≡1（mod7）所以特解x0`≡5（mod7）同余式3x≡2（mod7）的一个特解x0≡2*x0`=2*5≡3（mod7）所有解为：x≡3（mod7）（3）解：因为（17，21）=1|14故原同余式有解又17x≡1（mod21）所以特解x0`≡5（mod21）同余式17x≡14（mod21）的一个特解x0≡14*x0`=14*5≡7（mod21）所有解为：x≡7（mod21）2．（1）解：因为（127，1012）=1|833故原同余式有解又127x≡1（mod1012）所以特解x0`≡255（mod1012）同余式127x≡833（mod1012）的一个特解x0≡833*x0`=833*255≡907（mod1012）所有解为：x≡907（mod1012）3．见课本3.2例17．（1）解：因为（5，14）=1由Euler定理知，同余方程5x≡3（mod14）的解为：x≡5j(14)-1*3≡9（mod14）（2）解：因为（4，15）=1由Euler定理知，同余方程4x≡7（mod15）的解为：x≡4j(15)-1*7≡13（mod15）（3）解：因为（3，16）课后答案网=1由Euler定理知，同余方程3x≡5（mod16）的解为：x≡3j(16)-1*5≡7（mod16）11．证明：由中国剩余定理知方程解为：x≡a1M1M1`+a2M2www.hackshp.cnM2`+……+akMkMk`（modm）因为mi两两互素，又中国剩余定理知：MiMi`≡1（modmi）又Mi=m/mi所以（m，Mi）≡1（modmi）所以MiMi`=Mij(mi)≡（modmi）代入方程解为x≡a1M1j(m1)+a2M2j(m2)+……+akMkj(mk)(modm)得证。12．（1）解：由方程组得：3x+3y≡2(mod7)6x+6y≡4(mod7)x+y≡-4(mod7)X≡5(mod7)y≡5(mod7)（2）解：由方程组得：2x+6y≡2(mod7)2x-y≡2(mod7)6x+8y≡4(mod7)x-y≡-4(mod7)X≡6(mod7)y≡3(mod7)13．见课本3.2例414．同课本3.2例321000000≡562（mod1309）15．（1）解：等价同余式组为：6 23x≡1（mod4）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）19．解：3x14+4x13+2x11+x9+x6+x3+12x2+x≡0（mod7）左边=(x7-x)(3x7+4x6+2x4+x2+3x+4)+x6+2x5+2x2+15x2+5x所以原同余式可化简为：x6+2x5+2x2+15x2+5x≡0（mod7）直接验算得解为：x≡0（mod7）x≡6（mod7）20．解：f`(x)≡4x3+7（mod243）直接验算的同余式f（x）≡0(mod3)有一解：x1≡1（mod3）f`(x1)≡4*13*7=-1(mod3)f`(x1)-1≡-1(mod3)所以t1≡-f（x1）*(f`(x1)-1(mod3))/31≡1(mod3)x2≡x1+3t1≡4(mod9)t2≡-f（x2）*(f`(x1)-1(mod3))/32≡2(mod3)x3≡x2+32t2≡22(mod27)t3≡-f（x3）*(f`(x1)-1(mod3))/33≡0(mod3)x4≡x3+33t3≡22(mod81)t5≡-f（x4）*(f`(x1)-1(mod3))/34≡2(mod3)x5≡x4+34t4≡18课后答案网4(mod243)所以同余式f（x）≡0(mod243)的解为：x5≡184(mod243)www.hackshp.cn第四章．二次同余式与平方剩余2．解：对x=0,1,2,3,4,5,6时，分别求出yx=0,y2≡1(mod7),y≡1,6(mod7)x=4,y2≡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时，分别求出yx=0,y2≡1(mod17),y≡1,16(mod17)x=1,y2≡3(mod17),无解x=2,y2≡11(mod17),无解x=3,y2≡14(mod17),无解x=4,y2≡1(mod17),y≡1,16(mod17)x=5,y2≡12(mod17),无解7 x=6,y2≡2(mod17),y≡6,11(mod17)x=7,y2≡11(mod17),无解x=8,y2≡11(mod17),无解x=9,y2≡8(mod17),y≡5,12(mod17)x=10,y2≡8(mod17),y≡5,12(mod17)x=11,y2≡0(mod17),y≡0(mod17)x=12,y2≡7(mod17),无解x=13,y2≡1(mod17),y≡1,16(mod17)x=14,y2≡5(mod17),无解x=15,y2≡8(mod17),y≡5,12(mod17)x=16,y2≡16(mod17),y≡4,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)(20040803-1)/(2*2)*(20040803/7)=112．解：（1）.因为（-2/67）=(65/67)=1所以-2是67的平方剩余所以x2≡-2(mod67)有2个解。（4）.因为（2/37）=(-1)(37*37-1)/8=-1所以2是37的平方非剩余所以x2≡2(mod37)无解。14．证明：（1）因为p为其素数，模p的所有二次剩余个数为(p-1)/2个，设为a1,a2,a3,…a(p-1)/2则a1*a2*a3…a(p-1)/2≡12*22*32…((p-1)/2)2(modp)≡1*2*3…((p-1)/2)*(-(p-1))*(-(p-2))*…(-(p-(p-1)/2))(modp)≡1*2*3…((p-1)/2)*(p-(p-1)/2)…*(p-2)*(p-1)(-1)(p-1)/2(modp)≡(p-1)!*(-1)(p-1)/2(modp)≡(-1)*(-课后答案网1)(p-1)/2(modp)（2.4定理3）≡(-1)(p+1)/2(modp)所以模p的所有二次剩余乘积模p的剩余为(-1)(p+1)/2得证。（2）1，2，3,…p-1为p的一个完全剩余系1*2*2…*(p-1)≡-1(modp)≡(-1)(p+1)/2(-1)(p-1)/2(modp)因为模p的所www.hackshp.cn有二次剩余乘积模p的剩余为(-1)(p+1)/2所以模p的所有非二次剩余乘积模p的剩余为(-1)(p－1)/2（3）当p=3时，其二次剩余只有1，所以p=3时，模p的所有二次剩余之和模p的剩余为1当p>3时，由（1）得a1+a2+a3…+a(p-1)/2≡p(p-1)(p+1)/24(modp)因为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。16．解：(1）.因为（7/227）=(-1)(227-1)(7-1)/(2*2)*(227/7)=1所以7是227的二次剩余所以x2≡7(mod227)有解8 (3）.因为11对91的逆元是58所以原同余方程等价于x2≡16(mod91)又16是91的平方剩余所以11x2≡-6(mod91)有解21．证明：应用模重复平方法11=20+21+23令x=23,b=2,a=1(1)x0=1a0=a*b≡2(mod23)b1=b2≡4(mod23)(2)x1=1a1=a0*b1≡8(mod23)b2=b12≡16(mod23)(3)x2=0a2=a1*b20≡8(mod23)b3=b22≡3(mod23)(4)x3=1a3=a2*b3≡1(mod23)所以211≡1(mod23)即23|211-147|223-1与503|2251-1应用同样的方法得证。第五章．原根与指标1．解：因为j(13)=12,所以只需对12的因数d=1,2,3,4,6,12,计算ad(mod12)因为21≡2,22≡4,23≡8,24≡3,26≡-1,212≡1(mod13)所以2模13的指数为12；同理可得：5模13的指数为4，10模13的指数为6。2．解：因为j(19)=18,所以只需对18的因数d=1,2,3,6,9,18计算ad(mod12)因为31≡3,32≡9,33≡8,36≡7,39≡-1,218≡1(mod13)所以3模19的指数为18；同理可得：7模19的课后答案网指数为3，10模19的指数为18。3．解：因为j(m)=j(81)=54=2*33,所以j(m)的素因数为q1=2,q2=3,进而j(m)/q1=27,j(m)/q2=18这样，只需验证：g27,g18模m是否同余于1。对2，4，5，6…逐个验算：因为227¹1(mod81)2www.hackshp.cn18¹1(mod81)根据5.2定理8得所以2是模81的原根7．证明：因为（a,m）=1,故由ordm(a)=st知：ast≡1(modm)即(as)t≡1(modm)不妨令ordm(as)=r则asr≡1(modm)所以st|sr由(as)t≡1(modm)得r|t即t＝k*rkNÎ≥1r≤t所以sr≤st所以sr=st所以r=t所以ordm(as)=t8．解：存在举例：如n=7,d=3因为j(7)=6d=3|6存在a=2(2,7)=1,2j(7)≡1(mod7)又23≡1(mod7)所以ord7(2)=3满足条件。10．证明：因为p为一个奇素数，p-1/2也是一个奇素数所以j(p)=p-1=2*(p-1)/2即j(p)的不同素因数为2，p-1/2又因为aj(p)/2=ap-1/2¹1(modp)aj(p)/[(p-1)/2]=a2¹1(modp)9 根据5.2定理8得a是模p的原根。15．证明：反证法假设n是一个合数，令ordn(a)=m则am≡1(modn)因为an-1≡1(modn)所以由5.1定理1得m|n-1即n-1=k*m对n-1的所有素因数q，必可找到一个q1使m|((n-1)/q1)所以an-1/q=am*t≡1(modn)与已知条件矛盾，故假设不成立，原结论得证。16．解：因为d=(n,j(m))=(22,j(41))=(22,40)=2ind5=22所以(n,j(m))|ind5，同余式有解等价同余式为22indx≡ind5(mod40)即11indx≡11(mod20)解得：indx=1,21(mod40)所以原同余式解为x=6,35(mod41)17．解：因为d=(n,j(m))=(22,j(41))=(22,40)=2ind29=7(2,7)=1所以原同余式无解。第六章．素性检验1．证明：因为91=13*7是奇合数，(3,91)=1又36=729≡1(mod91)则391-1=390≡(36)15≡1(mod91)则91是对于基3的拟素数。2．证明：因为45=5*3*3是奇合数，(17,45)=1由Euler定理：174≡1(mod5)172≡1(mod3)所以174≡1(mod3)所以174≡1(mod45)则1745-1=1744≡(174)11≡1(mod45)则45是对于基17课后答案网的拟素数。同理45是对于基19的拟素数。10．证明：25=5*5是奇素数设n=25n-1=24=23*3则t=3(7,25)=173≡18(mod25)72*3≡-1(mod25)所以25是基于7www.hackshp.cn的强拟素数。15．证明：n=561=3*11*17为奇素数（561,2）=1b(n-1)/2≡2(561-1)/2≡2280≡1(mod561)(b/n)=(2/561)=(-1)(561*561-1)/8=1所以2280≡(2/561)(mod561)所以561是对于基2的Euler拟素数。10 第八章．群2222.证明：群G是交换群的充要条件是对任意a,bGÎ，有()ab=ab。证明：必Þ要性：若G是交换群，则对任意a,bGÎ，有ab=ba，从而222()ab===ababaabbab。222Ü充分性：若对任意a,bGÎ，有()ab=ab。那么-12-1--1221ba=ebae=a()abb=aabb==eabeab。因此群G是交换群。n4.设是Gn阶有限群。证明：对任意元aGÎ，有ae=。证明：任取aGÎ，考虑生a成的循环群a。不妨设aq=。根据拉格朗日定理，有qqn|，从而存在正整数，k使得n=qk。因为ae=（否则aq¹），所以nqkka=()a==ee。6.设G是一个群。记cent(课后答案网G)={aÎG|("bÎ=G)}abba。证明：centG()是G的正规子群。证明：首先证明centG()是的G子群。任取a,aÎcentG()，bGÎ。计算12-1-1-1-1-1-1-1-1-1-1-1--11baa=aba=a(b)a=a(ab)=a(ba)==aa()baab。12121www.hackshp.cn212121212-1因此，aaÎcentG()，从而centG()是的G子群。12-1再证明centG()是G的正规子群。任取aÎÎG,xacent(Ga)。那么存在-1--11yGÎcent()，使得x=aya。由的y交换性，有x=aya=aay=ey=ÎyGcent()。-1从而acent(G)aGÌcent()，centG()是G的正规子群。-17.设是a群G的一个元素。证明：映射s:x®axa是G到自身的自同构。证明：（1）任取x,yGÎ。计算11 -1-1--11s(xy)=a(xy)a=axeya==axaayass(xy)()因此s是同态映射。--11（2）若x,yGÎ，且ss(xy)=()。那么axa=aya，从而-1-1--11x===aaxaaaayaay，因此是s单射。-1--11（3）任取cGÎ。由于s(aca)=a()acaa==ecec，故s是满射。-1综上所述，映射s:x®axa是G到自身的自同构。-18.设是H群G的子群。在G中定义关系R:aRbÛÎbaH。证明：（i）R是等价关系。（ii）aRb的充要条件是aH=bH。-1证明：（i）任取aGÎ。既然H是群G的子群，那么eHÎ。因此aa=ÎeH，这说明aRa，即R满足自反性。-1取a,bGÎ满足aRb。那么baHÎ。根据H是群G的子群以及逆元的性质，我们有-1--11ab=Î()baH，这说明bRa，即R满足对称性。-1-1取a,,bcGÎ满足aRb，bRc。那么baHÎ，cbHÎ。根据H是群G的子群，-1--11课后答案网我们有ca=Î(cb)()baH。从而aRc成立，即R满足传递性。综上所述R是等价关系。-1（ii）即要证明：baÎHÛ=aHbH。Ü充分性：设aH=bHwww.hackshp.cn，则a=aeÎ=aHbH，于是存在hHÎ使得a=bh，左右-1--11两边同乘b，得ba=bbh=ÎhH。-1Þ必要性：如果baHÎ。对任意cÎaH，存在hHÎ使得c=ah。进而，22-1c=b()bah=ÎbhhbH，212因此，aHÌbH。-1--11同样，对任意cÎbH，存在hHÎ使得c=bh，进而c=a()bah=ÎahhaH。33312因此bHÌaH，故aH=bH。12 2007年试题31证明：如果a是整数，则aa-能被3整除。2用广义欧几里德算法求最大公因子(4655,12075)3设m是一个正整数，aºbm(mod)，如果dm|，证明：aºbd(mod)。4解方程987xº610(mod2668)ìxº2(mod3)ï5解方程组íxº1(mod5)ïîxº1(mod7)6计算3模19的指数。æö67计算ç÷的Legendre符号èø538证明：91是对基3的拟素数。9设是f群G到G¢的一个同态，kerf={a|aÎ=G,f()ae¢}，其中e¢是的G¢单位元。证明：kerf是的G课后答案网子群。-110设是a群G的一个元素。证明：映射s:x®axa是G到自身的自同构。www.hackshp.cn2007年试题答案1证明：因为a3-a=(a-1)a(a+1)当a=3k，kZÎ3|a则3|a3-a当a=3k-1，kÎZ3|a+1则3|a3-a当a=3k+1，kÎZ3|a-1则3|a3-a所以a3-a能被3整除。2.12075=2*4655+27654655=1*2765+18902765=1*1890+8751890=2*875+140875=6*140+3513 140=4*35所以(4655,12075)=353.因为d|m，所以存在整数m"使得m=dm¢。又因为aºbm(mod)，所以存在整数k使得a=+bmk。该式又可以写成a=+bd()mk¢。故aºbd(mod)。4.987xº610(mod2668)计算最大公因式(987,2668)=1，所以原同余式有解且只有一个解。利用广义欧几里德除法，求同余式987xº1(mod2668)的解为x¢=2495(mod2668)。再写出同余0式987xº610(mod2668)的解为xx=610*¢=º610*24951190(mod2668)。005令m=3,mm==5,7，m==3*5*7105，123M=5*7=35,MM=3*7=21,==3*515。123分别求解同余式M¢Mmº1(mod)（i=1,2,3）iii得到M¢=2，M¢=1，M¢=1。故同余式的解为123xºM¢¢¢M*2++MM*1MM*1(mod105)112233º2*3课后答案网5*2++1*21*11*15*1(mod105)º71(mod105)6解：因为j(19)=18,所以只需对18的因数d=1,2,3,6,9,18计算ad(mod12)因为31≡3,32≡9,3www.hackshp.cn3≡8,36≡7,39≡-1,218≡1(mod13)所以3模19的指数为18；7æ6öæ23öæöç÷=ç÷ç÷è53øè53øèø53(532-1)/8(3--1)(531)/4æö53=(-1)×-(1)ç÷èø3æö2(32-1)/8=-1×1×ç÷=-1×(-=1)1èø38证明：因为91=13*7是奇合数，(3,91)=1又36=729≡1(mod91)则391-1=390≡(36)15≡1(mod91)则91是对于基3的拟素数。14 9对任意a,bfÎker，有f(a)==e¢¢,f()be，从而，-1-1--11f(ab)==f(a)f(b)f(a)f(b)==f(a)f()ae¢。-1因此，abfÎker，kerf是群G的子群。10证明：（1）任取x,yGÎ。计算-1-1--11s(xy)=a(xy)a=axeya==axaayass(xy)()因此s是同态映射。--11（2）若x,yGÎ，且ss(xy)=()。那么axa=aya，从而-1-1--11x===aaxaaaayaay，因此是s单射。-1--11（3）任取cGÎ。由于s(aca)=a()acaa==ecec，故s是满射。-1综上所述，映射s:x®axa是G到自身的自同构。课后答案网www.hackshp.cn15'