Chinese Remainder Theorem (intro)

2.5.10 · Maths › Number Theory (Intermediate)

Chinese Remainder Theorem Kya Hai?

"Unique solution modulo $M$" ka matlab kya hai? Range $0\le x<M$ mein exactly ek solution $x$ hota hai, aur baaki saare solutions usme $M$ ke multiples add karke milte hain.

CRT Kaam Kyun Karta Hai? (First Principles)

WHY: Coprimality Hi Asli Cheez Hai

Moduli coprime kyun hone chahiye?

Agar $\gcd (m_1,m_2)=d>1$ ho, toh dono congruences $x\mathrm{mod}d$ par restrictions lagate hain. Yeh restrictions conflict kar sakti hain:

• $x\equiv 1(\mathrm{mod}4)$ aur $x\equiv 2(\mathrm{mod}6)$ conflict karte hain kyunki pehla $x$ ko odd force karta hai, doosra $x$ ko even force karta hai.

Jab moduli coprime hote hain, unke "constraints" independent hote hain — koi overlap nahi, koi conflict nahi.

HOW: Solution Banana

Hum solution step-by-step do congruences ke liye banate hain, phir generalize karte hain.

Problem: Solve karo

x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \end{cases}$$ jahan $\gcd(m_1, m_2) = 1$. **Step 1: Pehla congruence kya bata raha hai?** $x \equiv a_1 \pmod{m_1}$ ka matlab hai $x = a_1 + k m_1$ kisi integer $k$ ke liye. **Step 2: Doosre congruence mein substitute karo** $$a_1 + k m_1 \equiv a_2 \pmod{m_2}$$ $$k m_1 \equiv a_2 - a_1 \pmod{m_2}$$ **Step 3: $k$ ke liye solve karo** Kyunki $\gcd(m_1, m_2) = 1$ hai, integer $m_1$ ka ek ==multiplicative inverse== modulo $m_2$ exist karta hai, use $m_1^{-1}$ kaho (jo Extended Euclidean Algorithm se milta hai). Toh: $$k \equiv (a_2 - a_1) \cdot m_1^{-1} \pmod{m_2}$$ Toh $k = (a_2 - a_1) \cdot m_1^{-1} + j m_2$ kisi integer $j$ ke liye. **Step 4: Wapas substitute karo** $$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$$ Last term $j m_1 m_2$ ka matlab hai $x$ modulo $M = m_1 m_2$ determine hota hai: $$x \equiv a_1 + (a_2 - a_1) \cdot (m_1^{-1} \text{ mod } m_2) \cdot m_1 \pmod{m_1 m_2}$$ **Yeh kaam kyun karta hai**: Humne $x$ ko construction se pehla congruence satisfy karne ke liye force kiya ($x = a_1 + km_1$), phir $k$ ko doosra satisfy karne ke liye choose kiya. Coprimality guarantee karti hai ki inverse exist karta hai aur solution modulo $M$ unique hai. ## General CRT Construction Formula > [!formula] CRT Solution (Constructive Method) > System $x \equiv a_i \pmod{m_i}$, $i = 1, \ldots, k$ ke liye coprime $m_i$ ke saath: > > 1. $M = m_1 \cdot m_2 \cdot \ldots \cdot m_k$ compute karo > 2. Har $i$ ke liye, $M_i = M / m_i$ compute karo ($m_i$ ko chhodkar baaki sabhi moduli ka product) > 3. Har $i$ ke liye, $y_i = M_i^{-1} \bmod m_i$ find karo ($M_i$ ka modulo $m_i$ inverse) > 4. Solution hai: > $$x \equiv \sum_{i=1}^{k} a_i M_i y_i \pmod{M}$$ **Yeh formula kaam kyun karta hai**: - $M_i = M/m_i$ sabhi $m_j$ se divisible hai jahan $j \neq i$, isliye $M_i \equiv 0 \pmod{m_j}$ jab $j \neq i$ - Lekin $\gcd(M_i, m_i) = 1$, toh $M_i$ ka ek inverse $y_i$ modulo $m_i$ hota hai - Term $a_i M_i y_i$ satisfy karta hai: yeh $\equiv a_i \pmod{m_i}$ hai (kyunki $M_i y_i \equiv 1 \pmod{m_i}$) aur $\equiv 0 \pmod{m_j}$ hai jab $j \neq i$ - In terms ka sum exactly $x \equiv a_i \pmod{m_i}$ deta hai har $i$ ke liye ## Worked Examples > [!example] Example 1: Do Congruences > Solve karo: > $$\begin{cases} > x \equiv 2 \pmod{3} \\ > x \equiv 3 \pmod{5} > \end{cases}$$ > > **Step 1**: Coprimality check karo. $\gcd(3, 5) = 1$. ✓ > **Step 2**: $M = 3 \cdot 5 = 15$ compute karo > > **Step 3**: $M_1 = 15/3 = 5$ aur $M_2 = 15/5 = 3$ compute karo > > **Step 4**: Inverses find karo: > - $M_1 = 5$ modulo $m_1 = 3$: Chahiye $5 \cdot y_1 \equiv 1 \pmod{3}$. Kyunki $5 \equiv 2 \pmod{3}$, chahiye $2y_1 \equiv 1 \pmod{3}$. Try karo: $2 \cdot 2 = 4 \equiv 1 \pmod{3}$. Toh $y_1 = 2$. > - $M_2 = 3$ modulo $m_2 = 5$: Chahiye $3 \cdot y_2 \equiv 1 \pmod{5}$. Try karo: $3 \cdot 2 = 6 \equiv 1 \pmod{5}$. Toh $y_2 = 2$. > **Yeh inverses kyun find karte hain?** Yeh "scaling factors" hain jo har term ko $i$-th congruence mein exactly $a_i$ contribute karate hain aur baaki ko $0$. > > **Step 5**: Formula apply karo: > $$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}$, toh $x \in \{8, 23, 38, 53, \ldots\}$ > [!example] Example 2: Teen Congruences > Solve karo: > $$\begin{cases} > x \equiv 1 \pmod{2} \\ > x \equiv 2 \pmod{3} \\ > x \equiv 3 \pmod{5} > \end{cases}$$ > > **Step 1**: Coprimality check karo. $\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**: Inverses find karo: > - $15 \cdot y_1 \equiv 1 \pmod{2}$: Kyunki $15 \equiv 1 \pmod{2}$, $y_1 = 1$. > - $10 \cdot y_2 \equiv 1 \pmod{3}$: Kyunki $10 \equiv 1 \pmod{3}$, $y_2 = 1$. > - $6 \cdot y_3 \equiv 1 \pmod{5}$: Kyunki $6 \equiv 1 \pmod{5}$, $y_3 = 1$. > > **Yeh saare inverses 1 kyun hain?** Lucky coincidence! Har $M_i$ $\equiv 1 \pmod{m_i}$ hota hai. > > **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: Coprimality Requirement Bhool Jaana > **Galat approach**: "Main CRT kisi bhi system of congruences par apply kar dunga." > **Kyun sahi lagta hai**: Formula mechanical lagta hai, jaise hamesha kaam karna chahiye. > > **Trap**: Dekho: > $$\begin{cases} > x \equiv 1 \pmod{4} \\ > x \equiv 3 \pmod{6} > \end{cases}$$ > > $\gcd(4, 6) = 2 \neq 1$. Pehla kehta hai $x$ odd hai, doosra kehta hai $x$ odd hai. Abhi tak theek hai. Lekin agar $x \equiv 2 \pmod{4}$ aur $x \equiv 3 \pmod{6}$ hote, toh **contradiction** hoti (even vs. odd). > > **Fix**: > 1. Hamesha check karo $\gcd(m_i, m_j) = 1$ sabhi pairs ke liye. > 2. Agar coprime nahi hain, toh **generalized CRT** use karo (is intro note se aage): solutions tabhi exist karte hain jab $a_i \equiv a_j \pmod{\gcd(m_i, m_j)}$ sabhi pairs ke liye. > 3. Galti ko aur deeply samjho: Inverses ka formula $M_i^{-1} \bmod m_i$ literally **fail** ho jaata hai jab $\gcd(M_i, m_i) > 1$ hota hai, jo tab hota hai jab moduli factors share karte hain. > [!mistake] Common Mistake: Inverse Galat Compute Karna > **Galat approach**: "$5\bmod 7$ ka inverse $1/5 \approx 0.2$ hai." > > **Kyun sahi lagta hai**: Division notation se ordinary division ka suggestion milta hai. > > **Trap**: Modular inverse ka matlab hai $y$ find karna jaise $5y \equiv 1 \pmod{7}$, jo $y = 3$ hai (kyunki $5 \cdot 3 = 15 = 2 \cdot 7 + 1$). Real division integers modulo $m$ par apply nahi hoti. > > **Fix**: Extended Euclidean Algorithm use karo ya chhote moduli ke liye trial-and-check karo. Yaad rakho: $a^{-1} \bmod m$ woh number $y$ hai jahan $ay \equiv 1 \pmod{m}$. ## Active Recall Flashcards #flashcards/maths What does the Chinese Remainder Theorem guarantee? :: Congruences $x \equiv a_i \pmod{m_i}$ ke system ke liye pairwise coprime moduli ke saath, $M = \prod m_i$ modulo ek unique solution exist karta hai. Why must the moduli be coprime in CRT? ::: Agar $\gcd(m_i, m_j) > 1$ ho, toh congruences $x$ modulo unke GCD par conflicting constraints impose kar sakti hain, aur inverses ka formula kaam nahi karta. In CRT construction, what is $M_i$? ::: $M_i = M / m_i$, yaani $m_i$ ko chhodkar baaki sabhi moduli ka product. Yeh $j \neq i$ ke liye $\equiv 0 \pmod{m_j}$ hota hai lekin $m_i$ se coprime hota hai. What is the role of $y_i = M_i^{-1} \bmod m_i$ in CRT? ::: $y_i$ woh inverse hai jo $M_i y_i \equiv 1 \pmod{m_i}$ banata hai, toh term $a_i M_i y_i$ $i$-th congruence mein exactly $a_i$ contribute karta hai aur baaki mein $0$. How do you verify a CRT solution? ::: $x$ ko har original congruence $x \equiv a_i \pmod{m_i}$ mein substitute karo aur division se remainder check karo. If $x \equiv 2 \pmod{5}$ and $x \equiv 3 \pmod{7}$, what is the range of the unique solution? ::: Unique solution $[0, 35)$ mein hoga kyunki $M = 5 \cdot 7 = 35$. > [!recall]- CRT Ko Ek 12 Saal Ke Bachche Ko Samjhao > Socho tumhare paas ek secret number hai, lekin main tumhe directly nahi bataunga. Bajaye iske, main tumhe clues deta hoon: > - Jab tum ise 3 se divide karo, remainder 2 aata hai. > - Jab tum ise 5 se divide karo, remainder 3 aata hai. > Chinese Remainder Theorem ek detective ke tool ki tarah hai jo kehta hai: "Yeh clues kaafi hain! 0 aur 14 ke beech (kyunki $3 \times 5 = 15$) exactly ek number hai jo dono clues fit karta hai." > > Hum ek special recipe use karte hain: > 1. Pehle clue ke liye, hum ek aisa number banate hain jo "5 ka multiple" ho (taki doosra clue disturb na ho) lekin 3 se divide karne par remainder 2 de. > 2. Doosre clue ke liye, hum ek aisa number banate hain jo "3 ka multiple" ho (taki pehla clue disturb na ho) lekin 5 se divide karne par remainder 3 de. > 3. Unhe add karo, aur bas — secret number mil gaya! > > Yeh kaam karta hai kyunki 3 aur 5 koi common factors share nahi karte (woh "coprime" hain), isliye unke clues ek doosre ko interfere nahi karte. Agar woh factors share karte, toh clues ek doosre se contradict kar sakte the, jaise yeh kehna ki "number even bhi hai aur odd bhi." > [!mnemonic] CRT Yaad Karo > **"Coprime Moduli → Recipe Turns Independent remainders into unique Solution"** > - **C**oprime moduli zaroori hain > - **R**ecipe: $M$, $M_i$, $y_i$ compute karo, phir $a_i M_i y_i$ sum karo > - **T**urns multiple remainder clues > - **I**nto a unique solution modulo $M$ > - **S**olution $[0, M)$ mein exist karta hai ## Connections - [[Modular Arithmetic Basics]] — CRT congruences aur modular inverses use karta hai - [[Extended Euclidean Algorithm]] — $M_i^{-1} \bmod m_i$ compute karne ke liye use hota hai - [[Bezout's Identity]] — Guarantee karta hai ki inverse exist karta hai jab $\gcd(M_i, m_i) = 1$ - [[Systems of Linear Congruences]] — CRT coprime moduli ke liye solution method hai - [[RSA Cryptography]] — CRT decryption ko speed up karta hai primes modulo alag-alag kaam karke - [[Fermat's Little Theorem]] — Primes modulo inverses find karne ka alternative tarika --- *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 ```