当前位置： >>
信息安全数学基础 (陈恭亮 著) 清华大学出版社 课后答案【khdaw
?? ? ?课后答案网，用心为你服务！?? 大学答案 --- 中学答案 --- 考研答案 --- 考试答案 ? 最全最多的课后习题参考答案，尽在课后答案网（）！ Khdaw团队一直秉承用心为大家服务的宗旨，以关注学生的学习生活为出发点， 旨在为广大学生朋友的自主学习提供一个分享和交流的平台。 ? 爱校园（） 课后答案网（） 淘答案（） ?信息安全数学基础习题答案第一章整数的可除性1．证明：因为 2|n 所以 n=2k , k ∈ Z 5|n 所以 5|2k ， 又（5，2）=1，所以 5|k 即 k=5 k1 ，k1 ∈ Z 7|n 所以 7|2*5 k1 ,又（7，10）=1，所以 7| k1 即 k1=7 k2，k2 ∈ Z 所以 n=2*5*7 k2 即 n=70 k2, k2 ∈ Z 因此 70|n 2．证明：因为 a3-a=(a-1)a(a+1) 当 a=3k，k ∈ Z 3|a 则 3|a3-a 当 a=3k-1，k ∈ Z 3|a+1 则 3|a3-a 当 a=3k+1，k ∈ Z 3|a-1 则 3|a3-a 所以 a3-a 能被 3 整除。 3．证明：任意奇整数可表示为 2 k0+1， k0 ∈ Z （2 k0+1）2＝4 k02+4 k0+1=4 k0 (k0+1)+1 由于 k0 与 k0+1 为两连续整数，必有一个为偶数，所以 k0 (k0+1)=2k 所以（2 k0+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), 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 个连续正整数都是合数。 6．证明：因为
,小于 14 的素数有 2，3，5，7，11，13 经验算都不能整除 191 所以 191 为素数。 因为
,小于 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．证明：p1 p2 p3|n， 则 n= p1 p2 p3k，k ∈ N+ 又 p1≤ p2 ≤p3，所以 n= p1 p2 p3k≥p13 即 p13≤n1/3 p1 为素数 则 p1≥2，又 p1≤ p2 ≤p3，所以 n= p1 p2 p3k≥2 p2 p3≥2p22 即 p2≤(n/2) 1/2 得证。 1/2 11．解：小于等于 500 的所有素数为 2，3，5，7，11，13，17，19，依次删除这些素数 的倍数可得所求素数： 12．证明：反证法 假设 3k+1 没有相同形式的素因数， 则它一定只能表示成若干形如 3k-1 的素数相 乘。 (3 k1+1)(3 k2+1)=[( 3 k1+1) k2+ k1]*3+1 显然若干个 3k+1 的素数相乘，得www. khd1课aw后 答案 网.com到的还是 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+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)*() =(-124)*89-2*1613) =551*3589+(- 所以 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*() =208*2947+(-743)*(7)www. khd2课aw后 答案 网.comww=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．证明：反证法 假设 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, m ∈ N 因此 p2=4m2=2q2 q2=2m2 q=2n, n ∈ N 则（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= p1 p2 p3 ……pn ， pi 为素数。 因为 7 为素数，假设 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 与已知矛盾 故原结论正确，71/2 不是有理数。 （3）同理可证 171/2 不是有理数。 41．证明：假设 log210 是有理数，则存在正整数 p, q,使得 log210=p/q,且（p, q）=1 又 log210=ln10/ln2=p/q Ln10q=ln2p 10q=2p (2*5)q=2p 5q=2p-q 所以只有当 q=p=0 是成立，所以假设不成立 故原结论正确，log210 是无理数。 同理可证 log37，log1521 都是无理数。 50． （1）解：因为 8=23, 60=22*3*5 所以[8,60]=23*3*5=120 51． （4）解：(001,1000)= 00]= 1w. k第二章．同余hd3课aw后 答案 网.com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(mod m) 即 1 与(m-1)2 在同一个剩余类中， 故 02,12,…,(m-1)2 一定不是模 m 的完全剩余系。 6．解：21≡2(mod7), 22≡4(mod7), 23≡1(mod7) 又 3503*3 所以 =(23)(mod7) 故
是星期六。 7．证明： （i）因为 ai≡ bi (modm),1≤i≤k 所以 ai=bi+kim 又 a1+a2+… +ak=∑ai=∑(bi+kim)=∑bi+m*∑ki 所以有∑ai≡∑bi (mod m) 即 a1+a2+… +ak=b1+b2+… +bk (mod m) （ii）因为 ai≡ bi (mod m),1≤i≤k 所以 ai(mod m)=bi (mod m) 所以（a1a2…ak）mod m≡[(a1mod m)( a2mod m)…(ak mod m)]mod m ≡[(b1mod m)( b2mod m)…(bk mod m)]mod m ≡（b1b2…bk）mod m 所以 a1a2…ak≡a1a2…ak(mod m) 8．证明：如果 a2≡b2(mod p) 则 a2= b2+kp , k ∈ Z 即 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(mod n) 则 a2= b2+kn , k ∈ Z 即 kn=a2-b2=(a+b)(a-b) 所以 n|(a+b)(a-b) 2 2 由 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）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 所以
不能被 3 整除，也不能被 9 整除。 （3）ak+ak-1+… +a0=8+9+3+7+7+5+2+7+4+4=56 因为 3!|56 , 9!|56 所以
不能被 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 所以 6 不能被 3 整除，也不能被 9 整除。 20．解： （）mod9≡[(89878mod9)*(58965mod9)]mod9≡(4*6)mod9 ≡6(mod9) ≡(mod9) 又 ≡(45+?)mod9≡?(mod9) 所以 ?=6 即未知数字为 6。www. khd4课aw后 答案 网.comwww. k又(7,9)=1, 所以 a7≡a(mod7*9) 即 a7≡a(mod63) 34．证明：因为 *5*7*13 又(a,32760)=1 所以(a,2)=(a,3)=(a,5)=(a,7)=(a,13)=1 有：a ? (13)≡1(mod13) 即 a12≡1(mod13) a ? (8)≡a4≡1(mod8) 即 a12≡1(mod8) a ? (5)≡a4≡1(mod5) 即 a12≡1(mod5) a ? (7)≡a6≡1(mod7) 即 a12≡1(mod7) a ? (9)≡a6≡1(mod9) 即 a12≡1(mod9) 又因为[5,7,8,9,13]=32760 所以 a12≡1(mod32760) 35．证明：因为(p,q)=1 p,q 都为素数 所以 ? (p)=p-1, ? (q)=q-1 由 Euler 定理知：p ? (q)≡1(modq) q ? (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 定理知：m ? (n)≡1(modn) n ? (m)≡1(modm) 所以 m ? (n)+n ? (m)≡(m ? (n)modn)+ (n ? (m)modn)≡1+0≡1(modn)5hda(mod9)课33．证明：因为 7 为素数，由 Fermat 定理知 a7 ≡a(mod7) 又（ a ，3 ） =1 所以 (a,9)=1 由 Euler 定理 知 a ? (9) ≡ a6 ≡ 1(mod9)后 答又（a-1,m）=1 所以 1+a+ a2+…+ a ? (m)-1 ≡0(modm)aw案 网对于任一 ci，有 m-ci 也属于模 m 的简化剩余系 所以 ci+(m-ci)≡0(modm) 因此 c1+c2+…+c ? (m)≡0(modm) 32．证明：因为 a ? (m)≡1(modm) 所以 a ? (m)-1≡0(modm) a ? (m)-1=(a-1)(1+a+ a2+…+ a ? (m)-1) ≡0(modm).c21．解： （1）因为 3≡[(36mod9)(17mod9)]mod9 ≡0(mod9) ≡26(mod9) ≡8(mod9) 所以等式 3= 不成立 （2）因为 ≡[(29mod9)(23mod9)]mod9 ≡1(mod9) ≡41(mod9) ≡5(mod9) 所以等式 = 不成立 （3）因为 ≡[(30mod9)(22mod9)]mod9 ≡3(mod9) ≡30(mod9) ≡3(mod9) 所以等式 = 可能成立 （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,…,c ? (m)是模 m 的简化剩余系om即 a7 ≡同理有：m ? (n)+n ? (m) ≡1(modm) 又[m,n]=mn 所以 m ? (n)+n ? (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 例 1 7． （1）解：因为（5，14）=1 由 Euler 定理知，同余方程 5x≡3（mod14）的解为： x≡5 ? (14)-1*3≡9（mod14）www. k（3）解：因为（3，16）=1 由 Euler 定理知，同余方程 3x≡5（mod16）的解为： x≡3 ? (16)-1*5≡7（mod16）11．证明：由中国剩余定理知方程解为： x≡a1M1M1`+ a2M2M2`+……+ akMkMk`（mod m） 因为 mi 两两互素，又中国剩余定理知：MiMi`≡1（mod mi） 又 Mi=m/mi 所以（m，Mi）≡1（mod mi） 所以 MiMi`=Mi ? (mi)≡（mod mi） 代入方程解为 x≡a1 M1 ? (m1)+ a2 M2 ? (m2)+……+ ak Mk ? (mk)(mod m) 得证。12． （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 2（mod1309） 15． （1）解：等价同余式组为：hd6（2）解：因为（4，15）=1 由 Euler 定理知，同余方程 4x≡7（mod15）的解为： x≡4 ? (15)-1*7≡13（mod15）课aw后 答案 网.comwww. k第四章．二次同余式与平方剩余2．解：对 x=0,1,2,3,4,5,6 时，分别求出 y x=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 时，分别求出 y x=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),无解hd723x≡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） 3 20．解：f`(x) ≡ 4x +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(mod 3) x2≡ x1+3 t1≡4(mod 9) t2≡-f（x2）*( f`(x1)-1(mod3))/32≡2(mod 3) x3≡ x2+32 t2≡22(mod 27) t3≡-f（x3）*( f`(x1)-1(mod3))/33≡0(mod 3) x4≡ x3+33 t3≡22(mod 81) t5≡-f（x4）*( f`(x1)-1(mod3))/34≡2(mod 3) x5≡ x4+34 t4≡184(mod 243) 所以同余式 f（x）≡0(mod243)的解为：x5 ≡184(mod 243)课aw后 答案 网.com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) (1-1)/(2*2) *(/3=1 (6）.（7/）=(-1) (7-1)()/(2*2) *()=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 的平方非剩余 所以 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(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） (p+1)/2 ≡(-1) (mod p) 所以模 p 的所有二次剩余乘积模 p 的剩余为(-1)(p+1)/2 得证。 （2）1，2，3,…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)(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(mod p) 因为 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)有解www. khd8课aw后 答案 网.comwww. k因为 31≡3, 32≡9, 33≡8, 36≡7, 39≡-1, 218≡1(mod13) 所以 3 模 19 的指数为 18； 同理可得：7 模 19 的指数为 3，10 模 19 的指数为 18。 3．解：因为 ? (m)= ? (81)=54=2*33,所以 ? (m)的素因数为 q1=2,q2=3,进而 ? (m)/q1=27, ? (m)/q2=18 这样，只需验证：g27,g18 模 m 是否同余于 1。对 2，4，5，6…逐个验算： 因为 227 ≠ 1(mod81) 218 ≠ 1(mod81) 根据 5.2 定理 8 得 所以 2 是模 81 的原根 7．证明：因为（a, m）=1, 故由 ordm(a)=st 知：ast≡1(mod m) 即(as)t≡1(mod m) 不妨令 ordm(as)=r 则 asr≡1(mod m) 所以 st|sr 由(as)t≡1(mod m)得 r|t 即 t＝k*r k ∈ N≥1 r≤t 所以 sr≤st 所以 sr=st 所以 r=t s 所以 ordm(a )=t 8．解：存在 举例：如 n=7,d=3 因为 ? (7)=6 d=3|6 存在 a=2 (2,7)=1, 2 ? (7)≡1(mod 7) 又 23≡1(mod 7) 所以 ord7(2)=3 满足条件。 10．证明：因为 p 为一个奇素数，p-1/2 也是一个奇素数 所以 ? (p)=p-1=2*(p-1)/2 即 ? (p)的不同素因数为 2，p-1/2 (p)/2 p-1/2 又因为 a ? =a a ? (p)/[(p-1)/2]=a2 ≠ 1(mod p) ≠ 1(mod p)9hd课因为 21≡2, 22≡4, 23≡8, 24≡3, 26≡-1, 212≡1(mod13) 所以 2 模 13 的指数为 12； 同理可得：5 模 13 的指数为 4，10 模 13 的指数为 6。 2．解：因为 ? (19)=18,所以只需对 18 的因数 d=1,2,3,6,9,18 计算 ad(mod12)后 答1．解：因为 ? (13)=12,所以只需对 12 的因数 d=1,2,3,4,6,12,计算 ad(mod12)aw第五章．原根与指标案 网.com(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=1 a0=a*b≡2(mod23) b1=b2≡4(mod23) (2)x1=1 a1=a0*b1≡8(mod23) b2=b12≡16(mod23) (3)x2=0 a2=a1*b20≡8(mod23) b3=b22≡3(mod23) (4)x3=1 a3=a2*b3≡1(mod23) 所以 211≡1(mod23) 即 23|211-1 47|223-1 与 503|2251-1 应用同样的方法得证。根据 5.2 定理 8 得 a 是模 p 的原根。 15．证明：反证法 假设 n 是一个合数，令 ordn(a)=m 则 am≡1(mod n) 因为 an-1≡1(mod n) 所以由 5.1 定理 1 得 m|n-1 即 n-1=k*m 对 n-1 的所有素因数 q，必可找到一个 q1 使 m|((n-1)/q1) 所以 an-1/q=am*t≡1(mod n) 与已知条件矛盾，故假设不成立，原结论得证。 16．解：因为 d=(n, ? (m))=(22, ? (41))=(22,40)=2 ind5=22 所以(n, ? (m))|ind5，同余式有解(2,7)=1所以原同余式无解。ww1．证明：因为 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 4 由 Euler 定理：17 ≡1(mod5) 172≡1(mod3) 所以 174≡1(mod3) 所以 174≡1(mod45) 则 4≡(174)11≡1(mod45) 则 45 是对于基 17 的拟素数。 同理 45 是对于基 19 的拟素数。 10．证明：25=5*5 是奇素数 设 n=25 n-1=24=23*3 则 t=3 (7,25)=1 3 2*3 7 ≡18(mod25) 7 ≡-1(mod25) 所以 25 是基于 7 的强拟素数。 15．证明：n=561=3*11*17 为奇素数 （561,2）=1 b(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 拟素数。w. khd10课aw第六章．素性检验后 答案 网.com等价同余式为 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. 证明：群 G 是交换群的充要条件是对任意 a, b ∈ G ，有 ( ab) 2 = a 2 b 2 。 证明： ? 必要性：若 G 是交换群，则对任意 a, b ∈ G ，有 ab = ba ，从而? 充分性：若对任意 a, b ∈ G ，有 (ab) 2 = a 2 b 2 。那么ba = ebae = a ?1 (ab) 2 b ?1 = a ?1a 2 b2 b ?1 = eabe = ab 。因此群 G 是交换群。4. 设 G 是 n 阶有限群。证明：对任意元 a ∈ G ，有 a n = e 。证明：任取 a ∈ G ，考虑 a 生成的循环群 a 。不妨设 a = q 。根据拉格朗日定理，有q | n ， 从 而 存 在 正 整 数 k ， 使 得 n = qk 。 因 为 a q = e （ 否 则 a ≠ q ）， 所 以6. 设 G 是一个群。记 cent (G ) = {a ∈ G | (?b ∈ G ) ab = ba} 。证明： cent (G ) 是 G 的正规 子群。www. k证明： （1）任取 x, y ∈ G 。计算证明：首先证明 cent (G ) 是 G 的子群。任取 a1 , a2 ∈ cent (G ) ， b ∈ G 。计算?1 ?1 ?1 ?1 ?1 ba1a2 = a1ba2 = a1 (b ?1 )?1 a2 = a1 (a2b ?1 )?1 = a1 (b ?1a2 ) ?1 = a1a2 (b ?1 )?1 = a1a2 b。?1 因此， a1a2 ∈ cent (G ) ，从而 cent (G ) 是 G 的子群。再 证 明 cent (G ) 是 G 的 正 规 子 群 。 任 取 a ∈ G , x ∈ a cent(G ) a ?1 。 那 么 存 在y ∈ cent(G ) ，使得 x = aya ?1 。由 y 的交换性，有 x = aya ?1 = aa ?1 y = ey = y ∈ cent(G ) 。从而 a cent(G ) a ?1 ? cent(G ) ， cent (G ) 是 G 的正规子群。hd11课a n = (a q )k = e k = e 。7. 设 a 是群 G 的一个元素。证明：映射 σ : x → axa 是 G 到自身的自同构。aw?1后 答案 网.com(ab)2 = abab = aabb = a 2b 2 。σ ( xy ) = a( xy )a ?1 = axeya ?1 = axa ?1aya ?1 = σ ( x)σ ( y )因此 σ 是同态映射。 （2）若 x, y ∈ G ，且 σ ( x ) = σ ( y ) 。那么 axa?1= aya ?1 ，从而x = a ?1axa ?1a = a ?1aya ?1a = y ，因此 σ 是单射。 （3）任取 c ∈ G 。由于 σ ( a ? ca ) = a( a ? ca) a ? = ece = c ，故 σ 是满射。1 1 1综上所述，映射 σ : x → axa ?1 是 G 到自身的自同构。8. 设 H 是群 G 的子群。在 G 中定义关系 R : aRb ? b ?1a ∈ H 。证明： （i） R 是等价关系。 （ii） aRb 的充要条件是 aH = bH 。取 a, b ∈ G 满足 aRb 。那么 b a ∈ H 。根据 H 是群 G 的子群以及逆元的性质，我们有hd?1 ?1 ?1课a ?1b = (b ?1a )?1 ∈ H ，这说明 bRa ，即 R 满足对称性。后 答aRa ，即 R 满足自反性。?1取 a, b, c ∈ G 满足 aRb ， bRc 。那么 b a ∈ H ， c b ∈ H 。根据 H 是群 G 的子群， 我们有 c ?1a = ( c ?1b)(b?1a) ∈ H 。 从而 aRc 成立，即 R 满足传递性。www. k?1综上所述 R 是等价关系。? （ii）即要证明： b 1a ∈ H ? aH = bH 。? 充分性：设 aH = bH ，则 a = ae ∈ aH = bH ，于是存在 h ∈ H 使得 a = bh ，左右两边同乘 b ，得 b a = b bh = h ∈ H 。? 必要性：如果 b ?1a ∈ H 。对任意 c ∈ aH ，存在 h2 ∈ H 使得 c = ah2 。进而，c = b(b ?1a )h2 = bh1h2 ∈ bH ，因此， aH ? bH 。 同样，对任意 c ∈ bH ，存在 h3 ∈ H 使得 c = bh3 ，进而 c = a (b ?1a) ?1 h3 = ah1?1h2 ∈ aH 。因此 bH ? aH ，故 aH = bH 。aw?1证明： （i）任取 a ∈ G 。既然 H 是群 G 的子群，那么 e ∈ H 。因此 a a = e ∈ H ，这说明?1案 网12.com2007 年试题2 用广义欧几里德算法求最大公因子 ()3 设 m 是一个正整数， a ≡ b(mod m) ，如果 d | m ，证明： a ≡ b(mod d ) 。 4 解方程 987 x ≡ 610(mod 2668)? 6 ? 7 计算 ? ? 的 Legendre 符号 ? 53 ?9 设 f 是群 G 到 G′ 的一个同态，ker f = {a | a ∈ G , f (a ) = e′} ， 其中 e′ 是 G ′ 的单位 元。证明： ker f 是 G 的子群。w. k2007 年试题答案2. 5+*65=1*0=2*875+140 875=6*140+3510 设 a 是群 G 的一个元素。证明：映射 σ : x → axa ?1 是 G 到自身的自同构。ww1 证明：因为 a3-a=(a-1)a(a+1) 当 a=3k，k ∈ Z 3|a 当 a=3k-1，k ∈ Z 3|a+1 当 a=3k+1，k ∈ Z 3|a-1 所以 a3-a 能被 3 整除。hd138 证明：91 是对基 3 的拟素数。课后 答6 计算 3 模 19 的指数。aw则 3|a3-a 则 3|a3-a 则 3|a3-a案 网? x ≡ 2(mod 3) ? 5 解方程组 ? x ≡ 1(mod 5) ? x ≡ 1(mod 7) ?.com1 证明：如果 a 是整数，则 a3 ? a 能被 3 整除。140=4*35 所以 () =353. 因为 d|m，所以存在整数 m ' 使得 m = dm′ 。又因为 a ≡ b(mod m) ，所以存在整 数 k 使得 a = b + mk 。该式又可以写成 a = b + d (m′k ) 。故 a ≡ b(mod d ) 。 4. 987 x ≡ 610(mod 2668)计算最大公因式(987,2668)=1，所以原同余式有解且只有一个解。利用广义欧几′ = 2495(mod 2668) 。再写出同余 里德除法，求同余式 987 x ≡ 1(mod 2668) 的解为 x0 ′ = 610* 2495 ≡ 1190(mod 2668) 。 式 987 x ≡ 610(mod 2668) 的解为 x0 = 610* x05 令 m1 = 3, m2 = 5, m3 = 7 ， m = 3*5*7 = 105 ， M 1 = 5* 7 = 35, M 2 = 3*7 = 21, M 3 = 3*5 = 15 。 分别求解同余式 M i′M i ≡ 1(mod mi ) （i=1,2,3）www. k76 解：因为 ? (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；? 6 ? ? 2 ?? 3 ? ? ? = ? ?? ? ? 53 ? ? 53 ?? 53 ?2 ? 53 ? = (?1)(53 ?1) / 8 ? (?1)(3?1)(53?1) / 4 ? ? ? 3 ? 2 ?2? = ?1 ?1 ? ? ? = ?1 ? (?1)(3 ?1) / 8 = 1 ?3?8 证明：因为 91=13*7 是奇合数，(3,91)=1 又 36=729≡1(mod91) 则 391-1=390≡(36)15≡1(mod91) 则 91 是对于基 3 的拟素数。hd14课′ =1， M3 ′ = 1 。故同余式的解为 得到 M 1′ = 2 ， M 2′ M 2 *1 + M 3 ′ M 3 *1(mod105) x ≡ M 1′M 1 *2 + M 2≡ 2*35* 2 + 1* 21*1 + 1*15*1(mod105) ≡ 71(mod105)aw后 答案 网.com9 对任意 a, b ∈ kerf ，有 f ( a) = e′, f (b) = e′ ，从而，f (ab ?1 ) = f (a ) f (b?1 ) = f (a ) f (b)?1 = f (a ) f (a) ?1 = e′ 。? 因此， ab 1 ∈ ker f ， ker f 是群 G 的子群。10 证明： （1）任取 x, y ∈ G 。计算σ ( xy ) = a( xy )a ?1 = axeya ?1 = axa ?1aya ?1 = σ ( x)σ ( y )因此 σ 是同态映射。 （2）若 x, y ∈ G ，且 σ ( x ) = σ ( y ) 。那么 axa ?1 = aya ?1 ，从而x = a ?1axa ?1a = a ?1aya ?1a = y ，因此 σ 是单射。（3）任取 c ∈ G 。由于 σ ( a ?1ca ) = a( a ?1ca) a ?1 = ece = c ，故 σ 是满射。 综上所述，映射 σ : x → axa 是 G 到自身的自同构。?1www. k15hd课aw后 答案 网.com
更多搜索：
All rights reserved Powered by
文档资料库内容来自网络，如有侵犯请联系客服。