Chinese Remainder Theorem (intro)

What Is the Chinese Remainder Theorem?

What does "unique solution modulo $M$" mean? There's exactly one solution $x$ in the range $0 \leq x < M$, and all other solutions differ from it by multiples of $M$.

Why Does CRT Work? (First Principles)

The WHY: Coprimality Is Key

Why must the moduli be coprime?

If $\gcd(m_1, m_2) = d > 1$, then both congruences impose restrictions on $x \bmod d$. These restrictions might conflict:

• $x \equiv 1 \pmod{4}$ and $x \equiv 2 \pmod{6}$ conflict because the first forces $x$ odd, the second forces $x$ even.

When moduli are coprime, their "constraints" are independent — no overlap, no conflict.

The HOW: Constructing the Solution

We build the solution step-by-step for two congruences, then generalize.

Problem: Solve

x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \end{cases}$$ where $\gcd(m_1, m_2) = 1$. **Step 1: What does the first congruence tell us?** $x \equiv a_1 \pmod{m_1}$ means $x = a_1 + k m_1$ for some integer $k$. **Step 2: Substitute into the second congruence** $$a_1 + k m_1 \equiv a_2 \pmod{m_2}$$ $$k m_1 \equiv a_2 - a_1 \pmod{m_2}$$ **Step 3: Solve for $k$** Since $\gcd(m_1, m_2) = 1$, the integer $m_1$ has a ==multiplicative inverse== modulo $m_2$, call it $m_1^{-1}$ (found via Extended Euclidean Algorithm). Then: $$k \equiv (a_2 - a_1) \cdot m_1^{-1} \pmod{m_2}$$ So $k = (a_2 - a_1) \cdot m_1^{-1} + j m_2$ for some integer $j$. **Step 4: Substitute back** $$x = a_1 + \left[(a_2 - a_1) \cdot m_1^{-1} + j m_2\right] m_1$$ $$x = a_1 + (a_2 - a_1) \cdot m_1^{-1} \cdot m_1 + j m_1 m_2$$ The last term $j m_1 m_2$ means $x$ is determined modulo $M = m_1 m_2$: $$x \equiv a_1 + (a_2 - a_1) \cdot (m_1^{-1} \text{ mod } m_2) \cdot m_1 \pmod{m_1 m_2}$$ **Why this works**: We forced $x$ to satisfy the first congruence by construction ($x = a_1 + km_1$), then chose $k$ to satisfy the second. Coprimality guarantees the inverse exists and the solution is unique modulo $M$. ## The General CRT Construction Formula > [!formula] CRT Solution (Constructive Method) > For the system $x \equiv a_i \pmod{m_i}$, $i = 1, \ldots, k$ with coprime $m_i$: > > 1. Compute $M = m_1 \cdot m_2 \cdot \ldots \cdot m_k$ > 2. For each $i$, compute $M_i = M / m_i$ (the product of all moduli except $m_i$) > 3. For each $i$, find $y_i = M_i^{-1} \bmod m_i$ (the inverse of $M_i$ modulo $m_i$) > 4. The solution is: > $$x \equiv \sum_{i=1}^{k} a_i M_i y_i \pmod{M}$$ **Why this formula works**: - $M_i = M/m_i$ is divisible by all $m_j$ for $j \neq i$, so $M_i \equiv 0 \pmod{m_j}$ when $j \neq i$ - But $\gcd(M_i, m_i) = 1$, so $M_i$ has an inverse $y_i$ modulo $m_i$ - The term $a_i M_i y_i$ satisfies: it's $\equiv a_i \pmod{m_i}$ (because $M_i y_i \equiv 1 \pmod{m_i}$) and $\equiv 0 \pmod{m_j}$ for $j \neq i$ - Suming these terms gives exactly $x \equiv a_i \pmod{m_i}$ for each $i$ ## Worked Examples > [!example] Example 1: Two Congruences > Solve: > $$\begin{cases} > x \equiv 2 \pmod{3} \\ > x \equiv 3 \pmod{5} > \end{cases}$$ > > **Step 1**: Check coprimality. $\gcd(3, 5) = 1$. ✓ > **Step 2**: Compute $M = 3 \cdot 5 = 15$ > > **Step 3**: Compute $M_1 = 15/3 = 5$ and $M_2 = 15/5 = 3$ > > **Step 4**: Find inverses: > - $M_1 = 5$ modulo $m_1 = 3$: We need $5 \cdot y_1 \equiv 1 \pmod{3}$. Since $5 \equiv 2 \pmod{3}$, we need $2y_1 \equiv 1 \pmod{3}$. Trying: $2 \cdot 2 = 4 \equiv 1 \pmod{3}$. So $y_1 = 2$. > - $M_2 = 3$ modulo $m_2 = 5$: We need $3 \cdot y_2 \equiv 1 \pmod{5}$. Trying: $3 \cdot 2 = 6 \equiv 1 \pmod{5}$. So $y_2 = 2$. > **Why find these inverses?** They're the "scaling factors" that make each term contribute exactly $a_i$ to the $i$-th congruence and $0$ to others. > > **Step 5**: Apply the formula: > $$x \equiv a_1 M_1 y_1 + a_2 M_2 y_2 \equiv 2 \cdot 5 \cdot 2 + 3 \cdot 3 \cdot 2 \pmod{15}$$ > $$x \equiv 20 + 18 \equiv 38 \equiv 8 \pmod{15}$$ > > **Verification**: > - $8 = 2 \cdot 3 + 2 \equiv 2 \pmod{3}$. ✓ > - $8 = 1 \cdot 5 + 3 \equiv 3 \pmod{5}$. ✓ > **Answer**: $x \equiv 8 \pmod{15}$, so $x \in \{8, 23, 38, 53, \ldots\}$ > [!example] Example 2: Three Congruences > Solve: > $$\begin{cases} > x \equiv 1 \pmod{2} \\ > x \equiv 2 \pmod{3} \\ > x \equiv 3 \pmod{5} > \end{cases}$$ > > **Step 1**: Check coprimality. $\gcd(2,3) = \gcd(2,5) = \gcd(3,5) = 1$. ✓ > > **Step 2**: $M = 2 \cdot 3 \cdot 5 = 30$ > **Step 3**: > - $M_1 = 30/2 = 15$ > - $M_2 = 30/3 = 10$ > - $M_3 = 30/5 = 6$ > > **Step 4**: Find inverses: > - $15 \cdot y_1 \equiv 1 \pmod{2}$: Since $15 \equiv 1 \pmod{2}$, $y_1 = 1$. > - $10 \cdot y_2 \equiv 1 \pmod{3}$: Since $10 \equiv 1 \pmod{3}$, $y_2 = 1$. > - $6 \cdot y_3 \equiv 1 \pmod{5}$: Since $6 \equiv 1 \pmod{5}$, $y_3 = 1$. > > **Why are all these inverses 1?** Lucky coincidence! Each $M_i$ happens to be $\equiv 1 \pmod{m_i}$. > > **Step 5**: > $$x \equiv 1 \cdot 15 \cdot 1 + 2 \cdot 10 \cdot 1 + 3 \cdot 6 \cdot 1 \pmod{30}$$ > $$x \equiv 15 + 20 + 18 \equiv 53 \equiv 23 \pmod{30}$$ > > **Verification**: > - $23 = 11 \cdot 2 + 1 \equiv 1 \pmod{2}$. ✓ > - $23 = 7 \cdot 3 + 2 \equiv 2 \pmod{3}$. ✓ > - $23 = 4 \cdot 5 + 3 \equiv 3 \pmod{5}$. ✓ > > **Answer**: $x \equiv 23 \pmod{30}$ > [!mistake] Common Mistake: Forgetting the Coprimality Requirement > **Wrong approach**: "I'll just apply CRT to any system of congruences." > **Why it feels right**: The formula looks mechanical, like it should always work. > > **The trap**: Consider: > $$\begin{cases} > x \equiv 1 \pmod{4} \\ > x \equiv 3 \pmod{6} > \end{cases}$$ > > $\gcd(4, 6) = 2 \neq 1$. The first says $x$ is odd, the second says $x$ is odd. So far okay. But if we had $x \equiv 2 \pmod{4}$ and $x \equiv 3 \pmod{6}$, we'd have a **contradiction** (even vs. odd). > > **The fix**: > 1. Always check $\gcd(m_i, m_j) = 1$ for all pairs. > 2. If not coprime, use the **generalized CRT** (beyond this intro note): solutions exist only if $a_i \equiv a_j \pmod{\gcd(m_i, m_j)}$ for all pairs. > 3. Steel-man the mistake: The formula for inverses $M_i^{-1} \bmod m_i$ literally **fails** when $\gcd(M_i, m_i) > 1$, which happens when moduli share factors. > [!mistake] Common Mistake: Computing Inverse Incorrectly > **Wrong approach**: "The inverse of $5\bmod 7$ is $1/5 \approx 0.2$." > > **Why it feels right**: Division notation suggests ordinary division. > > **The trap**: Modular inverse means finding $y$ such that $5y \equiv 1 \pmod{7}$, which is $y = 3$ (since $5 \cdot 3 = 15 = 2 \cdot 7 + 1$). Real division doesn't apply to integers modulo $m$. > > **The fix**: Use Extended Euclidean Algorithm or trial-and-check for small moduli. Remember: $a^{-1} \bmod m$ is the number $y$ where $ay \equiv 1 \pmod{m}$. ## Active Recall Flashcards #flashcards/maths What does the Chinese Remainder Theorem guarantee? :: For a system of congruences $x \equiv a_i \pmod{m_i}$ with pairwise coprime moduli, there exists a unique solution modulo $M = \prod m_i$. Why must the moduli be coprime in CRT? ::: If $\gcd(m_i, m_j) > 1$, the congruences might impose conflicting constraints on $x$ modulo their GCD, and the formula for inverses breaks down. In CRT construction, what is $M_i$? ::: $M_i = M / m_i$, the product of all moduli except $m_i$. It's $\equiv 0 \pmod{m_j}$ for $j \neq i$ but coprime to $m_i$. What is the role of $y_i = M_i^{-1} \bmod m_i$ in CRT? ::: $y_i$ is the inverse that makes $M_i y_i \equiv 1 \pmod{m_i}$, so the term $a_i M_i y_i$ contributes exactly $a_i$ to the $i$-th congruence and $0$ to others. How do you verify a CRT solution? ::: Substitute $x$ into each original congruence $x \equiv a_i \pmod{m_i}$ and check the remainder by division. If $x \equiv 2 \pmod{5}$ and $x \equiv 3 \pmod{7}$, what is the range of the unique solution? ::: The unique solution lies in $[0, 35)$ since $M = 5 \cdot 7 = 35$. > [!recall]- Explain CRT to a 12-Year-Old > Imagine you have a secret number, but I won't tell it to you directly. Instead, I give you clues: > - When you divide it by 3, the remainder is 2. > - When you divide it by 5, the remainder is 3. > The Chinese Remainder Theorem is like a detective's tool that says: "These clues are enough! There's exactly one number between 0 and 14 (because $3 \times 5 = 15$) that fits both clues." > > We use a special recipe: > 1. For the first clue, we build a number that's a "multiple of 5" (so it doesn't mess up the second clue) but leaves remainder 2 when divided by 3. > 2. For the second clue, we build a number that's a "multiple of 3" (so it doesn't mess up the first clue) but leaves remainder 3 when divided by 5. > 3. Add them up, and boom—you've found the secret number! > > It works because 3 and 5 share no common factors (they're "coprime"), so their clues don't interfere with each other. If they did share factors, the clues might contradict each other, like saying "the number is both even and odd." > [!mnemonic] Remember CRT > **"Coprime Moduli → Recipe Turns Independent remainders into unique Solution"** > - **C**oprime moduli are required > - **R**ecipe: compute $M$, $M_i$, $y_i$, then sum $a_i M_i y_i$ > - **T**urns multiple remainder clues > - **I**nto a unique solution modulo $M$ > - **S**olution exists in $[0, M)$ ## Connections - [[Modular Arithmetic Basics]] — CRT uses congruences and modular inverses - [[Extended Euclidean Algorithm]] — Used to compute $M_i^{-1} \bmod m_i$ - [[Bezout's Identity]] — Guarantees inverse exists when $\gcd(M_i, m_i) = 1$ - [[Systems of Linear Congruences]] — CRT is the solution method for coprime moduli - [[RSA Cryptography]] — CRT speeds up decryption by working modulo primes separately - [[Fermat's Little Theorem]] — Alternative way to find inverses modulo primes --- *Last updated: 2026-07-01* ## 🖼️ Concept Map ```mermaid flowchart TD CRT[Chinese Remainder Theorem] CONG[System of congruences] COP[Pairwise coprime moduli] UNIQUE[Unique solution mod M] M[M equals product of mi] CONFLICT[Conflicting constraints] INV[Multiplicative inverse mod m2] EEA[Extended Euclidean Algorithm] CONSTRUCT[Constructed solution x] APP[Cryptography and RSA] CRT -->|solves| CONG CONG -->|requires| COP COP -->|guarantees| UNIQUE UNIQUE -->|defined over| M COP -->|prevents| CONFLICT COP -->|ensures existence of| INV INV -->|found via| EEA INV -->|used to build| CONSTRUCT CONSTRUCT -->|satisfies| CONG CRT -->|applied in| APP ``` ## 🔊 Hinglish (regional understanding) > [!intuition]- Hinglish mein samjho > Chinese Remainder Theorem ek powerful tool hai jo modular arithmetic mein use hota hai. Maan lo tumhare pas ek secret number hai, par tumhe directly nahi pata. Bas tumhe kuch clues mile hain - jaise ki "jab 3 se divide karo toh remainder 2 ata hai" aur "jab 5 se divide karo toh remainder 3 aata hai". CRT kehta hai ki agar yeh divisors coprime hain (matlab unka GCD = 1), toh sirf ek unique number hoga jo 0 se lekar (3×5-1) = 14 tak range mein inn dono conditions ko satisfy karega. > > Construction formula thoda technical hai par logic simple hai. Hum do parts banate hain:ek part jo pehli condition satisfy kare (aur dusri condition ko disturb na kare kyunki woh dusre modulus ka multiple hai), aur dosra part jo dusri condition satisfy kare. Dono parts ko add karte hain toh exact solution mil jata hai. Yeh technique bahut useful hai - RSA encryption mein, parallel computing mein, aur calendar calculations mein bhi use hoti hai. Key point yad rakho: moduli must be coprime, warna formula kaam nahi karega aur contradictions aa sakte hain. ![[audio/2.5.10-Chinese-Remainder-Theorem-(intro).mp3]]