Chinese Remainder Theorem

Apr 3, 2023

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

• x ≡ a (mod p)
• x ≡ b (mod q)
  且 $x = aqq^{-1} + bpp^{-1} \pmod{n}$

n 个数下推广：有 n 个互素的模数 $m_{0} \cdots m_{n-1}$, 解为 $x = \Sigma_{i=0}^{n-1} a_{i}b_{i}b_{i}^{-1} \pmod{M}$
Where $b_{i} = \frac{M}{m_{i}}$, $b_{i}^{-1}b_{i} \equiv 1 \pmod{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}^} \cong \mathbb{Z_{p}^} \times \mathbb{Z_{q}^*}$