Chinese Remainder Theorem

数论视角

设 p 和 q 是互素的两个正整数, n = pq。对任意的 a ∈ Zp 和 b ∈ Zq,存在唯一解 x,0 ≤ x < n 使得:

• x ≡ a (mod p)
• x ≡ b (mod q)
  且 $x=aq{q}^{-1}+bp{p}^{-1}(\mathrm{mod}n)$

n 个数下推广：有 n 个互素的模数 $m_0\cdots m_{n-1}$, 解为 $x={\Sigma }_{i=0}^{n-1}{a}_i{b}_i{b}_i^{-1}(\mathrm{mod}M)$
Where $b_i=\frac{M}{m_i}$, $b_i^{-1}{b}_i\equiv 1(\mathrm{mod}{m}_i)$, $M={\prod }_{i=0}^{n-1}{m}_i$

代数视角

$n=pq$, p and q coprime, ${\mathbb{Z}}_n\cong {\mathbb{Z}}_p\times {\mathbb{Z}}_q$ and ${\mathbb{Z}}_n^{\ast }\cong {\mathbb{Z}}_p^{\ast }\times {\mathbb{Z}}_q^{\ast }$