中国剩余定理是$\text{OI}$中较为基础却常用的数论算法之一。而扩展中国剩余定理作为扩展，解决的问题较中国剩余定理广。本文将介绍扩展中国剩余定理相关内容。
前言
中国剩余定理是$\text{OI}$中较为基础却常用的数论算法之一。而扩展中国剩余定理作为扩展，解决的问题较中国剩余定理广。本文将介绍扩展中国剩余定理相关内容。
- 前置知识：扩展欧几里得（$\text{Exgcd}$）
扩展中国剩余定理
要解决的问题
扩展中国剩余定理要解决的问题是求解线性模方程组。
已知如下$k$个模意义下的方程，求$x$的最小非负整数解。
$\left{\begin{aligned}x\equiv\ a_1(\mod m_1) \quad\ x\equiv\ a_2(\mod m_2) \quad\ x\equiv\ a_3(\mod m_3) \quad\ …\quad\x\equiv\ a_k(\mod m_k) \quad\end{aligned}\right.$
整体思路
扩展中国剩余定理解决此问题的大体思路是将方程依次合并。具体来说，对任意两个方程合并，之后继续做下去，直到剩下一个方程。这样方程组就可以变成一个同余方程，可以用$\text{Exgcd}$解出最小的非负整数$x$。而现在的关键问题就是：如何将两个同余方程合并成一个。
合并同余方程的证明过程
现在只需考虑合并两个方程。假设这两个方程如下：
$$\left{\begin{aligned}x\equiv\ a_1(\mod m_1) \quad\ x\equiv\ a_2(\mod m_2) \quad\end{aligned}\right.$$
也就是：
$$\left{\begin{aligned}x=a_1+k_1m_1 \ x=a_2+k_2m_2\end{aligned}\right.$$
所以：
$$a_1+k_1m_1=a_2+k_2m_2$$
移项得：
$$k_1m_1-k_2m_2=a_2-a_1$$
目前方程的形式很类似$\text{Exgcd}$可解的方程形式：
$$ax+by=\text{gcd}(x,y)$$
而$a_2-a_1$不一定等于$\text{gcd}(m_1,m_2)$，不能直接用$\text{Exgcd}$求解。
但我们可以解出如下方程$k_1’,k_2’$的解：
$$k_1’m_1+k_2’m_2=\text{gcd}(m_1,m_2)$$
注意，这里解得的$k_1’,k_2’$的解有多组。
将这个方程两边乘上$\frac{a_2-a_1}{\text{gcd}(m_1,m_2)}$就是我们要解的方程，所以方程的解为：
$$\left{\begin{aligned}k_1=k_1’* \frac{a_2-a_1}{\text{gcd}(m_1,m_2)}\ k_2=-k_2’* \frac{a_2-a_1}{\text{gcd}(m_1,m_2)}\end{aligned}\right.$$
将方程的解代回到最初的方程
$$\left{\begin{aligned}x=a_1+k_1m_1 \ x=a_2+k_2m_2\end{aligned}\right.$$
中，可得：
$$\left{\begin{aligned}x=a_1+k_1’* \frac{a_2-a_1}{\text{gcd}(m_1,m_2)}m_1 \ x=a_2-k_2’ \frac{a_2-a_1}{\text{gcd}(m_1,m_2)}*m_2\end{aligned}\right.$$
由于$k_1’,k_2’$有多组解，这样的$x$会有多种取值，而不同取值之间成等差，差既是$\frac{a_2-a_1}{\text{gcd}(m_1,m_2)}m_1 $的倍数，又是$\frac{a_2-a_1}{\text{gcd}(m_1,m_2)}m_2$的倍数。由此又可得出，差是$\frac{m_1*m_2}{\text{gcd}(m_1,m_2)}$的倍数，即$\text{lcm}(m_1,m_2)$的倍数。
因此：$x=k_1’m_1+x_1\text{lcm}(m_1,m_2)$
即可将两个同余方程
$$\left{\begin{aligned}x\equiv\ a_1(\mod m_1) \quad\ x\equiv\ a_2(\mod m_2) \quad\end{aligned}\right.$$
合并为
$$x\equiv k_1’*m_1+x_1(\mod (\text{lcm}(m_1,m_2)))$$
结论
将两个同余方程
$$\left{\begin{aligned}x\equiv\ a_1(\mod m_1) \quad\ x\equiv\ a_2(\mod m_2) \quad\end{aligned}\right.$$
合并为一个的步骤为：
1.求解
$$k_1’m_1+k_2’m_2=\text{gcd}(m_1,m_2)$$
中的$k_1’$。
2.合并后的方程为：
$$x\equiv k_1’*m_1+x_1(\mod (\text{lcm}(m_1,m_2)))$$
