信息安全数学基础习题答案

信息安全数学基础习题答案第⼀章整数的可除性

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．证明：因为1911/2＜14 ,⼩于14的素数有2，3，5，7，11，13经验算都不能整除191 所以191为素数。

因为5471/2＜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．证明：p1 p2 p3|n，则n= p1 p2 p3k，k∈N+⼜p1

≤p2≤p3，所以n= p1 p2 p3k≥p13 即p13≤n1/3

p 1为素数则p1≥2，⼜p1

≤p2≤p3，所以n= p1 p2 p3k≥2 p2 p3≥2p22即p2

≤(n/2)1/2得证。

11．解：⼩于等于5001/2的所有素数为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的素数只有有限个，记为p1, p2,…, p n

因为4k+3=4k`-1=4k-1 构造N=4*p1*p2*…*p n-1≥3*p1*p2*…*p n所以N＞p i (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）=2

29．（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*(161-3*41)=-14*161+55*(363-2*161)=55*363+(-124)*(1613-4*363)=(-124)*1613+551*(35-2*1613)=551*35+(-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+*(472-1*353)=*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）=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,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个素数p i的乘积，m= p1 p2 p3……p n ，p i为素数。因为7为素数，假设7 !| m，则7 !∈｛p1，p2，p3，……p n｝

所以m2= p12 p22 p32……p n 2=( p1 p2 p3……p n)( p1 p2 p3……p n)所以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．证明：假设log

210是有理数，则存在正整数p, q,使得log2

10=p/q,且（p, q）=1⼜log2

10=ln10/ln2=p/qLn10q=ln2p 10q=2p(2*5)q=2p 5q=2p-q

所以只有当q=p=0是成⽴，所以假设不成⽴故原结论正确，log2

10是⽆理数。同理可证log37，log15

21都是⽆理数。

50．（1）解：因为8=23, 60=22*3*5所以[8,60]=23*3*5=120

51．（4）解：(471179111011001,4111831111011000)= 4104707908301011000=1011000[471179111011001,4111831111011000]= 4111471179111831111011001第⼆章．同余

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)

⼜20080509=6693503*3

所以220080509=(23)6693503≡1(mod7)故220080509是星期六。

7．证明：（i）因为a i≡b i (modm),1≤i≤k 所以a i=b i+k i m⼜a1+a2+… +a k=∑a i=∑(b i+k i m)=∑b i+m*∑k i所以有∑a i≡∑b i (mod m)

即a1+a2+… +a k=b1+b2+… +b k (mod m)

（ii）因为a i≡b i (mod m),1≤i≤k 所以a i(mod m)=b i (mod m)

所以（a1a2…a k）mod m≡[(a1mod m)( a2mod m)…(a k mod m)]mod m≡[(b1mod m)( b2mod m)…(b k mod m)]mod m≡（b1b2…b k）mod m

所以a1a2…a k≡a1a2…a k(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)由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 (mod c) 则a=cq+b , q∈Z根据1.3定理3知(a, c)=(b, c)

17．解：（1）a k+a k-1+… +a0=1+8+4+3+5+8+1=30因为3|30 ,9!|30 所以1843581能被3整除，不能被9整除。（2）a k+a k-1+… +a0=1+8+4+2+3+4+0+8+1=31

因为3!|31 , 9!|31 所以184234081不能被3整除，也不能被9整除。（3）a k+a k-1+… +a0=8+9+3+7+7+5+2+7+4+4=56

因为3!|56 , 9!|56 所以37752744不能被3整除，也不能被9整除。（4）a k+a k-1+… +a0=4+1+5+3+7+6+8+9+1+2+2+4+6=58

因为3!|58 , 9!|58 所以41537612246不能被3整除，也不能被9整除。20．解：（(565mod9)]mod9≡(4*6)mod9≡6(mod9) ≡5299?56270(mod9)

878*565）mod9≡[(878mod9)*⼜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）因为147*23567≡[(29mod9)(23mod9)]mod9 ≡1(mod9) 348532367≡41(mod9) ≡5(mod9)所以等式147*23567=348532367不成⽴

（3）因为247*43717≡[(30mod9)(22mod9)]mod9 ≡3(mod9) 1092700713≡30(mod9) ≡3(mod9)所以等式247*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-c i )≡0(modm)因此c 1+c 2+…+c ?(m)≡0(modm)32．证明：因为a ?(m)≡1(modm) 所以a ?(m)-1≡0(modm)

a ?(m)-1=(a-1)(1+a+ a 2+…+ a ?(m)-1) ≡0(modm) ⼜（a-1,m ）=1所以1+a+ a 2+…+ 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) 即a 7≡a(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≡1(mod13)a ?

(8)≡a 4≡1(mod8) 即a 12≡1(mod8)a ?

(5)≡a 4≡1(mod5) 即a 12≡1(mod5)a ?(7)≡a 6≡1(mod7) 即a 12≡1(mod7)a ?

(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 都为素数 所以?(p)=p-1, ?(q)=q-1由Euler 定理知：p ?(q)≡1(modq) q ?

(p)≡1(modp) 即p q-1≡1(modq) q p-1≡1(modp) ⼜ q p-1≡0(modq) p q-1

≡0(modp) 所以p q-1+q p-1≡1(modq) q p-1+p q-1≡1(modp)⼜[p,q]=pq 所以p q-1+q p-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)同理有：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）（2）解：因为（4，15）=1

由Euler定理知，同余⽅程4x≡7（mod15）的解为：

x≡4?(15)-1*7≡13（mod15）（3）解：因为（3，16）=1

由Euler定理知，同余⽅程3x≡5（mod16）的解为：x≡3?(16)-1*5≡7（mod16）

11．证明：由中国剩余定理知⽅程解为：x≡a1M1M1`+ a2M2M2`+……+ akMkMk

`（mod m）因为m

