问题:
求最小非负整数x，使其满足：
[egin{cases}x&equiv&r_1&pmod {p_1}\x&equiv&r_2&pmod {p_2}\ &&vdots\x&equiv&r_n&pmod {p_n}end{cases}
]
同时不保证模数互质。
解法
考虑同余方程两两合并
[egin{cases}x&equiv&r_1&pmod {p_1}\x&equiv&r_2&pmod {p_2}\ end{cases}
]
合并并移项(1).(r_2-r_1=p_1x_1-p_2x_2),设(p=lcm(p1,p2),g=gcd(p1,p2))
我们可以用(exGCD)算出(p_1x_1-p_2x_2=g)的最小整数解
显然如果(g
ot| (r_2-r_1))则方程无解。
否则有解
那么我们可以得到这个方程((1))的解((x1,x2))
那么将(x1)代入第一个同余式得到一个特解(X)
这时考虑两个同余式的周期——它们每(p)(定义在上面)次能取到一个相等值
结合已经解得的一个特殊解，就可以得到通解(xequiv X (mod p))