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

1信息安全数学基础习题答案第三章.同余式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*x0`=833*255≡907（mod1012）所有解为：x≡907（mod1012）3．见课本3.2例14.设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）28.解：根据题意可设倍数为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（mod2），→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；X≡105*1*1+70*1*2+42*3*1+30*4*2≡191(mod210)所以所有解为(191+210t)*11,其中t=0,1,2,3…9.构造性证明如下:(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)modc有解m这是因为(b/(b,c),c)=1,故(b/(b,c))m==1modc有解,从而(2)有解.于是,x*(a,c)+bmy==1modc(3)再求解同余式(a,c)==amy*rmodc注:(1)中,(y,c)=1,(2)中,(m,c)=1,又(a/(a,c),c)=1故1==(a/(a,c))my*rmodc有解,从而式(3)有解.最后可得x*amyr+bmy==1modc即(axr+b)my==1modc于是取n=xr,(an+b,c)=110.证明：必要性是显然的，下面证明充分性。若（m1,m2）|(a1,a2)成立，由3.1节定理1，同余方程m2y≡a1-a2(modm1)有解y≡y0(modm1).记x0=a2+m2y0,则x0≡a2(modm2),并且有x0=a2+m2y0≡a2+a1-a2≡a1(modm1),因此x0是同余方程组的解。即若x1和x2都是同余方程组的解，那么x1≡x2(modm1),x1≡x2(modm2),因此有x1≡x2(mod[m1,m2]).11．证明：由中国剩余定理知方程解为：x≡a1M1M1`+a2M2M2`+……+akMkMk`（modm）因为mi两两互素，又中国剩余定理知：MiMi`≡1（modmi）又Mi=m/mi所以（m，Mi）≡1（modmi）所以MiMi`=Mi(mi)≡（modmi）代入方程解为x≡a1M1(m1)+a2M2(m2)+……+akMk(mk)(modm)得证。12．（1）解：由方程组得：3x+3y≡2(mod7)6x+6y≡4(mod7)x+y≡-4(mod7)X≡5(mod7)y≡5(mod7)（2）解：由方程组得：2x+6y≡2(mod7)2x-y≡2(mod7)6x+8y≡4(mod7)x-y≡-4(mod7)X≡6(mod7)y≡3(mod7)313．见课本3.2例414．同课本3.2例321000000≡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）16.设k是正整数，a1,…ak是两两互素的正整数，证明：存在k个相邻整数，使得第j个数被aj整除(1≤j≤k)。17.设整数m1,…mk两两互素，则同余方程组aix≡bi(modmj),(1≤j≤k)有解的充要条件是每一个同余方程18.设整数m1,…mk两两互素，（aj,mj）=1.证明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(mod3)x2≡x1+3t1≡4(mod9)t2≡-f（x2）*(f`(x1)-1(mod3))/32≡2(mod3)x3≡x2+32t2≡22(mod27)t3≡-f（x3）*(f`(x1)-1(mod3))/33≡0(mod3)x4≡x3+33t3≡22(mod81)t5≡-f（x4）*(f`(x1)-1(mod3))/34≡2(mod3)x5≡x4+34t4≡184(mod243)所以同余式f（x）≡0(mod243)的解为：x5≡184(mod243)