标准的中国剩余定理要求模数$ n_1,n_2,\cdots ,n_k $两两互素，使得

$ \begin{cases}x\equiv a_1(\mod n_1)\x\equiv a_2(\mod n_2)\ \cdots\x\equiv a_k(\mod n_k)\end{cases} $

在模$ N=n_1n_2\cdots n_k $下有唯一解

但如果模数之间不互素，以上结论便不再成立

但是，同余方程组仍可能有解，此时需使用扩展中国剩余定理，并满足相容性条件

对于模数不互质的情况，我们可以通过合并相邻两组方程的方式来逐步得到解

对于

$ \begin{cases}x\equiv a_i(\mod m_i)\x\equiv a_j(\mod m_j)\end{cases} $

可以将其转化成一般形式

$ \begin{cases}x+y_im_i=a_i\x+y_jm_j=a_j\end{cases} $

移项，再合并可得：

$ a_i-a_j=y_im_i-y_jm_j $

现在$ a_i,a_j,m_i,m_j $都是已知的，只有$ y_i,y_j $是未知的。我们不妨把它看成是关于$ y_i,y_j $的不定方程，根据贝祖定理，如果$ gcd(m_i,m_j)\nmid a_i-a_j $的话，这组方程是无解的，从而导致整个方程组是无解的

若$ gcd(m_i,m_j)\mid a_i-a_j $，我们可以使用扩展欧几里得算法求出一组$ y_i,y_j $，然后带回去得到x的一个特解。不过现在的问题在于，存在无穷多组解，使得我们即使求出了其中一对方程的解也无法确定哪个是我们最终都想要的

不过好消息是，扩展中国剩余定理告诉我们，两组这样的同余方程可以再不舍去根的情况下合并成一个方程。下面是扩展中国剩余定理的核心内容：

对于方程组$ \begin{cases}x\equiv u(\mod p)\x\equiv v(\mod q)\end{cases} $，记特解为$ x_0 $，则有通解$ x=x_0-klcm(p,q) $

即这个方程组等价于方程$ x\equiv x_0(\mod lcm(p,q)) $

以下是这个定理的推导过程：

首先原方程组等价于$ \begin{cases}x+py=u\x+qz=v\end{cases} $，即$ \begin{cases}x=u-py\x=v-qz\end{cases} \rightarrow u-py=v-qz $，最后化简成$ u-v=py-qz $（这里的y、z都是同余方程转成不定方程的未知数）

假设我们通过扩展欧几里得算法求得了一组特解$ y_0,z_0 $

上述的方程组具有线性性，所以欲求通解我们可以借用线性代数的核心思想：通解=特解+齐次通解（不用知道为什么，学习了线性代数自然会懂的）

构造对应的齐次方程，求出齐次通解：

$ py-qz=0 \leftrightarrow py=qz $

这意味着：$ p\mid qz $，但由于$ gcd(p,q)=d $，我们可以设：

$ p=dp’\q=dq’ $

其中$ gcd(p’,q’)=1 $

带入得：

$ dp’y=dq’z \rightarrow p’y=q’z $

因为$ gcd(p’,q’)=1 $，所以：

$ q’\mid y $，设$ y=kq’ $

代入得：$ p’(kq’)=q’z\rightarrow z=kp’ $

所以齐次方程的通解为：

$ \begin{cases}y=kq’\z=kp’\end{cases}=\begin{cases}y=k\frac{q}{gcd(p,q)}\z=k\frac{p}{gcd(p,q)}\end{cases} $

由此可得这个方程组的通解为：

$ \begin{cases}y=y_0+k\frac{q}{gcd(p,q)}\z=z_0-k\frac{p}{gcd(p,q)}\end{cases} $

我们通过$ y_0 $,也可以得到x的一个特解$ x_0=u-py_0 $

x的通解为：

$ \begin{aligned}x&=u-p(y_0+k\frac{q}{gcd(p,q)})\ &=u-py_0-k\frac{pq}{gcd(p,q)}\ &=x_0-k\frac{pq}{gcd(p,q)}\ &=x_0-klcm(p,q)\x&=x_0(\mod lcm(p,q))\end{aligned} $

参考文献：
https://zhuanlan.zhihu.com/p/594855411
原文链接：
https://www.yuque.com/fragrantveget/ucxpnh/gn2b6lf95zw08grg?singleDoc# 《扩展中国剩余定理》