i 两两互素，⼜中国剩余定理知：MiMi

`≡1（mod mi）⼜Mi =m/mi

所以（m，M

i

）≡1（mod mi）所以Mi Mi`=Mi(mi)≡（mod mi）

代⼊⽅程解为x≡a1 M1(m1)+ a2M2(m2)+……+ akMk(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 21000000≡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）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(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)第四章．⼆次同余式与平⽅剩余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),⽆解

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(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得证。（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)有解(3）.因为11对91的逆元是58所以原同余⽅程等价于x 2

≡16(mod91) ⼜16是91的平⽅剩余 所以11x 2≡-6(mod91)有解 21．证明：应⽤模重复平⽅法 11=20+21+23令x=23,b=2,a=1

(1)x 0=1 a 0=a*b ≡2(mod23) b 1=b 2≡4(mod23) (2)x 1=1 a 1=a 0*b 1≡8(mod23) b 2=b 12≡16(mod23)

(3)x 2=0 a 2=a 1*b 20≡8(mod23) b 3=b 22

≡3(mod23) (4)x 3=1 a 3=a 2*b 3≡1(mod23) 所以211≡1(mod23) 即23|211-1 47|223-1与503|2251

-1 应⽤同样的⽅法得证。第五章．原根与指标

1．解：因为?(13)=12,所以只需对12的因数d=1,2,3,4,6,12,计算a d (mod12) 因为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计算a d (mod12) 因为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)的素因数为q 1=2,q 2=3,进⽽ ?(m)/q 1=27, ?(m)/q 2=18

这样，只需验证：g 27,g 18

模m 是否同余于1。对2，4，5，6…逐个验算： 因为227≠1(mod81) 218≠1(mod81) 根据5.2定理8得所以2是模81的原根

7．证明：因为（a, m ）=1, 故由ord m (a)=st 知：a st ≡1(mod m) 即(a s )t ≡1(mod m) 不妨令ord m (a s )=r 则a sr ≡1(mod m)所以st|sr

由(a s )t ≡1(mod m)得r|t 即t ＝k*r k ∈N ≥1 r ≤t 所以sr ≤st所以sr=st 所以r=t 所以ord m (a s )=t8．解：存在

举例：如n=7,d=3 因为?(7)=6 d=3|6存在a=2 (2,7)=1, 2?

(7)≡1(mod 7) ⼜23≡1(mod 7)所以ord 7(2)=3 满⾜条件。

