中国剩余定理（孙子、秦九韶）

存在性，第一步（构造零件）：对每个 $i$，定义 $M_i=M/m_i$（除 $m_i$ 外所有模的乘积）。由于各 $m_j$ 两两互素，$m_i$ 的任何素因子都不会出现在其他 $m_j$（$j\neq i$）中，故 $\gcd(M_i,m_i)=1$。由裴蜀等式（扩展欧几里得算法）可知存在整数 $y_i$——即 $M_i$ 模 $m_i$ 的逆元——满足 $M_iy_i\equiv1\pmod{m_i}$。

存在性，第二步（拼出解）：令 $x=\sum_{i=1}^{k}a_iM_iy_i\bmod M$。固定任意下标 $i$，把这个和式模 $m_i$ 化简。对每个 $j\neq i$，因子 $M_j=M/m_j$（由于 $i\neq j$）含有 $m_i$ 作为其因子之一，故 $m_i\mid M_j$，从而 $a_jM_jy_j\equiv0\pmod{m_i}$。只剩下第 $i$ 项：利用 $M_iy_i\equiv1\pmod{m_i}$，得 $x\equiv a_iM_iy_i\equiv a_i\cdot1=a_i\pmod{m_i}$。由于 $i$ 任意，$x$ 同时满足所有同余式 $x\equiv a_i\pmod{m_i}$。

模 $M$ 的唯一性：设另有整数 $x'$ 也满足所有 $x\equiv a_i\pmod{m_i}$。则对每个 $i$ 都有 $x-x'\equiv0\pmod{m_i}$，即每个 $m_i$ 都整除 $x-x'$。由于各 $m_i$ 两两互素，它们的最小公倍数等于其乘积 $M$，因此 $M\mid(x-x')$——两两互素的数的任何公倍数必定是其乘积的倍数。故 $x\equiv x'\pmod M$：解在模 $M$ 意义下唯一，正如所述。

小例验证：取 $m_1=3,m_2=5$，$a_1=2,a_2=3$，即方程组 $x\equiv2\pmod3,\ x\equiv3\pmod5$。此处 $M=15$；$M_1=5$ 需要 $5y_1\equiv1\pmod3$，即 $2y_1\equiv1\pmod3$，故 $y_1=2$；$M_2=3$ 需要 $3y_2\equiv1\pmod5$，故 $y_2=2$。于是 $x=2\cdot5\cdot2+3\cdot3\cdot2=20+18=38\equiv8\pmod{15}$，即 $x=8$。验证：$8=2\cdot3+2$ 模 $3$ 余 $2$，$8=1\cdot5+3$ 模 $5$ 余 $3$——两个同余式都成立，构造得证。