整数中国剩余定理

两两互素的模数提供彼此独立的坐标。每个 $N_i{u}_i$ 在第 $i$ 个坐标等于一、在其余坐标等于零，像离散的坐标选择器。互素模数像彼此独立的坐标轴：一个剩余类在模 $n_i$ 的信息不会与其他坐标发生冲突。Bézout 等式构造出的系数在一个坐标上等于 $1$、在其余坐标上等于 $0$，于是可以像拼接坐标分量一样组装全局整数。唯一性则来自两个解的差同时被所有模数整除公理库整除Divisibility存在整数倍关系时定义的二元关系。。

$x\equiv 2(\mathrm{mod}3)$、$x\equiv 3(\mathrm{mod}5)$ 的解为 $x\equiv 8(\mathrm{mod}15)$。若模数不互素，方程组有解当且仅当 $a_i\equiv a_j(\mathrm{mod}gcd(n_i,n_j))$ 对所有 $i,j$ 成立；解若存在，模最小公倍数唯一。例如$x\equiv 0(\mathrm{mod}2)$ 与 $x\equiv 1(\mathrm{mod}4)$ 不相容。两两互素比“整体 gcd 为一”更强，三个模数整体 gcd 为一并不足以直接使用乘积模结论。显式公式中的逆元存在正因 $gcd(N_i,n_i)=1$。

求解

设 $x=1+4k$，则 $4k\equiv 1(\mathrm{mod}9)$；因为 $4^{-1}\equiv 7(\mathrm{mod}9)$，得 $k\equiv 7(\mathrm{mod}9)$，于是

若模数不互素，必须先检查兼容性。例如$x\equiv 1(\mathrm{mod}4)$ 与 $x\equiv 3(\mathrm{mod}6)$ 相容，因为二者模 $2$ 同余；解只在模 $\mathrm{lcm}(4,6)=12$ 意义下唯一。

CRT 用于大整数并行模运算、有限环分解、插值、秘密分享和密码实现加速。整数版本是 环的中国剩余定理公理库环上的中国剩余定理Chinese remainder theorem for rings两两互素理想的交商与对应商环直积之间存在规范同构。 的特例，并依赖 最大公因数公理库最大公约数Greatest common divisor · GCD同时整除两个整数且被所有公约数整除的非负整数。 与 Bézout 关系。它把大模数运算分解为小模数运算，用于多精度计算、RSA 私钥运算加速、同余方程计数以及有限环上的算法。