10．证明：因为p 为⼀个奇素数，p-1/2也是⼀个奇素数所以?(p)=p-1=2*(p-1)/2 即?(p)的不同素因数为2，p-1/2⼜因为a ?(p)/2=a p-1/2≠1(mod p) a ?

(p)/[(p-1)/2]=a 2≠1(mod p) 根据5.2定理8得a 是模p 的原根。15．证明：反证法

假设n是⼀个合数，令ord n(a)=m 则a m≡1(mod n)因为a n-1≡1(mod n) 所以由5.1定理1得m|n-1 即n-1=k*m对n-1的所有素因数q，必可找到⼀个q1使m|((n-1)/q1)

所以a n-1/q=a m*t≡1(mod n) 与已知条件⽭盾，故假设不成⽴，原结论得证。16．解：因为d=(n,?(m))=(22,?(41))=(22,40)=2ind5=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

⼜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=25 n-1=24=23*3 则t=3 (7,25)=173≡18(mod25) 72*3≡-1(mod25)所以25是基于7的强拟素数。

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拟素数。第⼋章．群

2. 证明：群G 是交换群的充要条件是对任意,a b G ∈，有222()ab a b =。 证明：?必要性：若G 是交换群，则对任意,a b G∈，有ab ba =，从⽽222

()ab abab aabb a b ===。充分性：若对任意,a b G ∈，有222

()ab a b =。那么1211221

()ba ebae a ab ba ab b

eabe ab ----=====。因此群G 是交换群。

4. 设G 是n 阶有限群。证明：对任意元a G ∈，有n a e =。

证明：任取a G ∈，考虑a ⽣成的循环群a 。不妨设a q =。根据拉格朗⽇定理，有|q n ，

从⽽存在正整数k ，使得n qk =。因为q a e =（否则a q ≠），所以()n q k k a a e e ===。

6. 设G 是⼀个群。记(){|()}cent G a G b G ab ba =∈?∈=。证明：()cent G 是G 的正规⼦群。证明：⾸先证明()cent G 是G 的⼦群。任取12,()a a cent G ∈，b G ∈。计算1111111111111

12121212121212()()()()

ba a a ba a b a a a b a b a a a b a a b -------------======。因此，1

12()a a cent G -∈，从⽽()cent G 是G 的⼦群。再证明()cent G 是G 的正规⼦群。任取1, c e n t () a G x a G a -∈∈。那么存在c e n t ()y G ∈，使得1

x aya -=。由y 的交换性，有11

cent()x aya

aa y ey y G --====∈。从⽽1

cent() cent()a G a G -?，()cent G 是G 的正规⼦群。7. 设a 是群G 的⼀个元素。证明：映射1

:x axa σ-→是G 到⾃⾝的⾃同构。 证明：（1）任取,x y G ∈。计算1111

()()()()xy a xy aaxeya

axa ayax y σσσ----====因此σ是同态映射。

（2）若,x y G ∈，且()()x y σσ=。那么11axa aya --=，从⽽1111

x a axa a a aya a y ----===，因此σ是单射。

（3）任取c G ∈。由于111()()a ca a a ca a ece c σ---===，故σ是满射。 综上所述，映射1:x axa σ-→是G 到⾃⾝的⾃同构。8. 设H 是群G 的⼦群。在G 中定义关系1:R aRb b a H -?∈。证明： （i ）R 是等价关系。（ii ）aRb 的充要条件是aH bH =。

证明：（i ）任取a G ∈。既然H 是群G 的⼦群，那么e H ∈。因此1a a e H -=∈，这说明aRa ，即R 满⾜⾃反性。取,a b G ∈满⾜aR b 。那么1b a H -∈。根据H 是群G 的⼦群以及逆元的性质，我们有111()

a b b a H ---=∈，这说明bR a ，即R 满⾜对称性。

取,,a b c G ∈满⾜aR b ，bR c 。那么1b a H -∈，1c b H -∈。根据H 是群G 的⼦群，我们有111()()c a c b b a H ---=∈。 从⽽aR c 成⽴，即R 满⾜传递性。综上所述R 是等价关系。（ii ）即要证明：1b a H aH bH -∈?=。

