信息安全数学基础习题答案
第一章 整数的可除性
1.证明:因为2|n 所以n=2k , k ∈Z
5|n 所以5|2k , 又(5,2)=1,所以5|k 即k=5 k1 ,k 1∈Z 7|n 所以7|2*5 k1 ,又(7,10)=1,所以7| k1 即k 1=7 k2,k 2∈Z 所以n=2*5*7 k2 即n=70 k2, k 2∈Z
因此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.证明:任意奇整数可表示为2 k0+1, k 0∈Z
22 (2 k0+1)=4 k0+4 k0+1=4 k0 (k 0+1)+1
由于k 0与k 0+1为两连续整数,必有一个为偶数,所以k 0 (k 0+1)=2k
2 所以(2 k0+1)=8k+1 得证。
34.证明:设三个连续整数为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 1 p2 p3|n, 则n= p1 p2 p3k ,k ∈N
3 31/3 又p 1≤ p 2 ≤p 3,所以n= p1 p2 p3k ≥p 1 即p 1≤n
2 p 1为素数 则p 1≥2,又p 1≤ p 2 ≤p 3,所以n= p1 p2 p3k ≥2 p2 p3≥2p 2
1/2 即p 2≤(n/2) 得证。
1/211.解:小于等于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的素数相乘,得
到的还是3k+1的形式,不能得出3k-1的数,因此假设不成立,结论得证。
同理可证其他。
13.证明:反证法
假设形如4k+3的素数只有有限个,记为p 1, p2, …, p n
因为4k+3=4k`-1=4k-1 构造N =4*p1*p 2*…*p n -1≥3*p1*p 2*…*p n
所以N >p i (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=-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)
=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, m∈N
22222 因此p =4m=2q q=2m q=2n, n∈N
则(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 i 的乘积,m= p1 p2 p3 ……p n , p i 为素数。 因为7为素数,假设7 !| m,则7 ! ∈{p 1 ,p 2,p 3 ,……p n }
2222 2 所以m = p 1 p2 p3 ……p n =( p1 p2 p3 ……p n )( p1 p2 p3 ……p n )
22 所以7 !| m,与7|m矛盾,故7|m, m=7k
同理可知:7|n, n=7 k0
所以(m, n)=(7k,7 k0)=7(k, k0) ≥7 与已知矛盾
1/2 故原结论正确,7不是有理数。
1/2(3)同理可证17不是有理数。
41.证明:假设log 210是有理数,则存在正整数p, q,使得log 210=p/q,且(p, q)=1 又log 210=ln10/ln2=p/q
q p q p Ln10=ln2 10=2
q p q p-q (2*5)=2 5=2
所以只有当q=p=0是成立,所以假设不成立
故原结论正确,log 210是无理数。
同理可证log 37,log 1521都是无理数。
3250.(1)解:因为8=2, 60=2*3*5
3 所以[8,60]=2*3*5=120
[***********][1**********]51.(4)解:(4779101,4183101)= [1**********]=101
[***********][1**********]01 [4779101,4183101]= [1**********]
第二章.同余
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)
即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 i ≡ b i (modm),1≤i ≤k 所以a i =b i +k i m
又a 1+a 2+… +a k =∑a i =∑(b i +k i m)=∑b i +m*∑k i
所以有∑a i ≡∑b i (mod m)
即a 1+a 2+… +a k =b 1+b 2+… +b k (mod m)
(ii )因为a i ≡ b i (mod m),1≤i ≤k 所以a i (mod m)=b i (mod m)
所以(a 1a 2…a k )mod m≡[(a 1mod m)( a2mod m)…(a k mod m)]mod m ≡[(b 1mod m)( b2mod m)…(b k mod m)]mod m ≡(b 1b 2…b k )mod m
所以 a 1a 2…a k ≡a 1a 2…a k (mod m)
22228.证明:如果a ≡b (mod p) 则a = b+kp , k∈Z
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 , k∈Z
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 k +a k-1+… +a 0=1+8+4+3+5+8+1=30
因为3|30 ,9!|30 所以1843581能被3整除,不能被9整除。
(2)a k +a k-1+… +a 0=1+8+4+2+3+4+0+8+1=31
因为3!|31 , 9!|31 所以184234081不能被3整除,也不能被9整除。
(3)a k +a k-1+… +a 0=8+9+3+7+7+5+2+7+4+4=56
因为3!|56 , 9!|56 所以8937752744不能被3整除,也不能被9整除。
(4)a k +a k-1+… +a 0=4+1+5+3+7+6+8+9+1+2+2+4+6=58
因为3!|58 , 9!|58 所以[1**********]46不能被3整除,也不能被9整除。
20.解:(89878*58965)mod9≡[(89878mod9)*(58965mod9)]mod9≡(4*6)mod9
≡6(mod9) ≡5299?56270(mod9)
又5299?56270≡(45+?)mod9≡?(mod9)
所以 ?=6 即未知数字为6。
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) 2222
所以等式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 1,c 2, …,c ϕ(m)是模m 的简化剩余系
对于任一c i ,有m-c i 也属于模m 的简化剩余系
所以c i +(m-ci ) ≡0(modm)
因此c 1+c2+…+c
32.证明:因为ϕϕ(m)≡0(modm)
(m)≡1(modm) 所以a ϕ(m)
aϕa -1≡0(modm)
(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为素数,由Fermat 定理知a 7 ≡a(mod7)
又(a ,3)=1 所以(a,9)=1 由Euler 定理知a ϕ(9)≡a 6≡1(mod9)
又(7,9)=1, 所以a 7≡a(mod7*9)
即a 7≡a(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) 即a 12≡
aϕ1(mod13)
(8)
aϕ≡a 4≡1(mod8) 即a 12≡1(mod8)
(5)≡a 4≡
aϕ1(mod5) 即a 12≡1(mod5)
(7)≡a 6≡1(mod7) 即a 12
aϕ≡1(mod7)
(9)≡a 6≡1(mod9) 即a 12≡1(mod9)
又因为[5,7,8,9,13]=32760
所以a 12≡1(mod32760)
35.证明:因为(p,q)=1 p,q
由Euler 定理知:p ϕ都为素数 所以ϕ(p)=p-1, ϕ(q)=q-1
(q)≡1(modq) qϕ(p)≡1(modp)
即p q-1≡1(modq) qp-1≡1(modp)
又 qp-1≡0(modq) pq-1≡0(modp)
所以p q-1+qp-1≡1(modq) qp-1+pq-1≡1(modp)
又[p,q]=pq 所以p q-1+qp-1≡1(modpq)
36.证明:因为(m,n)=1
由Euler ϕ(n)
所以m ϕ定理知:m ≡1(modn) nϕ(m)≡1(modm)
(n)+nϕ(m)≡(mϕ(n)modn)+ (nϕ(m)modn)
同理有:m ϕ≡1+0≡1(modn)
(n)+nϕ(m)
又[m,n]=mn 所以m ϕ ≡1(modm)ϕ
(n)+n(m) ≡1(modmn)
第三章. 同余式
a 7≡a(mod9) 即
1.(1)解:因为(3,7)=1 | 2 故原同余式有解
又3x ≡1(mod7) 所以 特解x 0`≡5(mod7)
同余式3x ≡2(mod7)的一个特解x 0≡2* x0`=2*5≡3(mod7)
所有解为:x ≡3(mod7)
(3)解:因为(17,21)=1 | 14 故原同余式有解
又17x ≡1(mod21) 所以 特解x 0`≡5(mod21)
同余式17x ≡14(mod21)的一个特解x 0≡14* x0`=14*5≡7(mod21)
所有解为:x ≡7(mod21)
2.(1)解:因为(127,1012)=1 | 833 故原同余式有解
又127x ≡1(mod1012) 所以 特解x 0`≡255(mod1012)
同余式127x ≡833(mod1012)的一个特解x 0≡833* x0`=833*255≡907(mod1012) 所有解为:x ≡907(mod1012)
3.见课本3.2例1
7.(1)解:因为(5,14)=1
由Euler 定理知,同余方程5x ≡3(mod14)的解为: ϕ(14)-1*3≡9(mod14) x ≡5
(2)解:因为(4,15)=1
由Euler 定理知,同余方程4x ≡7(mod15)的解为: ϕ(15)-1*7≡13(mod15) x ≡4
(3)解:因为(3,16)=1
由Euler 定理知,同余方程3x ≡5(mod16)的解为: ϕ(16)-1*5≡7(mod16) x ≡3
11.证明:由中国剩余定理知方程解为:
x≡a 1M 1M 1`+ a2M 2M 2`+……+ ak M k M k `(mod m)
因为m i 两两互素,又中国剩余定理知:M i M i `≡1(mod mi )
又M i =m/mi 所以(m ,M i )≡1(mod mi ) ϕ(mi)≡(mod mi ) 所以M i M i `=Mi ϕ(m1)+ a2 M2ϕ(m2)+……+ ak Mk ϕ(mk)(mod m) 得证。 代入方程解为x ≡a 1 M1
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
100000014.同课本3.2例3 2≡562(mod1309)
15.(1)解:等价同余式组为:
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)
[1**********]9.解: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≡1(mod3)
3-1 f`(x 1) ≡4*1*7=-1(mod3) f`(x 1) ≡-1(mod3)
-11 所以t 1≡-f (x 1)*( f`(x 1) (mod3))/3≡1(mod 3)
x 2≡ x 1+3 t1≡4(mod 9)
-12 t 2≡-f (x 2)*( f`(x 1) (mod3))/3≡2(mod 3)
2 x 3≡ x 2+3 t2≡22(mod 27)
-13 t 3≡-f (x 3)*( f`(x 1) (mod3))/3≡0(mod 3)
3 x 4≡ x 3+3 t3≡22(mod 81)
-14 t 5≡-f (x 4)*( f`(x 1) (mod3))/3≡2(mod 3)
4 x 5≡ x 4+3 t4≡184(mod 243)
所以同余式f (x )≡0(mod243)的解为:x 5 ≡184(mod 243)
第四章.二次同余式与平方剩余
2.解:对x=0,1,2,3,4,5,6时,分别求出y
2 x=0,y≡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)
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),无解
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 1, a2, a3, …a (p-1)/2
2222则a 1*a2*a3…a (p-1)/2≡1*2*3…((p-1)/2)(mod p)
≡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 1+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。
(227-1)(7-1)/(2*2)16.解:(1). 因为(7/227)=(-1)*(227/7)= 1
所以7是227的二次剩余
2 所以x ≡7(mod227)有解
(3). 因为11对91的逆元是58
2 所以原同余方程等价于x ≡16(mod91)
又16是91的平方剩余
2 所以11x ≡-6(mod91)有解
21.证明:应用模重复平方法
013 11=2+2+2
令x=23,b=2,a=1 2
(1)x0=1 a0=a*b≡2(mod23) b1=b≡4(mod23)
2 (2)x1=1 a1=a0*b1≡8(mod23) b2=b1≡16(mod23)
02 (3)x2=0 a2=a1*b2≡8(mod23) b3=b2≡3(mod23)
(4)x3=1 a3=a2*b3≡1(mod23)
1111 所以2≡1(mod23) 即23|2-1
23251 47|2-1与503|2-1 应用同样的方法得证。
2
第五章.原根与指标
1.解:因为ϕ(13)=12,所以只需对12的因数d=1,2,3,4,6,12,计算a (mod12) d
因为2≡2, 2≡4, 2≡8, 2≡3, 2≡-1, 2≡1(mod13)
所以2模13的指数为12;
同理可得:5模13的指数为4,10模13的指数为6。
d 2.解:因为ϕ(19)=18,所以只需对18的因数d=1,2,3,6,9,18计算a (mod12)
因为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 1=2,q2=3,进而
ϕ(m)/q1=27, ϕ(m)/q2=18
这样,只需验证:g ,g 模m 是否同余于1。对2,4,5,6…逐个验算:
2718 因为2≠1(mod81) 2≠1(mod81) 根据5.2定理8得
所以2是模81的原根
st s t 7.证明:因为(a, m)=1, 故由ord m (a)=st知:a ≡1(mod m) 即(a) ≡1(mod m)
s sr 不妨令ord m (a)=r 则a ≡1(mod m) 所以st|sr
s t 由(a) ≡1(mod m)得r|t 即t =k*r k∈N ≥1 r≤t 所以sr ≤st
所以sr=st 所以r=t
s 所以ord m (a)=t
8.解:存在
举例:如n=7,d=3 因为ϕ(7)=6 d=3|6 ϕ(7)≡1(mod 7) 又23≡1(mod 7) 存在a=2 (2,7)=1, 2
所以ord 7(2)=3 满足条件。
10.证明:因为p 为一个奇素数,p-1/2也是一个奇素数
所以ϕ(p)=p-1=2*(p-1)/2 即ϕ(p)的不同素因数为2,p-1/2 ϕ(p)/2=ap-1/2≠1(mod p) aϕ(p)/[(p-1)/2]=a2≠1(mod p) 又因为a
根据5.2定理8得a 是模p 的原根。
15.证明:反证法
m 假设n 是一个合数,令ord n (a)=m 则a ≡1(mod n)
n-1 因为a ≡1(mod n) 所以由5.1定理1得m|n-1 即n-1=k*m
对n-1的所有素因数q ,必可找到一个q 1使m|((n-1)/q1)
n-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
691-190615 又3=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 拟素数。
第八章.群
2. 证明:群G 是交换群的充要条件是对任意a , b ∈G ,有(ab ) =a b 。 证明:⇒必要性:若G 是交换群,则对任意a , b ∈G ,有ab =ba ,从而 222
(ab ) 2=abab =aabb =a 2b 2。
⇐充分性:若对任意a , b ∈G ,有(ab ) 2=a 2b 2。那么
ba =ebae =a -1(ab ) 2b -1=a -1a 2b 2b -1=eabe =ab 。
因此群G 是交换群。
4. 设G 是n 阶有限群。证明:对任意元a ∈G ,有a =e 。
证明:任取a ∈G ,考虑a 生成的循环群a 。不妨设a =q 。根据拉格朗日定理,有q |n ,
n q k k q
从而存在正整数k ,使得n =qk 。因为a =e (否则a ≠q ),所以a =(a ) =e =e 。
n
6. 设G 是一个群。记cent (G ) ={a ∈G |(∀b ∈G ) ab =ba }。证明:cent (G ) 是G 的正规子群。
证明:首先证明cent (G ) 是G 的子群。任取a 1, a 2∈cent (G ) ,b ∈G 。计算
-1-1-1-1-1
ba 1a 2=a 1ba 2=a 1(b -1) -1a 2=a 1(a 2b -1) -1=a 1(b -1a 2) -1=a 1a 2(b -1) -1=a 1a 2b 。
因此,a 1a 2∈cent (G ) ,从而cent (G ) 是G 的子群。
-1
∈a c e n t G () a 。那么存在再证明cent (G ) 是G 的正规子群。任取a ∈G , x
x =aya -1。由y 的交换性,有x =aya -1=aa -1y =ey =y ∈cent(G ) 。y ∈c e n t G (,使得)
从而a cent(G ) a
7. 设a 是群G 的一个元素。证明:映射σ:x →axa 是G 到自身的自同构。 证明:(1)任取x , y ∈G 。计算
-1
-1
-1
⊂cent(G ) ,cent (G ) 是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 ca ) =a (a ca ) a
-1
-1-1-1
=ece =c ,故σ是满射。
综上所述,映射σ:x →axa 是G 到自身的自同构。
8. 设H 是群G 的子群。在G 中定义关系R :aRb ⇔b a ∈H 。证明: (i )R 是等价关系。
(ii )aRb 的充要条件是aH =bH 。
证明:(i )任取a ∈G 。既然H 是群G 的子群,那么e ∈H 。因此a a =e ∈H ,这说明aRa ,即R 满足自反性。
取a , b ∈G 满足aRb 。那么b a ∈H 。根据H 是群G 的子群以及逆元的性质,我们有
-1
-1
-1
a -1b =(b -1a ) -1∈H ,这说明bRa ,即R 满足对称性。
取a , b , c ∈G 满足aRb ,bRc 。那么b a ∈H ,c b ∈H 。根据H 是群G 的子群,我们有c a =(c b )(b a ) ∈H 。 从而aRc 成立,即R 满足传递性。
综上所述R 是等价关系。
(ii )即要证明:b a ∈H ⇔aH =bH 。
-1
-1
-1
-1
-1-1
⇐充分性:设aH =bH ,则a =ae ∈aH =bH ,于是存在h ∈H 使得a =bh ,左右
两边同乘b ,得b a =b bh =h ∈H 。
-1
-1-1
⇒必要性:如果b -1a ∈H 。对任意c ∈aH ,存在h 2∈H 使得c =ah 2。进而,
c =b (b -1a ) h 2=bh 1h 2∈bH ,
因此,aH ⊂bH 。
同样,对任意c ∈bH ,存在h 3∈H 使得c =bh 3,进而c =a (b a ) h 3=ah 1h 2∈aH 。因此bH ⊂aH ,故aH =bH 。
-1
-1
-1
2007年试题
1 证明:如果a 是整数,则a -a 能被3整除。
3
2 用广义欧几里德算法求最大公因子(4655,12075)
3 设m 是一个正整数,a ≡b (modm ) ,如果d |m ,证明:a ≡b (modd ) 。 4 解方程987x ≡610(mod2668)
⎧x ≡2(mod3) ⎪
5 解方程组⎨x ≡1(mod5)
⎪x ≡1(mod7) ⎩
6 计算3模19的指数。
⎛6⎫
7 计算 ⎪的Legendre 符号
⎝53⎭
8 证明:91是对基3的拟素数。
9 设f 是群G 到G '的一个同态,ker f ={a |a ∈G , f (a ) =e '},其中e '是G '的单位元。证明:ker f 是G 的子群。
10 设a 是群G 的一个元素。证明:映射σ:x →axa -1是G 到自身的自同构。
2007年试题答案
1 证明:因为a 3-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 所以a 3-a 能被3整除。
2. 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
3. 因为d|m,所以存在整数m ' 使得m =dm '。又因为a ≡b (modm ) ,所以存在整数k 使得a =b +mk 。该式又可以写成a =b +d (m 'k ) 。故a ≡b (modd ) 。 4. 987x ≡610(mod2668)
计算最大公因式(987,2668)=1,所以原同余式有解且只有一个解。利用广义欧几
'=2495(mod2668) 。再写出同余里德除法,求同余式987x ≡1(mod2668) 的解为x 0
'=610*2495≡1190(mod2668) 。 式987x ≡610(mod2668) 的解为x 0=610*x 0
5 令m 1=3, m 2=5, m 3=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(modm i ) (i =1,2,3)
'=1,M 3'=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)
6 解:因为ϕ(19)=18,所以只需对18的因数d=1,2,3,6,9,18计算a d (mod12)
因为3≡3, 3≡9, 3≡8, 3≡7, 3≡-1, 2≡1(mod13)
所以3模19的指数为18; 7
1
2
3
6
9
18
⎛6⎫⎛2⎫⎛3⎫ ⎪= ⎪⎪⎝53⎭⎝53⎭⎝53⎭
=(-1)
(532-1) /8
⎛53⎫
⋅(-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
又3=729≡1(mod91) 则3=3≡(3) ≡1(mod91) 则91是对于基3的拟素数。
9 对任意a , b ∈ker f ,有f (a ) =e ', f (b ) =e ',从而,
6
91-1
90
615
f (ab -1) =f (a ) f (b -1) =f (a ) f (b ) -1=f (a ) f (a ) -1=e '。
因此,ab ∈ker f ,ker f 是群G 的子群。 10 证明:(1)任取x , y ∈G 。计算
-1
σ(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
-1
-1
-1
-1
=ece =c ,故σ是满射。
综上所述,映射σ:x →axa 是G 到自身的自同构。
信息安全数学基础习题答案
第一章 整数的可除性
1.证明:因为2|n 所以n=2k , k ∈Z
5|n 所以5|2k , 又(5,2)=1,所以5|k 即k=5 k1 ,k 1∈Z 7|n 所以7|2*5 k1 ,又(7,10)=1,所以7| k1 即k 1=7 k2,k 2∈Z 所以n=2*5*7 k2 即n=70 k2, k 2∈Z
因此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.证明:任意奇整数可表示为2 k0+1, k 0∈Z
22 (2 k0+1)=4 k0+4 k0+1=4 k0 (k 0+1)+1
由于k 0与k 0+1为两连续整数,必有一个为偶数,所以k 0 (k 0+1)=2k
2 所以(2 k0+1)=8k+1 得证。
34.证明:设三个连续整数为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 1 p2 p3|n, 则n= p1 p2 p3k ,k ∈N
3 31/3 又p 1≤ p 2 ≤p 3,所以n= p1 p2 p3k ≥p 1 即p 1≤n
2 p 1为素数 则p 1≥2,又p 1≤ p 2 ≤p 3,所以n= p1 p2 p3k ≥2 p2 p3≥2p 2
1/2 即p 2≤(n/2) 得证。
1/211.解:小于等于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的素数相乘,得
到的还是3k+1的形式,不能得出3k-1的数,因此假设不成立,结论得证。
同理可证其他。
13.证明:反证法
假设形如4k+3的素数只有有限个,记为p 1, p2, …, p n
因为4k+3=4k`-1=4k-1 构造N =4*p1*p 2*…*p n -1≥3*p1*p 2*…*p n
所以N >p i (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=-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)
=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, m∈N
22222 因此p =4m=2q q=2m q=2n, n∈N
则(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 i 的乘积,m= p1 p2 p3 ……p n , p i 为素数。 因为7为素数,假设7 !| m,则7 ! ∈{p 1 ,p 2,p 3 ,……p n }
2222 2 所以m = p 1 p2 p3 ……p n =( p1 p2 p3 ……p n )( p1 p2 p3 ……p n )
22 所以7 !| m,与7|m矛盾,故7|m, m=7k
同理可知:7|n, n=7 k0
所以(m, n)=(7k,7 k0)=7(k, k0) ≥7 与已知矛盾
1/2 故原结论正确,7不是有理数。
1/2(3)同理可证17不是有理数。
41.证明:假设log 210是有理数,则存在正整数p, q,使得log 210=p/q,且(p, q)=1 又log 210=ln10/ln2=p/q
q p q p Ln10=ln2 10=2
q p q p-q (2*5)=2 5=2
所以只有当q=p=0是成立,所以假设不成立
故原结论正确,log 210是无理数。
同理可证log 37,log 1521都是无理数。
3250.(1)解:因为8=2, 60=2*3*5
3 所以[8,60]=2*3*5=120
[***********][1**********]51.(4)解:(4779101,4183101)= [1**********]=101
[***********][1**********]01 [4779101,4183101]= [1**********]
第二章.同余
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)
即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 i ≡ b i (modm),1≤i ≤k 所以a i =b i +k i m
又a 1+a 2+… +a k =∑a i =∑(b i +k i m)=∑b i +m*∑k i
所以有∑a i ≡∑b i (mod m)
即a 1+a 2+… +a k =b 1+b 2+… +b k (mod m)
(ii )因为a i ≡ b i (mod m),1≤i ≤k 所以a i (mod m)=b i (mod m)
所以(a 1a 2…a k )mod m≡[(a 1mod m)( a2mod m)…(a k mod m)]mod m ≡[(b 1mod m)( b2mod m)…(b k mod m)]mod m ≡(b 1b 2…b k )mod m
所以 a 1a 2…a k ≡a 1a 2…a k (mod m)
22228.证明:如果a ≡b (mod p) 则a = b+kp , k∈Z
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 , k∈Z
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 k +a k-1+… +a 0=1+8+4+3+5+8+1=30
因为3|30 ,9!|30 所以1843581能被3整除,不能被9整除。
(2)a k +a k-1+… +a 0=1+8+4+2+3+4+0+8+1=31
因为3!|31 , 9!|31 所以184234081不能被3整除,也不能被9整除。
(3)a k +a k-1+… +a 0=8+9+3+7+7+5+2+7+4+4=56
因为3!|56 , 9!|56 所以8937752744不能被3整除,也不能被9整除。
(4)a k +a k-1+… +a 0=4+1+5+3+7+6+8+9+1+2+2+4+6=58
因为3!|58 , 9!|58 所以[1**********]46不能被3整除,也不能被9整除。
20.解:(89878*58965)mod9≡[(89878mod9)*(58965mod9)]mod9≡(4*6)mod9
≡6(mod9) ≡5299?56270(mod9)
又5299?56270≡(45+?)mod9≡?(mod9)
所以 ?=6 即未知数字为6。
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) 2222
所以等式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 1,c 2, …,c ϕ(m)是模m 的简化剩余系
对于任一c i ,有m-c i 也属于模m 的简化剩余系
所以c i +(m-ci ) ≡0(modm)
因此c 1+c2+…+c
32.证明:因为ϕϕ(m)≡0(modm)
(m)≡1(modm) 所以a ϕ(m)
aϕa -1≡0(modm)
(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为素数,由Fermat 定理知a 7 ≡a(mod7)
又(a ,3)=1 所以(a,9)=1 由Euler 定理知a ϕ(9)≡a 6≡1(mod9)
又(7,9)=1, 所以a 7≡a(mod7*9)
即a 7≡a(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) 即a 12≡
aϕ1(mod13)
(8)
aϕ≡a 4≡1(mod8) 即a 12≡1(mod8)
(5)≡a 4≡
aϕ1(mod5) 即a 12≡1(mod5)
(7)≡a 6≡1(mod7) 即a 12
aϕ≡1(mod7)
(9)≡a 6≡1(mod9) 即a 12≡1(mod9)
又因为[5,7,8,9,13]=32760
所以a 12≡1(mod32760)
35.证明:因为(p,q)=1 p,q
由Euler 定理知:p ϕ都为素数 所以ϕ(p)=p-1, ϕ(q)=q-1
(q)≡1(modq) qϕ(p)≡1(modp)
即p q-1≡1(modq) qp-1≡1(modp)
又 qp-1≡0(modq) pq-1≡0(modp)
所以p q-1+qp-1≡1(modq) qp-1+pq-1≡1(modp)
又[p,q]=pq 所以p q-1+qp-1≡1(modpq)
36.证明:因为(m,n)=1
由Euler ϕ(n)
所以m ϕ定理知:m ≡1(modn) nϕ(m)≡1(modm)
(n)+nϕ(m)≡(mϕ(n)modn)+ (nϕ(m)modn)
同理有:m ϕ≡1+0≡1(modn)
(n)+nϕ(m)
又[m,n]=mn 所以m ϕ ≡1(modm)ϕ
(n)+n(m) ≡1(modmn)
第三章. 同余式
a 7≡a(mod9) 即
1.(1)解:因为(3,7)=1 | 2 故原同余式有解
又3x ≡1(mod7) 所以 特解x 0`≡5(mod7)
同余式3x ≡2(mod7)的一个特解x 0≡2* x0`=2*5≡3(mod7)
所有解为:x ≡3(mod7)
(3)解:因为(17,21)=1 | 14 故原同余式有解
又17x ≡1(mod21) 所以 特解x 0`≡5(mod21)
同余式17x ≡14(mod21)的一个特解x 0≡14* x0`=14*5≡7(mod21)
所有解为:x ≡7(mod21)
2.(1)解:因为(127,1012)=1 | 833 故原同余式有解
又127x ≡1(mod1012) 所以 特解x 0`≡255(mod1012)
同余式127x ≡833(mod1012)的一个特解x 0≡833* x0`=833*255≡907(mod1012) 所有解为:x ≡907(mod1012)
3.见课本3.2例1
7.(1)解:因为(5,14)=1
由Euler 定理知,同余方程5x ≡3(mod14)的解为: ϕ(14)-1*3≡9(mod14) x ≡5
(2)解:因为(4,15)=1
由Euler 定理知,同余方程4x ≡7(mod15)的解为: ϕ(15)-1*7≡13(mod15) x ≡4
(3)解:因为(3,16)=1
由Euler 定理知,同余方程3x ≡5(mod16)的解为: ϕ(16)-1*5≡7(mod16) x ≡3
11.证明:由中国剩余定理知方程解为:
x≡a 1M 1M 1`+ a2M 2M 2`+……+ ak M k M k `(mod m)
因为m i 两两互素,又中国剩余定理知:M i M i `≡1(mod mi )
又M i =m/mi 所以(m ,M i )≡1(mod mi ) ϕ(mi)≡(mod mi ) 所以M i M i `=Mi ϕ(m1)+ a2 M2ϕ(m2)+……+ ak Mk ϕ(mk)(mod m) 得证。 代入方程解为x ≡a 1 M1
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
100000014.同课本3.2例3 2≡562(mod1309)
15.(1)解:等价同余式组为:
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)
[1**********]9.解: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≡1(mod3)
3-1 f`(x 1) ≡4*1*7=-1(mod3) f`(x 1) ≡-1(mod3)
-11 所以t 1≡-f (x 1)*( f`(x 1) (mod3))/3≡1(mod 3)
x 2≡ x 1+3 t1≡4(mod 9)
-12 t 2≡-f (x 2)*( f`(x 1) (mod3))/3≡2(mod 3)
2 x 3≡ x 2+3 t2≡22(mod 27)
-13 t 3≡-f (x 3)*( f`(x 1) (mod3))/3≡0(mod 3)
3 x 4≡ x 3+3 t3≡22(mod 81)
-14 t 5≡-f (x 4)*( f`(x 1) (mod3))/3≡2(mod 3)
4 x 5≡ x 4+3 t4≡184(mod 243)
所以同余式f (x )≡0(mod243)的解为:x 5 ≡184(mod 243)
第四章.二次同余式与平方剩余
2.解:对x=0,1,2,3,4,5,6时,分别求出y
2 x=0,y≡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)
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),无解
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 1, a2, a3, …a (p-1)/2
2222则a 1*a2*a3…a (p-1)/2≡1*2*3…((p-1)/2)(mod p)
≡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 1+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。
(227-1)(7-1)/(2*2)16.解:(1). 因为(7/227)=(-1)*(227/7)= 1
所以7是227的二次剩余
2 所以x ≡7(mod227)有解
(3). 因为11对91的逆元是58
2 所以原同余方程等价于x ≡16(mod91)
又16是91的平方剩余
2 所以11x ≡-6(mod91)有解
21.证明:应用模重复平方法
013 11=2+2+2
令x=23,b=2,a=1 2
(1)x0=1 a0=a*b≡2(mod23) b1=b≡4(mod23)
2 (2)x1=1 a1=a0*b1≡8(mod23) b2=b1≡16(mod23)
02 (3)x2=0 a2=a1*b2≡8(mod23) b3=b2≡3(mod23)
(4)x3=1 a3=a2*b3≡1(mod23)
1111 所以2≡1(mod23) 即23|2-1
23251 47|2-1与503|2-1 应用同样的方法得证。
2
第五章.原根与指标
1.解:因为ϕ(13)=12,所以只需对12的因数d=1,2,3,4,6,12,计算a (mod12) d
因为2≡2, 2≡4, 2≡8, 2≡3, 2≡-1, 2≡1(mod13)
所以2模13的指数为12;
同理可得:5模13的指数为4,10模13的指数为6。
d 2.解:因为ϕ(19)=18,所以只需对18的因数d=1,2,3,6,9,18计算a (mod12)
因为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 1=2,q2=3,进而
ϕ(m)/q1=27, ϕ(m)/q2=18
这样,只需验证:g ,g 模m 是否同余于1。对2,4,5,6…逐个验算:
2718 因为2≠1(mod81) 2≠1(mod81) 根据5.2定理8得
所以2是模81的原根
st s t 7.证明:因为(a, m)=1, 故由ord m (a)=st知:a ≡1(mod m) 即(a) ≡1(mod m)
s sr 不妨令ord m (a)=r 则a ≡1(mod m) 所以st|sr
s t 由(a) ≡1(mod m)得r|t 即t =k*r k∈N ≥1 r≤t 所以sr ≤st
所以sr=st 所以r=t
s 所以ord m (a)=t
8.解:存在
举例:如n=7,d=3 因为ϕ(7)=6 d=3|6 ϕ(7)≡1(mod 7) 又23≡1(mod 7) 存在a=2 (2,7)=1, 2
所以ord 7(2)=3 满足条件。
10.证明:因为p 为一个奇素数,p-1/2也是一个奇素数
所以ϕ(p)=p-1=2*(p-1)/2 即ϕ(p)的不同素因数为2,p-1/2 ϕ(p)/2=ap-1/2≠1(mod p) aϕ(p)/[(p-1)/2]=a2≠1(mod p) 又因为a
根据5.2定理8得a 是模p 的原根。
15.证明:反证法
m 假设n 是一个合数,令ord n (a)=m 则a ≡1(mod n)
n-1 因为a ≡1(mod n) 所以由5.1定理1得m|n-1 即n-1=k*m
对n-1的所有素因数q ,必可找到一个q 1使m|((n-1)/q1)
n-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
691-190615 又3=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 拟素数。
第八章.群
2. 证明:群G 是交换群的充要条件是对任意a , b ∈G ,有(ab ) =a b 。 证明:⇒必要性:若G 是交换群,则对任意a , b ∈G ,有ab =ba ,从而 222
(ab ) 2=abab =aabb =a 2b 2。
⇐充分性:若对任意a , b ∈G ,有(ab ) 2=a 2b 2。那么
ba =ebae =a -1(ab ) 2b -1=a -1a 2b 2b -1=eabe =ab 。
因此群G 是交换群。
4. 设G 是n 阶有限群。证明:对任意元a ∈G ,有a =e 。
证明:任取a ∈G ,考虑a 生成的循环群a 。不妨设a =q 。根据拉格朗日定理,有q |n ,
n q k k q
从而存在正整数k ,使得n =qk 。因为a =e (否则a ≠q ),所以a =(a ) =e =e 。
n
6. 设G 是一个群。记cent (G ) ={a ∈G |(∀b ∈G ) ab =ba }。证明:cent (G ) 是G 的正规子群。
证明:首先证明cent (G ) 是G 的子群。任取a 1, a 2∈cent (G ) ,b ∈G 。计算
-1-1-1-1-1
ba 1a 2=a 1ba 2=a 1(b -1) -1a 2=a 1(a 2b -1) -1=a 1(b -1a 2) -1=a 1a 2(b -1) -1=a 1a 2b 。
因此,a 1a 2∈cent (G ) ,从而cent (G ) 是G 的子群。
-1
∈a c e n t G () a 。那么存在再证明cent (G ) 是G 的正规子群。任取a ∈G , x
x =aya -1。由y 的交换性,有x =aya -1=aa -1y =ey =y ∈cent(G ) 。y ∈c e n t G (,使得)
从而a cent(G ) a
7. 设a 是群G 的一个元素。证明:映射σ:x →axa 是G 到自身的自同构。 证明:(1)任取x , y ∈G 。计算
-1
-1
-1
⊂cent(G ) ,cent (G ) 是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 ca ) =a (a ca ) a
-1
-1-1-1
=ece =c ,故σ是满射。
综上所述,映射σ:x →axa 是G 到自身的自同构。
8. 设H 是群G 的子群。在G 中定义关系R :aRb ⇔b a ∈H 。证明: (i )R 是等价关系。
(ii )aRb 的充要条件是aH =bH 。
证明:(i )任取a ∈G 。既然H 是群G 的子群,那么e ∈H 。因此a a =e ∈H ,这说明aRa ,即R 满足自反性。
取a , b ∈G 满足aRb 。那么b a ∈H 。根据H 是群G 的子群以及逆元的性质,我们有
-1
-1
-1
a -1b =(b -1a ) -1∈H ,这说明bRa ,即R 满足对称性。
取a , b , c ∈G 满足aRb ,bRc 。那么b a ∈H ,c b ∈H 。根据H 是群G 的子群,我们有c a =(c b )(b a ) ∈H 。 从而aRc 成立,即R 满足传递性。
综上所述R 是等价关系。
(ii )即要证明:b a ∈H ⇔aH =bH 。
-1
-1
-1
-1
-1-1
⇐充分性:设aH =bH ,则a =ae ∈aH =bH ,于是存在h ∈H 使得a =bh ,左右
两边同乘b ,得b a =b bh =h ∈H 。
-1
-1-1
⇒必要性:如果b -1a ∈H 。对任意c ∈aH ,存在h 2∈H 使得c =ah 2。进而,
c =b (b -1a ) h 2=bh 1h 2∈bH ,
因此,aH ⊂bH 。
同样,对任意c ∈bH ,存在h 3∈H 使得c =bh 3,进而c =a (b a ) h 3=ah 1h 2∈aH 。因此bH ⊂aH ,故aH =bH 。
-1
-1
-1
2007年试题
1 证明:如果a 是整数,则a -a 能被3整除。
3
2 用广义欧几里德算法求最大公因子(4655,12075)
3 设m 是一个正整数,a ≡b (modm ) ,如果d |m ,证明:a ≡b (modd ) 。 4 解方程987x ≡610(mod2668)
⎧x ≡2(mod3) ⎪
5 解方程组⎨x ≡1(mod5)
⎪x ≡1(mod7) ⎩
6 计算3模19的指数。
⎛6⎫
7 计算 ⎪的Legendre 符号
⎝53⎭
8 证明:91是对基3的拟素数。
9 设f 是群G 到G '的一个同态,ker f ={a |a ∈G , f (a ) =e '},其中e '是G '的单位元。证明:ker f 是G 的子群。
10 设a 是群G 的一个元素。证明:映射σ:x →axa -1是G 到自身的自同构。
2007年试题答案
1 证明:因为a 3-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 所以a 3-a 能被3整除。
2. 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
3. 因为d|m,所以存在整数m ' 使得m =dm '。又因为a ≡b (modm ) ,所以存在整数k 使得a =b +mk 。该式又可以写成a =b +d (m 'k ) 。故a ≡b (modd ) 。 4. 987x ≡610(mod2668)
计算最大公因式(987,2668)=1,所以原同余式有解且只有一个解。利用广义欧几
'=2495(mod2668) 。再写出同余里德除法,求同余式987x ≡1(mod2668) 的解为x 0
'=610*2495≡1190(mod2668) 。 式987x ≡610(mod2668) 的解为x 0=610*x 0
5 令m 1=3, m 2=5, m 3=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(modm i ) (i =1,2,3)
'=1,M 3'=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)
6 解:因为ϕ(19)=18,所以只需对18的因数d=1,2,3,6,9,18计算a d (mod12)
因为3≡3, 3≡9, 3≡8, 3≡7, 3≡-1, 2≡1(mod13)
所以3模19的指数为18; 7
1
2
3
6
9
18
⎛6⎫⎛2⎫⎛3⎫ ⎪= ⎪⎪⎝53⎭⎝53⎭⎝53⎭
=(-1)
(532-1) /8
⎛53⎫
⋅(-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
又3=729≡1(mod91) 则3=3≡(3) ≡1(mod91) 则91是对于基3的拟素数。
9 对任意a , b ∈ker f ,有f (a ) =e ', f (b ) =e ',从而,
6
91-1
90
615
f (ab -1) =f (a ) f (b -1) =f (a ) f (b ) -1=f (a ) f (a ) -1=e '。
因此,ab ∈ker f ,ker f 是群G 的子群。 10 证明:(1)任取x , y ∈G 。计算
-1
σ(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
-1
-1
-1
-1
=ece =c ,故σ是满射。
综上所述,映射σ:x →axa 是G 到自身的自同构。