中国剩余定理(CRT)不能解决模数不互质情况的模线性同余方程组。这是中国剩余定理的原理所决定的。
但当我们的模数不互质时，这个方式显然就寄掉了，因此我们要打破原有的思路，去找一个新的方式解不定方程组，这时我们的扩展中国剩余定理（EXCRT）就出现了
假设我们现在有如下不定方程组
\[\begin{cases} x \equiv r_1(mod \ m_1) \\ x \equiv r_2(mod \ m_2) \\ x \equiv r_3 (mod \ m_3) \\ \cdot \cdot \cdot \cdot \cdot \cdot \cdot\end{cases} \]显然我们可以得到 $ x = m_1k_1 + r_1 = m_2k_2 + r_2$ ---------- \((1)\)
则我们移项可得 $ m_1k_1 + m_2k_2 = r_2 - r_1$ ---------- \((2)\)
这里我们 \(m_2k_2\) 的系数变为正，是因为 \(k_2\) 是任意整数，所以前面的系数不会影响整个式子）
我们已知式子 \(m_1p_1 + m_2p_2 = \gcd(m_1,m_2)\) 将 \(d\) 设为 $ \gcd(m_1,m_2) $ 。
根据裴蜀定理，此时我们要进行判断，判断 \(r_2-r_1\) 是否为 \(\gcd(m_1,m_2)\) 的倍数，若是，那么有解，若不是，那么无解。
判断完是否有解后我们可以的到一个显然的式子 \(m_1p_1+m_2p_2+km_1m_2-km_1m_2=m_1p_1+m_2p_2=d=\gcd(m_1,m_2)\)
此时最左边的式子我们可以化简为 \(m_1(p_1+km_2)+m_2(p_2-km_1)=d\)
由于我们要找到原式子的通解，所以此时我们将等式两边同乘 $ \dfrac {r_2-r_1}{\gcd(m_1,m_2)} $
则可以得到式子 \(m_1(\dfrac {p_1(r_2-r_1)}{\gcd(m_1,m_2)} + \dfrac {km_2(r_2-r_1)}{\gcd(m_1,m_2)}) + m_2(\dfrac {p_2(r_2-r_1)}{\gcd(m_1,m_2)}- \dfrac {km_1(r_2-r_1)}{\gcd(m_1,m_2)}) = r_2-r_1\) ---------- \((3)\)
由上面的等式 \((2)\) 得可将 \((3)\) 式右面 \(r_2-r_1\) 的式子代换成 $ m_1k_1 + m_2k_2 $
从而得到的等式 $m_1(\dfrac {p_1(r_2-r_1)}{\gcd(m_1,m_2)} + \dfrac {km_2(r_2-r_1)}{\gcd(m_1,m_2)}) + m_2(\dfrac {p_2(r_2-r_1)}{\gcd(m_1,m_2)}- \dfrac {km_1(r_2-r_1)}{\gcd(m_1,m_2)}) = m_1k_1 + m_2k_2 $
由此我们显然可以得到
\[m_1k_1 = m_1(\dfrac {p_1(r_2-r_1)}{\gcd(m_1,m_2)} + \dfrac {km_2(r_2-r_1)}{\gcd(m_1,m_2)}) \]\[m_2k_2 = m_2(\dfrac {p_2(r_2-r_1)}{\gcd(m_1,m_2)} - \dfrac {km_1(r_2-r_1)}{\gcd(m_1,m_2)}) \]消掉第一个式子中的 \(m_1\) 。则我们求得 \(k_1=p_1\dfrac {(r_2-r_1)}{\gcd(m_1,m_2)} + km_2 \dfrac {(r_2-r_1)}{\gcd(m_1,m_2)}\) ---------- \((4)\)
我们将现在得到的等式 \((4)\) 带入等式 \((1)\) 则显然可以得到
\[x = m_1(p_1\dfrac {(r_2-r_1)}{\gcd(m_1,m_2)} + km_2 \dfrac {(r_2-r_1)}{\gcd(m_1,m_2)}) + r_1 \]化简得
\[x = p_1m_1\dfrac {(r_2-r_1)}{\gcd(m_1,m_2)} + km_1m_2 \dfrac {(r_2-r_1)}{\gcd(m_1,m_2)} + r_1 \]由于 \(k\) 是任意的整数，因此我们可以将 \(k\) 的系数化成 \(m_1m_2 \dfrac {1}{\gcd(m_1,m_2)}\)
从而得到最终的式子
\[x = p_1m_1\dfrac {(r_2-r_1)}{\gcd(m_1,m_2)} + km_1m_2 \dfrac {1}{\gcd(m_1,m_2)} + r_1 \]我们此时显然是知道 \(m_1,m_2,r_1,r_2,p_1,\gcd(m_1,m_2)\) 的值，但我们不知道 \(k\) 的值，那么这时我们只要模上 \(k\) 的系数即可消掉 \(k\) 。即把模数变为 \(m_1m_2 \dfrac {(r_2-r_1)}{\gcd(m_1,m_2)}\)
此时我们就将两个不定方程组合并完成了
\(x \equiv p_1m_1\dfrac {(r_2-r_1)}{\gcd(m_1,m_2)} + r_1 (mod \ \dfrac {m_1m_2}{\gcd(m_1,m_2)})\)
则此时新的不定方程的 \(r\) 为 \(\dfrac {(r_2-r_1)}{\gcd(m_1,m_2)} + r_1\) , \(m\) 为 \(\dfrac {m_1m_2}{\gcd(m_1,m_2)}\)
再继续往下合并
最后我们可以合并成唯一一个式子 \(x \equiv r(mod \ m)\)
则 \(x\) 的最小整数解为 $ x = ( r \ mod \ m + m ) \ mod \ m $
（ \(r \ mod \ m+m\) 中加 \(m\) 是为了防止出现 \(r\) 为负数的情况）
标签：剩余,gcd,dfrac,定理,km,EXCRT,mod,1m,式子 From： https://www.cnblogs.com/jueqingfeng/p/17483395.html