扩展中国剩余定理（EXCRT，Extended Chinese remainder theorem）用于求解如下形式的一元线性同余方程组：

不同于普通中国剩余定理，扩展版本中不要求 $m_1,m_2,\dots,m_n$ 两两互质。

推导

我们先来考虑两个方程的情况：

把同余式写成不定方程的形式：

移项，使其变为关于 $p$ 和 $q$ 的丢番图方程的形式：

接着就可以套用[[EXCRT]]中解这种不定方程的方法，根据[[裴蜀定理]]，若 $\gcd(m_1,m_2)\nmid a_2-a_1$ 则无解，其余情况下，我们可以解出一组 $(p,q)$ ，使 $p$ 为最小非负整数值，这时 $x=m_1p+a_1$ 就为该方程组的最小非负整数解，注意到给 $x$ 加上任意数量的 $\mathrm{lcm}(m_1,m_2)$ 方程依然满足，所以可以把方程组的解写为：

把刚刚的方法看作“合并了两个同余式”，则对于多个方程的方程组，我们按照这样两两合并就可以了。 因此我们能归纳出以下的算法：

• 对于 $1$ 到 $n-1$ 的第 $i$ 条方程，执行：
  • 应用EXGCD求解 $m_ip-m_{i+1}q=a_{i+1}-a_i$ ，若无解则同余方程组无解，否则求出满足方程的最小非负整数 $p$
  • 修改第 $i+1$ 条同余方程：
    • $a_{i+1}\leftarrow m_ip+a_i$
    • $m_{i+1}\leftarrow \mathrm{lcm}(m_i,m_{i+1})$
• 最后的 $p$ 即为答案