信息安全數(shù)學(xué)基礎(chǔ)習(xí)題第三章答案

1、精選優(yōu)質(zhì)文檔-傾情為你奉上信息安全數(shù)學(xué)基礎(chǔ)習(xí)題答案第三章.同余式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.設(shè)a,b,m是正整數(shù)，（a,m）=1,下面的方法可以用

3、來求解一次同余方程axb(mod m)(3)6x7（mod 23）解：依據(jù)題意可知，原式與(a%m)x-bm/a(mod m)同解即與5x-7*3(mod 23)同解,化簡得5x2(mod 23).重復(fù)使用上述過程，5x2(mod 23)-3x-8(mod 23)-2x10(mod 23)-x5(mod 23).x5(mod 23)即為方程的解。5.設(shè)p是素數(shù)，k是正整數(shù)，證明：同余式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.解：根據(jù)題意可設(shè)倍數(shù)為x,那么可列出同余式組：11x1（mod 2）11x1（mod 3） 11x1（mod 5）11x1（mod 7）所有首項系數(shù)化為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.構(gòu)造性證明如下:(1)由已知, (a,c),(b,c)=1 于是存在x,y使得 x*(a,c)+y*(b,c)=1 (可以對兩邊求模(a,c)的余數(shù)而得解出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節(jié)

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.設(shè)k是正整數(shù)，a1,ak是兩兩互素的正整數(shù)，證明：存在k個相鄰整數(shù)，使得第j個數(shù)被aj整除(1jk)。17.設(shè)整數(shù)m1,mk兩兩互素，則同余方程組aixbi(mod mj

10、), (1jk)有解的充要條件是每一個同余方程18. 設(shè)整數(shù)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)