中國剩餘定理

中國剩餘定理 (Chinese remainder theorem):模數 $m_1,\dots,m_k$ 兩兩互質,則同餘方程組 $x\equiv a_i\pmod{m_i}$ 在 $\bmod M = \prod m_i$ 下有唯一解。《孫子算經》的「物不知數」:三三數之剩二,五五數之剩三,七七數之剩二,答 23。

兩種解法:(1) 逐步代入——寫 $x = a_1 + m_1t$ 代入第二式解 $t$;(2) 構造公式 $x = \sum a_iM_iy_i$,$M_i = M/m_i$、$y_i$ 是 $M_i$ 模 $m_i$ 的反元素。

算例:$x\equiv2\pmod3$、$x\equiv3\pmod5$:$x = 2 + 3t$,$3t\equiv1\pmod5$,兩邊乘 3 的模 5 反元素 2 得 $t\equiv2$,$x = 8$。

CRT 的結構意義是:$\gcd(m,n) = 1$ 時有環同構 $\mathbb{Z}_{mn}\cong\mathbb{Z}_m\times\mathbb{Z}_n$——大模數的計算可以拆成小模數平行做,RSA 解密加速、多項式快速乘法、秘密分享都用它。