第三章.同余式
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（mod 21） 所以 特解x0`≡5（mod 21）
同余式17x≡14（mod 21）的一个特解x0≡14* x0`=14*5≡7（mod 21） 所有解为：x≡7（mod 21）
（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例1
4.设a,b,m是正整数，（a,m）=1,下面的方法可以用来求解一次同余方程ax≡b(mod m) (3)6x≡7（mod 23）
解：依据题意可知，原式与(a%m)x≡-b[m/a](mod m)同解 即与5x≡-7*3(mod 23)同解,化简得5x≡2(mod 23).
重复使用上述过程，5x≡2(mod 23)->3x≡-8(mod 23)->2x≡10(mod 23)->x≡5(mod 23). x≡5(mod 23)即为方程的解。
2k
5.设p是素数，k是正整数，证明：同余式X≡1(mod p)正好有两个不同余的解
2k
6.证明：k>2时，同余式X≡1(mod 2)恰好有四个不同的解 7．（1）解：因为（5，14）=1
由Euler定理知，同余方程5x≡3（mod14）的解为：
(14)-1*3≡9（mod14）
x≡5
（2）解：因为（4，15）=1
由Euler定理知，同余方程4x≡7（mod15）的解为：
(15)-1*7≡13（mod15）
x≡4
（3）解：因为（3，16）=1
由Euler定理知，同余方程3x≡5（mod16）的解为：
(16)-1*5≡7（mod16）
x≡3
1
8.解：根据题意可设倍数为x,那么可列出同余式组：
11x≡1（mod 2） 11x≡1（mod 3） 11x≡1（mod 5） 11x≡1（mod 7）
所有首项系数化为1得到 x≡1（mod 2） x≡2（mod 3） x≡1（mod 5） x≡2（mod 7）
其中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（mod 3），→M2’=1；M3=2*3*7=42，M3’M3≡1（mod 5），→M3’=3；M4=2*3*5=30，M4’M4≡1（mod 7），→M4’=4； X≡105*1*1+70*1*2+42*3*1+30*4*2 ≡191(mod 210)
所以所有解为(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) mod c有解m 这是因为 (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)=1
10.证明：必要性是显然的，下面证明充分性。
若（m1,m2）|(a1,a2)成立，由3.1节定理1，同余方程m2y≡a1-a2(mod m1)有解y≡y0(mod m1).记x0=a2+m2y0,则x0≡a2(mod m2),并且有x0=a2+m2y0≡a2+a1-a2≡a1(mod m1),因此x0是同余方程组的解。即若x1和x2都是同余方程组的解，那么x1≡x2(mod m1),x1≡x2(mod m2),因此有x1≡x2(mod [m1,m2]).
11．证明：由中国剩余定理知方程解为：
x≡a1M1M1`+ a2M2M2`+……+ akMkMk`（mod m）
因为mi两两互素，又中国剩余定理知：MiMi`≡1（mod mi） 又Mi=m/mi 所以（m，Mi）≡1（mod mi）
(mi)≡（mod mi）
所以MiMi`=Mi
(m1)+ a2 M2(m2)+……+ ak Mk(mk)(mod m) 得证。
代入方程解为x≡a1 M1
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)
2
13．见课本3.2例4
1000000
14．同课本3.2例3 2≡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(mod mj), (1≤j≤k)有解的充要条件是每一个同余方程
18. 设整数m1,…mk两两互素，（aj,mj）=1.证明
1413119632
19．解：3x+4x+2x+x+x+x+12x+x≡0（mod7）
776426522
左边=(x-x)( 3x+4x+2x+x+3x+4)+ x+2x+2x+15x+5x
6522
所以原同余式可化简为：x+2x+2x+15x+5x≡0（mod7） 直接验算得解为：x≡0（mod7） x≡6（mod7）
3
20．解：f`(x) ≡ 4x+7（mod243）
直接验算的同余式f（x）≡0(mod3)有一解：x1≡1（mod3）
3-1
f`(x1) ≡4*1*7=-1(mod3) f`(x1)≡-1(mod3)
-11
所以t1≡-f（x1）*( f`(x1)(mod3))/3≡1(mod 3) x2≡ x1+3 t1≡4(mod 9)
-12
t2≡-f（x2）*( f`(x1)(mod3))/3≡2(mod 3)
2
x3≡ x2+3 t2≡22(mod 27)
-13
t3≡-f（x3）*( f`(x1)(mod3))/3≡0(mod 3)
3
x4≡ x3+3 t3≡22(mod 81)
-14
t5≡-f（x4）*( f`(x1)(mod3))/3≡2(mod 3)
4
x5≡ x4+3 t4≡184(mod 243)
所以同余式f（x）≡0(mod243)的解为：x5 ≡184(mod 243)
3
因篇幅问题不能全部显示，请点此查看更多更全内容