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

1、精选优质文档-倾情为你奉上信息安全数学基础习题答案第三章.同余式1（1）解：因为（3，7）=1 | 2 故原同余式有一个解 又3x1（mod7） 所以 特解x05（mod7） 同余式3x2（mod7）的一个特解x02* x0=2*53（mod7） 所有解为：x3（mod7） （2）解：因为（6，9）=3 | 3故原同余式有解 又2x1（mod3） 所以 特解x02（mod3） 同余式2x1（mod3）的一个特解x01* x0=1*22（mod3） 所有解为：x2+3t（mod9）t=0,1,2 所以解分别为x2，5, 8（mod9） （3）解：因为（17，21）=1 | 14 故原同余式有解

2、又17x1（mod 21） 所以 特解x05（mod 21） 同余式17x14（mod 21）的一个特解x014* x0=14*57（mod 21） 所有解为：x7（mod 21）（4）解：因为（15，25）=5 不整除9，故原同余式无解2（1）解：因为（127，1012）=1 | 833 故原同余式有解 又127x1（mod1012） 所以 特解x0255（mod1012） 同余式127x833（mod1012）的一个特解x0833* x0=833*255907（mod1012） 所有解为：x907（mod1012）3见课本3.2例14.设a,b,m是正整数，（a,m）=1,下面的方法可以用

3、来求解一次同余方程axb(mod m)(3)6x7（mod 23）解：依据题意可知，原式与(a%m)x-bm/a(mod m)同解即与5x-7*3(mod 23)同解,化简得5x2(mod 23).重复使用上述过程，5x2(mod 23)-3x-8(mod 23)-2x10(mod 23)-x5(mod 23).x5(mod 23)即为方程的解。5.设p是素数，k是正整数，证明：同余式X21(mod pk)正好有两个不同余的解6.证明：k2时，同余式X21(mod 2k)恰好有四个不同的解7（1）解：因为（5，14）=1 由Euler定理知，同余方程5x3（mod14）的解为： x5(14)-

4、1*39（mod14） （2）解：因为（4，15）=1 由Euler定理知，同余方程4x7（mod15）的解为： x4(15)-1*713（mod15） （3）解：因为（3，16）=1 由Euler定理知，同余方程3x5（mod16）的解为： x3(16)-1*57（mod16）8.解：根据题意可设倍数为x,那么可列出同余式组：11x1（mod 2）11x1（mod 3） 11x1（mod 5）11x1（mod 7）所有首项系数化为1得到x1（mod 2）x2（mod 3）x1（mod 5）x2（mod 7）其中m=2*3*5*7=210；M1=3*5*7=105，M1M11（mod 2），M

5、1=1；M2=2*5*7=70，M2M21（mod 3），M2=1；M3=2*3*7=42，M3M31（mod 5），M3=3；M4=2*3*5=30，M4M41（mod 7），M4=4；X105*1*1+70*1*2+42*3*1+30*4*2191(mod 210)所以所有解为(191+210t)*11,其中t=0,1,2,39.构造性证明如下:(1)由已知, (a,c),(b,c)=1 于是存在x,y使得 x*(a,c)+y*(b,c)=1 (可以对两边求模(a,c)的余数而得解出y,同理可解出x) 注意取合适的y值,使 (y,c)=1 (2)同余式 bm=(b,c) mod c有解m

6、这是因为 (b/(b,c),c)=1,故(b/(b,c) m =1 mod c有解,从而(2)有解. 于是, x*(a,c)+bmy =1 mod c (3)再求解同余式(a,c)=a my *r mod c 注: (1)中,(y,c)=1 ,(2)中, (m,c)=1,又(a/(a,c),c)=1故1=(a/(a,c)my *r mod c有解,从而式(3)有解. 最后可得 x*a myr +bmy =1 mod c 即 (axr+b) my =1 mod c 于是取n=xr, (an+b, c)=110.证明：必要性是显然的，下面证明充分性。若（m1,m2）|(a1,a2)成立，由3.1节

7、定理1，同余方程m2ya1-a2(mod m1)有解yy0(mod m1).记x0=a2+m2y0,则x0a2(mod m2),并且有x0=a2+m2y0a2+a1-a2a1(mod m1),因此x0是同余方程组的解。即若x1和x2都是同余方程组的解，那么x1x2(mod m1),x1x2(mod m2),因此有x1x2(mod m1,m2).11证明：由中国剩余定理知方程解为： xa1M1M1+ a2M2M2+ akMkMk（mod m） 因为mi两两互素，又中国剩余定理知：MiMi1（mod mi） 又Mi=m/mi 所以（m，Mi）1（mod mi） 所以MiMi=Mi(mi)（mod

8、mi） 代入方程解为xa1 M1(m1)+ a2 M2(m2)+ ak Mk(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例414同课本3.2例3 562（mod1309）15（1）解：等价同余式组为： 23x1（mod4） 23x1（mod5） 23x1（mod7） 所以 x3（mod4）

9、x2（mod5） x4（mod7） 所以x3*35*3 + 2*28*2 + 4*20*667（mod140） （2）解：等价同余式组为： 17x1（mod4） 17x1（mod5） 17x1（mod7） 17x1（mod11） 所以 x1（mod4） x2（mod5） x-3（mod7） x7（mod11） 所以x1*385*1 + 2*308*2 + (-3)*220*5 + 7*140*7 557（mod1540）16.设k是正整数，a1,ak是两两互素的正整数，证明：存在k个相邻整数，使得第j个数被aj整除(1jk)。17.设整数m1,mk两两互素，则同余方程组aixbi(mod mj

10、), (1jk)有解的充要条件是每一个同余方程18. 设整数m1,mk两两互素，（aj,mj）=1.证明19解：3x14+4x13+2x11+x9+x6+x3+12x2+x0（mod7） 左边=(x7-x)( 3x7+4x6+2x4+x2+3x+4)+ x6+2x5+2x2+15x2+5x 所以原同余式可化简为：x6+2x5+2x2+15x2+5x0（mod7） 直接验算得解为：x0（mod7） x6（mod7）20解：f(x) 4x3+7（mod243） 直接验算的同余式f（x）0(mod3)有一解：x11（mod3） 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+32 t222(mod 27)