中国剩余定理

中国剩余定理处理一个整数同时满足几个余数条件的情形。若模数 $m,n$ 互素，那么任意给定的余数 $r,s$ 都对应唯一的模 $mn$ 剩余类，使 $$x\equiv r(\mathrm{mod}m),x\equiv s(\mathrm{mod}n).$$ 这里的“唯一”是指任何两个解相差 $mn$ 的倍数，不是说整数解只有一个。

从两个日程周期合并

求 $x\equiv 2(\mathrm{mod}3)$、$x\equiv 3(\mathrm{mod}5)$。先写 $x=2+3k$，代入第二式得到 $3k\equiv 1(\mathrm{mod}5)$。因为 $3\cdot 2\equiv 1(\mathrm{mod}5)$，有 $k\equiv 2(\mathrm{mod}5)$，于是 $x=8+15t$。检验 8 除以 3 余 2，除以 5 余 3。

互素条件的工作

贝祖等式使互素模数各自的模逆元存在，因而上面的代入总能解出一个剩余类。若 $x,y$ 是两个解，则 $m\mid (x-y)$ 且 $n\mid (x-y)$；互素保证 $mn\mid (x-y)$，得到唯一性。

模数不互素时，任意余数未必相容。例如 $x\equiv 2(\mathrm{mod}4)$ 要求 $x$ 为偶数，而 $x\equiv 3(\mathrm{mod}6)$ 要求 $x$ 为奇数，不可能同时满足。一般判据是两个余数之差能被 $gcd(m,n)$ 整除；相容时解按最小公倍数重复。多模数版本可逐次合并，但每次都需核查相应条件。

参考资料

• MIT，Mathematics for Computer Science，Number Theory 章节。
• MIT 18.781，初等数论讲义。
• 继续阅读：同余、模逆元、最小公倍数。