How to use the Chinese Remainder Theorem for solving systems of congruences?

**Constructive Solution Method:** For the system $x \equiv a_i \pmod{m_i}$ with $m_i$ pairwise coprime: 1. Compute $M = \prod m_i$. 2. For each $i$: $M_i = M / m_i$. 3. Find $y_i$ such that $M_i y_i \equiv 1 \pmod{m_i}$ (modular inverse). 4. Solution: $x \equiv \sum a_i M_i y_i \pmod{M}$. **Example: $x \equiv 2 \pmod{3}$, $x \equiv 3 \pmod{5}$, $x \equiv 2 \pmod{7}$.** $M = 3 \cdot 5 \cdot 7 = 105$. \begin{array}{c|c|c|c} i & m_i & M_i & y_i \\ \hline 1 & 3 & 35 & 35 \cdot 2 \equiv 70 \equiv 1 \pmod{3} \Rightarrow y_1 = 2 \\ 2 & 5 & 21 & 21 \cdot 1 \equiv 21 \equiv 1 \pmod{5} \Rightarrow y_2 = 1 \\ 3 & 7 & 15 & 15 \cdot 1 \equiv 15 \equiv 1 \pmod{7} \Rightarrow y_3 = 1 \end{array} $$x \equiv 2 \cdot 35 \cdot 2 + 3 \cdot 21 \cdot 1 + 2 \cdot 15 \cdot 1 = 140 + 63 + 30 = 233 \equiv 23 \pmod{105}$$ **Verification:** $23 \equiv 2 \pmod{3}$, $23 \equiv 3 \pmod{5}$, $23 \equiv 2 \pmod{7}$ ✓ **CRT in RSA Decryption:** Instead of computing $m \equiv c^d \pmod{n}$ (modulus $n = pq$), compute: $$m_p \equiv c^d \pmod{p}, \quad m_q \equiv c^d \pmod{q}$$ Then use CRT to combine, achieving approximately 4x speedup since exponents are modulo $p-1$ and $q-1$ (much smaller than $d$). **Non-coprime Moduli:** If $\gcd(m_i, m_j) > 1$, consistency condition: $a_i \equiv a_j \pmod{\gcd(m_i, m_j)}$. Solutions exist iff all pairwise conditions hold, and the solution is unique modulo $\text{lcm}(m_1, \ldots, m_k)$. **CRT for Rings:** If $I$ and $J$ are ideals of a commutative ring $R$ with $I + J = R$, then $R/(I \cap J) \cong R/I \times R/J$. This is the ring-theoretic CRT.