Question

一次同余方程组求解

71014x≡6(mod 19)
x≡71019(mod 23)

Answer 1

用不定方程的方法来做。
————————————————————————————————
先解第一个方程。
71014x≡6(mod 19)
因为71014≡11（mod 19）
所以
11x≡6（mod 19）
11x=19a+6
11x≡19a+6（mod 11）
0≡8a+6（mod 11）
11b=8a+6
11b≡8a+6（mod 8）
3b≡0+6（mod 8）
b≡2（mod 8）
b=2+8p
代入上面式子，11（2+8p）=8a+6，a=11p+2
代入上面式子，11x=19（11p+2）+6，于是x=19p+4
————————————————————————————————
再解第二个方程。
x≡71019(mod 23)
71019≡18(mod 23)
因而x≡18(mod 23)
于是，x=23q+18
————————————————————————————————
联合两个解：
x=19p+4=23q+18
同时取模19，
19p+4≡23q+18（mod 19）
0+4≡4q+(-1)（mod 19）
4q≡5（mod 19）
4q=19c+5
4q≡19c+5（mod 4）
0≡-c+1（mod 4）
c≡1（mod 4）
于是，c=4r+1，代入，
4q=19（4r+1）+5
q=19r+6，代入，
x=23（19r+6）+18
x=437r+156
————————————————————————————————
于是答案即为
x≡156（mod 437）

有更方便的方法，例如孙子定理，套公式即可。那个没啥意思感觉。

---------------------------
【经济数学团队为你解答！】欢迎追问。

Answer 2

原方程组等价于x=6(mod11) ,x=3(mod 8),x=11(mod4) ,x=11(mod 5）
注意到x=3(mod 8)是x=11(mod4)的解的真子集，故等价于
x=6(mod11) ,x=3(mod 8),x=11(mod 5）
由于11,8,5两两互质，所以剩下的工作交给中国剩余定理
最后得到171是一个解，故通解为x=171(mod440)

一般结论：对于模不互质的情形，首先要检验，即任意两个有公约数的模对于最大公约数是否同余
如本题(8,20)=4,且3=11(mod4)，符合
其次，列出等价同余方程组，其原则为所有的模数分解质因子为标准形，然后取每个质因子的最高次幂，并写出相应同余方程
本题，11是质数，8=2^3,20=2^2*5,因此模数分别取11,8,5对应同余方程为
x=6(mod11) ,x=3(mod 8),x=11(mod 5）
最后，由于每个同余方程的模取自不同质数的幂，故互质，所以用中国剩余定理得到一个特解，从而得到通解