充分性：设aH bH =，则a ae aH bH =∈=，于是存在h H ∈使得a bh =，左右两边同乘1b -，得11b a b bh h H --==∈。必要性：如果1b a H -∈。对任意

c aH ∈，存在2h H ∈使得2c ah =。进⽽，1

212()c b b a h bh h bH -==∈，因此，aH bH ?。

同样，对任意c bH ∈，存在3h H ∈使得3c bh =，进⽽111312()c a b a h ah h aH ---==∈。因此bH aH ?，故aH bH =。2007年试题

1 证明：如果a 是整数，则3a a -能被3整除。

2 ⽤⼴义欧⼏⾥德算法求最⼤公因⼦(4655,12075)

3 设m 是⼀个正整数，(mod )a b m ≡，如果|d m ，证明：(mod )a b d ≡。4 解⽅程987610(mod 2668)x ≡

5 解⽅程组2(m od 3)1(m od 5)1(m od 7)x x x ≡??≡??≡?

6 计算3模19的指数。7 计算653??

的Legendre 符号

8 证明：91是对基3的拟素数。

9 设f 是群G 到G '的⼀个同态，{}ker |,()f a a G f a e '=∈=，其中e '是G '的单位元。证明：ker f 是G 的⼦群。10 设a 是群G 的⼀个元素。证明：映射1:x axa σ-→是G 到⾃⾝的⾃同构。2007年试题答案

1 证明：因为a 3-a=(a-1)a(a+1)

当a=3k ，k ∈Z 3|a 则3|a 3-a 当a=3k-1，k ∈Z 3|a+1 则3|a 3-a 当a=3k+1，k ∈Z 3|a-1 则3|a 3-a 所以a 3-a 能被3整除。2. 12075=2*4655+2765 4655=1*2765+10 2765=1*10+875 10=2*875+140 875=6*140+35 140=4*35所以(4655,12075)=35

3. 因为d|m ，所以存在整数'm 使得m dm '=。⼜因为(mod )a b m ≡，所以存在整数k 使得a b m k =+。该式⼜可以写成()a b dm k '=+。故(mod )a b d ≡。4. 987610(mod 2668)x ≡

计算最⼤公因式(987,2668)=1，所以原同余式有解且只有⼀个解。利⽤⼴义欧⼏

⾥德除法，求同余式9871(mod 2668)x ≡的解为02495(m od 2668)x '=。再写出同余式987610(mod 2668)x ≡的解为00610*610*24951190(mod 2668)x x '==≡。5 令1233,5,7m m m ===， 3*5*7105m ==，1235*735,3*721,3*515M M M ======。

分别求解同余式1(mod )i i i M M m '≡（i =1,2,3） 得到12M '=，21M '=，31M '=。故同余式的解为112

233*2*1*1(m od 105)2*35*21*21*11*15*1(m od 105)71(m od 105)x M M M M M M '''≡++≡++≡

6 解：因为?(19)=18,所以只需对18的因数d=1,2,3,6,9,18计算a d (mod12)因为31≡3, 32≡9, 33≡8, 36≡7, 39≡-1, 218≡1(mod13)所以3模19的指数为18； 7 22(531)/8(31)(531)/4(31)/8

62353535353(1)(1)32111(1)1

3----= ? ? ?=-?- ?=-=-?-= ?

8 证明：因为91=13*7是奇合数， (3,91)=1

⼜36=729≡1(mod91) 则391-1=390≡(36)15≡1(mod91) 则91是对于基3的拟素数。9 对任意,ker a b f ∈，有(),()f a e f b e ''==，从⽽，1111()()()()()()()

f ab f a f b f a f b f a f a e ----'====。

因此，1ker ab f -∈，ker f 是群G 的⼦群。 10 证明：（1）任取,x y G ∈。计算1111

()()()()xy a xy aaxeyaaxa ayax y σσσ----====因此σ是同态映射。

（2）若,x y G ∈，且()()x y σσ=。那么11axa aya --=，从⽽1111

x a axa a a aya a y ----===，因此σ是单射。

（3）任取c G ∈。由于111()()a ca a a ca a ece c σ---===，故σ是满射。 综上所述，映射1:x axa σ-→是G 到⾃⾝的⾃同构。