The Chinese Remainder Theorem

Study Sheet

The Chinese Remainder Theorem

Solving systems of congruences

CRT

Concept
Independent moduli combine

If m1,…,mkm_1, \ldots, m_k are pairwise coprime, the system x≡ai(modmi)x \equiv a_i \pmod{m_i} has exactly one solution mod M=m1⋯mkM = m_1\cdots m_k. To find it: solve two at a time, substituting x=a1+m1tx = a_1 + m_1t into the second congruence and solving for tt.

The theorem says that knowing a number mod 33 and mod 55 is the same as knowing it mod 1515 — no more, no less. Write 0,…,140, \ldots, 14 in a table by their two remainders and every cell gets exactly one number. That is why problems about a composite modulus split into prime-power pieces (Euler's theorem on each, then reassemble), and why φ\varphi and τ\tau are multiplicative. It is also how a computer can do arithmetic on huge integers by working mod several small primes at once.

Example
Two congruences
0061239110171342511281401234columns: x mod 5 rows: x mod 3each of 0–14 sits in its own cell; 8 is row 2, column 3
Rows: x mod 3. Columns: x mod 5. Every cell holds exactly one number from 0 to 14.

Solve x≡2(mod3)x \equiv 2 \pmod 3, x≡3(mod5)x \equiv 3 \pmod 5. The first says x=2+3tx = 2 + 3t. Put that into the second: 2+3t≡32 + 3t \equiv 3, so 3t≡1(mod5)3t \equiv 1 \pmod 5, and 3⋅2=6≡13\cdot2 = 6 \equiv 1 gives t≡2t \equiv 2. Then x=2+3⋅2=8x = 2 + 3\cdot2 = 8, and the solution is x≡8(mod15)x \equiv 8 \pmod{15} — the single cell in row 22, column 33 of the table.

Example
Three congruences

x≡2(mod3)x \equiv 2 \pmod 3, x≡3(mod5)x \equiv 3 \pmod 5, x≡2(mod7)x \equiv 2 \pmod 7. The first two combine to x=8+15sx = 8 + 15s, as above. Mod 77: 8+15s≡1+s≡28 + 15s \equiv 1 + s \equiv 2, so s≡1s \equiv 1. x≡23(mod105)x \equiv 23 \pmod{105}. Check: 23=7⋅3+2=4⋅5+3=3⋅7+223 = 7\cdot3 + 2 = 4\cdot5 + 3 = 3\cdot7 + 2. ✓

Example
Eggs in a basket

Counting eggs by 22s, 33s, 44s, 55s or 66s always leaves 11; by 77s leaves none. Fewest eggs? The first five conditions say x−1x - 1 is a multiple of lcm(2,3,4,5,6)=60\text{lcm}(2, 3, 4, 5, 6) = 60: x=60k+1x = 60k + 1. Mod 77: 60k+1≡4k+1≡060k + 1 \equiv 4k + 1 \equiv 0, so 4k≡64k \equiv 6, and 4−1≡24^{-1} \equiv 2 gives k≡12≡5k \equiv 12 \equiv 5. So x=301=43⋅7x = 301 = 43\cdot7.

Side note
Where it goes wrong

Keeping the number but dropping the family. After the first two congruences the answer is not "x=8x = 8" but "x=8+15sx = 8 + 15s for all ss"; replacing it by 88 alone and testing mod 77 (8≡1≠28 \equiv 1 \ne 2) wrongly suggests the system has no solution. Carry the modulus along until the last step.

Try it
Try it: CRT

Find the smallest positive xx with x≡1(mod4)x \equiv 1 \pmod 4 and x≡4(mod9)x \equiv 4 \pmod 9.

Show the answer

x=1+4tx = 1 + 4t; mod 99: 1+4t≡41 + 4t \equiv 4, 4t≡34t \equiv 3, and since 4−1≡74^{-1} \equiv 7 (28≡128 \equiv 1), t≡21≡3t \equiv 21 \equiv 3. x=13x = \mathbf{13}. Check: 13=3⋅4+1=9+413 = 3\cdot4 + 1 = 9 + 4. ✓

Moduli That Share a Factor

Concept
Consistency first

If the moduli share factors, the system x≡a1(modm1)x \equiv a_1 \pmod{m_1}, x≡a2(modm2)x \equiv a_2 \pmod{m_2} has a solution iff a1≡a2(modgcd⁡(m1,m2))a_1 \equiv a_2 \pmod{\gcd(m_1, m_2)}, and the solution is then unique mod lcm(m1,m2)\text{lcm}(m_1, m_2) — not mod m1m2m_1m_2.

Both congruences say something about x mod gcd⁡(m1,m2)x \bmod \gcd(m_1, m_2), and those two statements must agree. With m1=4m_1 = 4 and m2=6m_2 = 6, both moduli are even, so both congruences fix the parity of xx; the 4×64\times6 table has only 1212 reachable cells, the ones whose row and column have the same parity. The count 12=lcm(4,6)12 = \text{lcm}(4, 6) is the period of the combined pattern.

Example
A consistent pair
008411952621037311012345columns: x mod 6 rows: x mod 4only same-parity cells are ever reached
x mod 4 and x mod 6 must agree mod 2, so half of the 24 cells stay empty.

Solve x≡3(mod4)x \equiv 3 \pmod 4, x≡5(mod6)x \equiv 5 \pmod 6. Here gcd⁡(4,6)=2\gcd(4, 6) = 2, and 33 and 55 are both odd: consistent. From x=3+4tx = 3 + 4t: 3+4t≡5(mod6)3 + 4t \equiv 5 \pmod 6 gives 4t≡2(mod6)4t \equiv 2 \pmod 6, i.e. 2t≡1(mod3)2t \equiv 1 \pmod 3, so t≡2(mod3)t \equiv 2 \pmod 3. Then x=11+12sx = 11 + 12s: the answer is x≡11(mod12)x \equiv 11 \pmod{12}: the shaded cell in row 33, column 55 of the table of 0,…,110, \ldots, 11.

Example
A factor of 33 in common

Solve x≡1(mod6)x \equiv 1 \pmod 6, x≡4(mod9)x \equiv 4 \pmod 9. gcd⁡=3\gcd = 3, and 1≡4(mod3)1 \equiv 4 \pmod 3: consistent. x=1+6t≡4(mod9)x = 1 + 6t \equiv 4 \pmod 9 gives 6t≡3(mod9)6t \equiv 3 \pmod 9, i.e. 2t≡1(mod3)2t \equiv 1 \pmod 3, t≡2t \equiv 2. So x=13+18sx = 13 + 18s: x≡13(mod18)x \equiv 13 \pmod{18}. Check: 13=2⋅6+1=9+413 = 2\cdot6 + 1 = 9 + 4. ✓

Example
An inconsistent pair

Solve x≡2(mod4)x \equiv 2 \pmod 4, x≡3(mod6)x \equiv 3 \pmod 6. The first makes xx even, the second makes xx odd. No integer is both: no solution. The substitution method agrees: 2+4t≡3(mod6)2 + 4t \equiv 3 \pmod 6 asks for 4t≡1(mod6)4t \equiv 1 \pmod 6, impossible since gcd⁡(4,6)=2∤1\gcd(4, 6) = 2 \nmid 1.

Side note
Where it goes wrong

Claiming uniqueness mod the product when the moduli are not coprime. For x≡3(mod4)x \equiv 3 \pmod 4 and x≡5(mod6)x \equiv 5 \pmod 6 there are TWO solutions below 2424, namely 1111 and 2323: the answer repeats every lcm(4,6)=12\text{lcm}(4, 6) = 12, not every 2424.

Try it
Try it: shared factor

Solve x≡5(mod8)x \equiv 5 \pmod 8, x≡9(mod12)x \equiv 9 \pmod{12}.

Show the answer

gcd⁡(8,12)=4\gcd(8, 12) = 4, and 5≡9≡1(mod4)5 \equiv 9 \equiv 1 \pmod 4: consistent. x=5+8t≡9(mod12)x = 5 + 8t \equiv 9 \pmod{12} gives 8t≡4(mod12)8t \equiv 4 \pmod{12}, so 2t≡1(mod3)2t \equiv 1 \pmod 3 and t≡2t \equiv 2. x=21+24sx = 21 + 24s: x≡21(mod24)x \equiv \mathbf{21} \pmod{24}. Check: 21=2⋅8+5=12+921 = 2\cdot8 + 5 = 12 + 9. ✓

Computing with CRT

Concept
Split, solve, reassemble

To compute something mod a composite m=m1m2m = m_1m_2 with gcd⁡(m1,m2)=1\gcd(m_1, m_2) = 1, compute it mod m1m_1 and mod m2m_2 separately — often much easier, for instance by Fermat on each prime — and then combine the two remainders with CRT. The number of solutions of a polynomial congruence mod mm is the product of the numbers mod each coprime factor.

CRT says the pair (remainder mod m1m_1, remainder mod m2m_2) is a complete, faithful description of a residue mod mm, and it respects addition and multiplication. So any computation can be carried out in the two small worlds in parallel. Counting follows too: if f(x)≡0f(x) \equiv 0 has s1s_1 solutions mod m1m_1 and s2s_2 mod m2m_2, each pair of choices assembles into exactly one solution mod mm.

Example
3100 mod 353^{100} \bmod 35

Split 35=5⋅735 = 5\cdot7. Mod 55: 34≡13^4 \equiv 1 (Fermat), so 3100=(34)25≡13^{100} = (3^4)^{25} \equiv 1. Mod 77: 36≡13^6 \equiv 1 and 100=6⋅16+4100 = 6\cdot16 + 4, so 3100≡34=81≡43^{100} \equiv 3^4 = 81 \equiv 4. Combine x≡1(mod5)x \equiv 1 \pmod 5, x≡4(mod7)x \equiv 4 \pmod 7: the candidates ≡4(mod7)\equiv 4 \pmod 7 are 4,11,18,…4, 11, 18, \ldots, and 11≡1(mod5)11 \equiv 1 \pmod 5. So 3100≡11(mod35)3^{100} \equiv 11 \pmod{35}.

Example
Last three digits of 210002^{1000}

Mod 1000=8⋅1251000 = 8\cdot125. Mod 88: 21000≡02^{1000} \equiv 0. Mod 125125: gcd⁡(2,125)=1\gcd(2, 125) = 1 and φ(125)=100\varphi(125) = 100, so 21000=(2100)10≡12^{1000} = (2^{100})^{10} \equiv 1. Combine x≡0(mod8)x \equiv 0 \pmod 8, x≡1(mod125)x \equiv 1 \pmod{125}: try 1,126,251,3761, 126, 251, 376 — the first multiple of 88 is 376=8⋅47376 = 8\cdot47. So 210002^{1000} ends in 376376.

Example
Square roots of 11 mod 1515
0061239110171342511281401234columns: x mod 5 rows: x mod 3rows 1, 2 meet columns 1, 4 in four cells
The four cells with x ≡ ±1 mod 3 and x ≡ ±1 mod 5: the square roots of 1 mod 15.

Solve x2≡1(mod15)x^2 \equiv 1 \pmod{15}. Mod 33 the solutions are x≡±1x \equiv \pm1 (two), and mod 55 also x≡±1x \equiv \pm1 (two), so there are 2⋅2=42\cdot2 = 4 solutions mod 1515, one for each pair of signs: (1,1)→1(1, 1) \to 1, (1,−1)→4(1, -1) \to 4, (−1,1)→11(-1, 1) \to 11, (−1,−1)→14(-1, -1) \to 14. Check: 42=16≡14^2 = 16 \equiv 1 and 112=121=8⋅15+111^2 = 121 = 8\cdot15 + 1. A prime modulus allows only ±1\pm1; a composite one allows more.

Side note
Where it goes wrong

Applying Euler to the whole modulus when the base is not coprime to it. "φ(1000)=400\varphi(1000) = 400, so 21000=2400⋅2+200≡22002^{1000} = 2^{400\cdot2 + 200} \equiv 2^{200}" is unjustified, since gcd⁡(2,1000)≠1\gcd(2, 1000) \ne 1. Splitting off the factor 88, where the power of 22 is simply 00, is what makes the computation legitimate.

Try it
Try it: roots of 11

Find all xx with 0≤x<210 \le x < 21 and x2≡1(mod21)x^2 \equiv 1 \pmod{21}.

Show the answer

Mod 33: x≡±1x \equiv \pm1; mod 77: x≡±1x \equiv \pm1 (since 77 is prime). Four combinations: x≡1x \equiv 1; x≡1(mod3),−1(mod7)x \equiv 1 \pmod 3, -1 \pmod 7 gives 1313; x≡−1(mod3),1(mod7)x \equiv -1 \pmod 3, 1 \pmod 7 gives 88; and x≡20x \equiv 20. Solutions 1,8,13,20\mathbf{1, 8, 13, 20}; check 82=64=3⋅21+18^2 = 64 = 3\cdot21 + 1.

Why It Works

Consider the map from residues mod MM to kk-tuples of residues (x mod m1,…,x mod mk)(x \bmod m_1, \ldots, x \bmod m_k). It is injective: if two residues agree mod every mim_i, each mim_i divides their difference, and since the mim_i are pairwise coprime so does their product MM — so the residues are equal mod MM. Both sides have exactly MM elements (MM residues; m1m2⋯mkm_1m_2\cdots m_k tuples), and an injection between finite sets of the same size is a bijection. Hence every tuple of remainders is hit exactly once: existence and uniqueness together, with no formula needed.