📋 Prerequisites

• Modular Arithmetic Basics
• Advanced Modular (inverses)

The Chinese Remainder Theorem (CRT) solves systems of simultaneous congruences. "Find a number that leaves remainder 2 when divided by 3, remainder 3 when divided by 5, and remainder 2 when divided by 7." This is the classic Sun Zi problem from ancient China. CRT tells us when solutions exist and how to find them.

📚 Key Concepts

The Chinese Remainder Theorem (Standard Form)

If $ m_1, m_2, ..., m_k $ are pairwise coprime (gcd of any two is 1), then for any integers $ a_1, a_2, ..., a_k $, the system:

\[ \begin{cases} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\ \quad \vdots \\ x \equiv a_k \pmod{m_k} \end{cases} \]

has a unique solution modulo $ M = m_1 m_2 ... m_k $.

Two key takeaways:

• Existence: solution always exists when moduli are pairwise coprime
• Uniqueness: all solutions are congruent mod M

Constructive Proof / Formula

Let $ M = m_1 m_2 ... m_k $ and $ M_i = M / m_i $ (product of all moduli except $m_i$).

Since moduli are pairwise coprime, gcd($M_i, m_i$) = 1, so $M_i$ has an inverse mod $m_i$. Call it $y_i$.

Then the solution is:

\[ x \equiv a_1 M_1 y_1 + a_2 M_2 y_2 + ... + a_k M_k y_k \pmod{M} \]

Why it works: each term $a_i M_i y_i$ is congruent to $a_i$ mod $m_i$ (since $M_i y_i \equiv 1$ mod $m_i$), and congruent to 0 mod every other $m_j$ (since $M_i$ contains $m_j$ as a factor).

Successive Substitution Method

Often easier for small systems. Solve two congruences at a time:

1. \(Start with first congruence: write x = a_{1} + m_{1} \\cdot t\)
2. \(Substitute into second congruence: a_{1} + m_{1} \\cdot t \\equiv a_{2} (mod m_{2})\)
3. \(Solve for t: m_{1} \\cdot t \\equiv a_{2} - a_{1} (mod m_{2})\)
4. Find t, then write new combined congruence
5. Repeat with next congruence

This works even when moduli aren't coprime (as long as a solution exists).

Non-Coprime Moduli

When moduli aren't pairwise coprime, a solution exists iff for every pair i, j:

\[ a_i \equiv a_j \pmod{\gcd(m_i, m_j)} \]

If the congruences are consistent on the overlapping parts, there's a unique solution mod \(lcm(m_{1}, m_{2},\) ..., m_k).

\(If inconsistent (e.g., x \\equiv 1 mod 2 and x \\equiv 2 mod 4), no solution exists.\)

CRT as a Ring Isomorphism (for context)

CRT means $ \mathbb{Z}/M\mathbb{Z} \cong \mathbb{Z}/m_1\mathbb{Z} \times ... \times \mathbb{Z}/m_k\mathbb{Z} $ \(when the m_{i} are pairwise coprime.\)

\(In plain language: working mod M is equivalent to working mod each m_{i} separately, component by component.\)

This is why multiplicative functions factor over prime powers — because the ring splits into independent pieces.

Applications

• Solving systems of congruences — classic number theory problems
• Breaking big mod problems into small ones — compute mod 2, mod 3, mod 5 separately, then combine with CRT
• RSA cryptography — CRT speeds up decryption
• Counting solutions — \(number of solutions mod M = product of solutions mod each m_{i}\)

How to Approach CRT Problems

1. Check consistency: \(For non-coprime moduli, verify a_{i} \(\\equiv a\)_{j} mod gcd(m_{i}, m_{j})\)
2. Choose method:
   • \(2 congruences, small numbers \\to successive substitution (easiest)\)
   • \(3+ congruences, coprime moduli \\to CRT formula\)
   • \(Non-coprime \\to successive substitution, checking consistency at each step\)
3. Verify: Plug your answer back into every original congruence

✏️ Example Problems