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

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

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

第三章.同余式

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）

（2）解：因为（6，9）=3|3故原同余式有解

又2x≡1（mod3）所以特解x0`≡2（mod3）

同余式2x≡1（mod3）的一个特解x0≡1*x0`=1*2≡2（mod3）

所有解为：x≡2+3t（mod9）t=0,1,2

所以解分别为x≡2，5,8（mod9）

（3）解：因为（17，21）=1|14故原同余式有解

又17x≡1（mod21）所以特解x0`≡5（mod21）

同余式17x≡14（mod21）的一个特解x0≡14*x0`=14*5≡7

（mod21）所有解为：x≡7（mod21）

（4）解：因为（15，25）=5不整除9，故原同余式无解

2．（1）解：因为（127，1012）=1|833故原同余式有解

又127x≡1（mod1012）所以特解x0`≡255（mod1012）

同余式127x≡833（mod1012）的一个特解x0≡833*x

0`=833*255≡907（mod1012）所有解为：x≡907（mod1012）

3．见课本3.2例1

4.设a,b,m是正整数，（a,m）=1,下面的方法可以用来求解一次

同余方程ax≡b(modm)

(3)6x≡7（mod23）

解：依据题意可知，原式与(a%m)x≡-b[m/a](modm)同解

即与5x≡-7*3(mod23)同解,化简得5x≡2(mod23).

重复使用上述过程，5x≡2(mod23)-3x≡-8(mod23)-2x

≡10(mod23)-x≡5(mod23).x≡5(mod23)即为方程的解。

5.设p是素数，k是正整数，证明：同余式X2≡1(modpk)正好

有两个不同余的解

6.证明：k2时，同余式X2≡1(mod2k)恰好有四个不同的解

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）

8.解：根据题意可设倍数为x,那么可列出同余式组：

11x≡1（mod2）

11x≡1（mod3）

11x≡1（mod5）

11x≡1（mod7）

所有首项系数化为1得到

x≡1（mod2）

x≡2（mod3）

x≡1（mod5）

x≡2（mod7）

其中m=2*3*5*7=210；M1=3*5*7=105，M1’M1≡1（mod

2），→M1’=1；M2=2*5*7=70，M2’M2≡1（mod3），

→M2’=1；M3=2*3*7=42，M3’M3≡1（mod5），→M3’=3；

M4=2*3*5=30，M4’M4≡1（mod7），→M4’=4；