Day 78 — Chinese Remainder Theorem

Updated

July 30, 2026

Day 78 — Chinese Remainder Theorem

Stage VII · concept day
Goal: Solve systems \(x\equiv a\pmod m\), \(x\equiv b\pmod n\) when \(\gcd(m,n)=1\); constructive proof; general pairwise coprime systems; non-coprime consistency; applications (secret sharing lite, calendars).

Why this matters

CRT is the structural theorem that \(\mathbb{Z}/mn\mathbb{Z}\cong\mathbb{Z}/m\mathbb{Z}\times\mathbb{Z}/n\mathbb{Z}\) when \(m,n\) coprime. It speeds modular computations (RSA CRT decryption literacy), reconstructs integers from residues, and appears in scheduling and secret-sharing puzzles. Constructive CRT is also a clean inverse application.

Note

No labs. Hand solutions of small systems. No coding of big-integer CRT.

Theory

Two congruences, coprime moduli

Theorem (CRT, two equations). Let \(m,n>0\) with \(\gcd(m,n)=1\). For any integers \(a,b\), the system \[ \begin{cases} x\equiv a\pmod m\\ x\equiv b\pmod n \end{cases} \] has a solution, and the solution is unique modulo \(mn\).

Constructive proof / algorithm.

  1. Since \(\gcd(m,n)=1\), there exists \(m^{-1}\bmod n\), i.e. \(y\) with \(my\equiv 1\pmod n\).
  2. Set \[ x_0 = a + m\bigl((b-a)y\bmod n\bigr). \] More symmetrically: find \(u,v\) with \(mu+nv=1\) (Bézout). Then \[ x_0 = a\,nv + b\,mu \] satisfies both congruences because \(nv\equiv 1\pmod m\) and \(mu\equiv 1\pmod n\).
  3. Standard explicit form: \[ x = \sum_i a_i M_i y_i, \] for two moduli \(M=mn\), \(M_1=n\), \(M_2=m\), \(y_1\equiv M_1^{-1}\pmod m\), \(y_2\equiv M_2^{-1}\pmod n\), \(a_1=a\), \(a_2=b\): \[ x_0 = a\, n\, (n^{-1}\bmod m) + b\, m\, (m^{-1}\bmod n). \]
  4. General solution: \(x=x_0 + mnt\), \(t\in\mathbb{Z}\).

Verification. \(x_0\equiv a\cdot n\cdot n^{-1}\equiv a\pmod m\) (second term has factor \(m\)). Similarly mod \(n\).

Uniqueness

If \(x,x'\) both solve the system, then \(m\mid(x-x')\) and \(n\mid(x-x')\), so \(mn\mid(x-x')\) when \(\gcd(m,n)=1\).

General pairwise coprime system

Theorem. Let \(m_1,\ldots,m_k\) be pairwise coprime (\(\gcd(m_i,m_j)=1\) for \(i\neq j\)). Let \(M=\prod m_i\). The system \[ x\equiv a_i\pmod{m_i},\qquad i=1,\ldots,k \] has a unique solution modulo \(M\).

Construction. Let \(M_i=M/m_i\). Then \(\gcd(M_i,m_i)=1\); let \(y_i\equiv M_i^{-1}\pmod{m_i}\). Set \[ x_0=\sum_{i=1}^k a_i M_i y_i. \] Then \(x_0\equiv a_j\pmod{m_j}\) for each \(j\), and solutions are \(x_0+Mt\).

Non-coprime moduli

Theorem (consistency). The system \(x\equiv a\pmod m\), \(x\equiv b\pmod n\) has a solution iff \[ a\equiv b\pmod{\gcd(m,n)}. \] If solvable, the solution is unique modulo \(\mathrm{lcm}(m,n)\).

Proof idea. Necessity: if \(x=a+mt=b+ns\), then \(a-b=ns-mt\), so \(\gcd(m,n)\mid(a-b)\). Sufficiency: divide through by \(d=\gcd(m,n)\) and apply coprime CRT to moduli \(m/d,n/d\) carefully, or solve \(a+mt\equiv b\pmod n\) as a linear congruence in \(t\).

Ring isomorphism literacy

When \(\gcd(m,n)=1\), the map \[ \mathbb{Z}/mn\mathbb{Z}\to \mathbb{Z}/m\mathbb{Z}\times\mathbb{Z}/n\mathbb{Z},\qquad x\bmod mn\mapsto (x\bmod m,\, x\bmod n) \] is a ring isomorphism. CRT is surjectivity + injectivity of this map.

Applications

Calendar / scheduling. “\(x\equiv 2\pmod 3\), \(x\equiv 3\pmod 5\), \(x\equiv 2\pmod 7\)” — classic Sun Tzu problem style; \(M=105\).

Secret sharing lite (idea). A secret \(s\) in a range can be packaged as residues mod coprime moduli; enough residues reconstruct \(s\) via CRT if \(s<M\). (Real secret sharing uses Shamir polynomials — awareness; this is only the residue-reconstruction idea.)

RSA CRT decryption (literacy). Compute \(c^d\bmod p\) and \(c^d\bmod q\) separately, recombine via CRT — faster exponentiation in practice. No implementation today.

Simultaneous range constraints. Finding \(n\) with given remainders (e.g. packing, cyclic scheduling).

Worked examples

Example 1 — Classic two-modulus.
Solve \(x\equiv 2\pmod 3\), \(x\equiv 3\pmod 5\).
\(M=15\), \(M_1=5\), \(y_1\equiv 5^{-1}\equiv 2\pmod 3\) (\(5\equiv 2\), \(2\cdot 2=4\equiv 1\)).
\(M_2=3\), \(y_2\equiv 3^{-1}\equiv 2\pmod 5\) (\(3\cdot 2=6\equiv 1\)).
\(x_0=2\cdot 5\cdot 2 + 3\cdot 3\cdot 2=20+18=38\equiv 8\pmod{15}\).
Check: \(8\equiv 2\pmod 3\), \(8\equiv 3\pmod 5\). ✓

Example 2 — Bézout form.
\(3u+5v=1\): \(u=2\), \(v=-1\). Then \(x=a\cdot 5\cdot(-1)?\) Wait — use \(x=a(1-3u)+b(3u)\) carefully… Prefer the standard sum form to avoid sign errors; verify by substitution.

Example 3 — Three moduli.
\(x\equiv 1\pmod 2\), \(x\equiv 2\pmod 3\), \(x\equiv 3\pmod 5\).
\(M=30\), \(M_1=15\), \(M_2=10\), \(M_3=6\).
\(y_1\equiv 15^{-1}\equiv 1^{-1}\equiv 1\pmod 2\).
\(y_2\equiv 10^{-1}\equiv 1^{-1}\equiv 1\pmod 3\).
\(y_3\equiv 6^{-1}\equiv 1^{-1}\equiv 1\pmod 5\).
\(x_0=1\cdot 15\cdot 1 + 2\cdot 10\cdot 1 + 3\cdot 6\cdot 1=15+20+18=53\equiv 23\pmod{30}\).
Check: \(23\) odd; \(23\equiv 2\pmod 3\); \(23\equiv 3\pmod 5\). ✓

Example 4 — Non-coprime solvable.
\(x\equiv 4\pmod 6\), \(x\equiv 10\pmod{15}\). \(\gcd(6,15)=3\), \(4\equiv 1\), \(10\equiv 1\pmod 3\) — consistent.
Solutions mod \(\mathrm{lcm}(6,15)=30\). Try: \(x=10\) works? \(10\equiv 4\pmod 6\)? \(10-4=6\) yes; \(10\equiv 10\pmod{15}\). So \(x\equiv 10\pmod{30}\).

Example 5 — Non-coprime impossible.
\(x\equiv 1\pmod 6\), \(x\equiv 2\pmod{15}\). \(1\not\equiv 2\pmod 3\). No solution.

Example 6 — Linear congruence via CRT idea.
Solve \(x\equiv 3\pmod 4\), \(x\equiv 5\pmod 7\). \(M=28\).
\(x=3+4t\equiv 5\pmod 7\) ⇒ \(4t\equiv 2\pmod 7\). Multiply by inverse of \(4\) mod \(7\) (\(4\cdot 2=8\equiv 1\), inv \(=2\)): \(t\equiv 4\pmod 7\). \(t=4+7s\), \(x=3+4(4+7s)=19+28s\).

Example 7 — Counting solutions.
Number of residue classes mod \(30\) satisfying \(x\equiv 1\pmod 2\) and \(x\equiv 1\pmod 3\): equivalent to \(x\equiv 1\pmod 6\), so \(30/6=5\) classes mod \(30\).

Example 8 — Calendar.
\(x\equiv 2\pmod 3\), \(x\equiv 3\pmod 5\), \(x\equiv 2\pmod 7\).
Note first and third: \(x\equiv 2\pmod{21}\) if CRT on \(3,7\) (coprime). Then \(x=2+21k\equiv 3\pmod 5\) ⇒ \(21k\equiv 1\pmod 5\) ⇒ \(k\equiv 1\pmod 5\) because \(21\equiv 1\). \(k=1+5t\), \(x=23+105t\). Classic answer \(23\) mod \(105\).

Exercises

A. Two coprime moduli

  1. Solve \(x\equiv 1\pmod 4\), \(x\equiv 2\pmod 5\).
  2. Solve \(x\equiv 3\pmod 5\), \(x\equiv 2\pmod 7\).
  3. Solve \(x\equiv 0\pmod 4\), \(x\equiv 1\pmod 9\).
  4. Prove uniqueness mod \(mn\) when \(\gcd(m,n)=1\).
  5. Find \(x\) with \(x\equiv -1\pmod{11}\), \(x\equiv -1\pmod{13}\). Interpret.

B. Construction details

  1. For moduli \(8\) and \(9\), compute \(M_i\), \(y_i\) and solve \(x\equiv 3\pmod 8\), \(x\equiv 5\pmod 9\).
  2. Solve using the method of successive substitution (Example 6 style): \(x\equiv 4\pmod 7\), \(x\equiv 3\pmod{10}\).
  3. Verify that \(x_0=\sum a_i M_i y_i\) satisfies \(x_0\equiv a_j\pmod{m_j}\) in general (write the argument).
  4. Find the inverse of \(M_1=15\) mod \(m_1=4\) for a \(2\cdot 3\cdot 5\) style system with first modulus \(4\) — wait, use \(m_1=4,m_2=3,m_3=5\) and \(a_i=1\) all; solve \(x\equiv 1\pmod{60}\)? Actually \(x\equiv 1\) mod each means \(x\equiv 1\pmod{60}\).

C. Three or more

  1. Solve \(x\equiv 1\pmod 3\), \(x\equiv 2\pmod 4\), \(x\equiv 3\pmod 5\).
  2. Solve \(x\equiv 2\pmod 3\), \(x\equiv 3\pmod 5\), \(x\equiv 2\pmod 7\) (Example 8 without looking).
  3. How many solutions mod \(210\) to \(x\equiv 1\pmod 2\), \(x\equiv 1\pmod 3\), \(x\equiv 1\pmod 5\), \(x\equiv 1\pmod 7\)?

D. Non-coprime

  1. Determine solvability: \(x\equiv 7\pmod{12}\), \(x\equiv 11\pmod{18}\).
  2. Same: \(x\equiv 7\pmod{12}\), \(x\equiv 13\pmod{18}\).
  3. Solve (if possible) \(x\equiv 6\pmod{10}\), \(x\equiv 16\pmod{15}\).
  4. Prove necessity of \(a\equiv b\pmod{\gcd(m,n)}\).
  5. State the uniqueness modulus when solvable.

E. Applications and stretch

  1. Secret sharing lite: moduli \(5,7,8\) (pairwise coprime), secret \(s=13\). Publish \(s\bmod 5\), \(s\bmod 7\), \(s\bmod 8\). Reconstruct via CRT.
  2. Scheduling: a task every \(6\) days on residue \(1\), and another constraint every \(7\) days on residue \(3\) — find day numbers.
  3. RSA literacy: explain in 4–6 sentences why decrypting mod \(p\) and mod \(q\) then CRT is equivalent to decrypting mod \(n\).
  4. Prove the ring map \(\mathbb{Z}/mn\mathbb{Z}\to\mathbb{Z}/m\times\mathbb{Z}/n\) is injective when \(\gcd(m,n)=1\).
  5. Stretch: solve \(x\equiv 3\pmod 4\), \(x\equiv 5\pmod 6\) after checking consistency.
  6. Stretch: general system \(x\equiv a_i\pmod{m_i}\) not pairwise coprime — outline a strategy using lcm and successive equations.

Deep dive — algorithm card (pairwise coprime)

Input: (a_i, m_i) for i=1..k, pairwise coprime m_i
M ← product of all m_i
for each i:
    M_i ← M / m_i
    y_i ← inverse of M_i modulo m_i   // extended Euclid
x0 ← sum_i a_i * M_i * y_i
return x0 mod M

Complexity literacy. \(k\) inverses of size related to \(m_i\); for hand work \(k\le 4\) and small moduli.

Deep dive — non-coprime solver

To solve \(x\equiv a\pmod m\), \(x\equiv b\pmod n\) when \(d=\gcd(m,n)\mid(a-b)\):

  1. Write \(x=a+mt\).
  2. \(a+mt\equiv b\pmod n\) ⇒ \(mt\equiv b-a\pmod n\).
  3. Divide equation and modulus by \(d\): \((m/d)t\equiv (b-a)/d\pmod{n/d}\).
  4. Invert \(m/d\) mod \(n/d\) (now coprime), solve for \(t\), substitute.
  5. Solutions unique mod \(\mathrm{lcm}(m,n)=mn/d\).

Additional worked examples

Example 9 — Four moduli.
\(x\equiv 1\pmod 2\), \(x\equiv 1\pmod 3\), \(x\equiv 1\pmod 5\), \(x\equiv 1\pmod 7\) ⇒ \(x\equiv 1\pmod{210}\).

Example 10 — Successive substitution.
\(x\equiv 2\pmod 5\), \(x\equiv 3\pmod 7\), \(x\equiv 2\pmod 3\).
From first: \(x=5s+2\). Into second: \(5s+2\equiv 3\pmod 7\) ⇒ \(5s\equiv 1\pmod 7\). Inv of \(5\) mod \(7\) is \(3\): \(s\equiv 3\pmod 7\), \(s=7t+3\), \(x=35t+17\).
Into third: \(35t+17\equiv 2\pmod 3\) ⇒ \(2t+2\equiv 2\pmod 3\) ⇒ \(2t\equiv 0\pmod 3\) ⇒ \(t\equiv 0\pmod 3\).
\(t=3u\), \(x=105u+17\). Check: \(17\bmod 5=2\), \(17\bmod 7=3\), \(17\bmod 3=2\).

Example 11 — Isomorphism count.
Number of pairs \((u\bmod m,v\bmod n)\) is \(mn\); number of classes mod \(mn\) is \(mn\) — bijection when coprime.

Example 12 — Inconsistent.
\(x\equiv 1\pmod 4\), \(x\equiv 0\pmod 6\): \(\gcd(4,6)=2\), \(1\not\equiv 0\pmod 2\). Impossible.

Example 13 — RSA CRT decrypt literacy.
\(d_p=d\bmod(p-1)\), compute \(m_p=c^{d_p}\bmod p\), \(m_q=c^{d_q}\bmod q\), recombine — same \(m\) as \(c^d\bmod n\), fewer bit operations for large \(n\).

More exercises

  1. Solve \(x\equiv 4\pmod 7\), \(x\equiv 5\pmod 8\), \(x\equiv 6\pmod 9\).
  2. Prove: if \(x\equiv a\pmod m\) and \(x\equiv a\pmod n\) and \(\gcd(m,n)=1\) then \(x\equiv a\pmod{mn}\).
  3. Find all \(x\bmod 60\) with \(x\equiv 3\pmod 4\) and \(x\equiv 5\pmod 3\).
  4. Secret sharing lite: residues \(s\equiv 2\pmod 5\), \(s\equiv 3\pmod 7\), \(s\equiv 2\pmod 8\); reconstruct \(s\bmod 280\).
  5. For \(m=12,n=18\), characterize all \((a,b)\) for which the system is solvable.
  6. CS: two cyclic timers period \(12\) and \(35\); when do they fire together if offsets given?
  7. Verify Example 10’s answer \(17\) mod \(105\).

Selected mini-solutions

  1. \(x\equiv 6\pmod{20}\) (check: \(6\equiv 1\pmod 4?\) wait \(6\equiv 2\) — recompute: \(x=4k+1\equiv 2\pmod 5\) ⇒ \(4k\equiv 1\pmod 5\), inv \(4\) is \(4\), \(k\equiv 4\), \(x=17\equiv 17\pmod{20}\)).
  2. \(x\equiv -1\pmod{143}\).
  3. Check \(5\equiv 11\pmod 3\)? \(5\equiv 2\), \(11\equiv 2\) yes; solve carefully.
  4. \(s=13\): residues \(3,6,5\); CRT reconstructs \(13\).

Common pitfalls

Pitfall Fix
Applying coprime formula when \(\gcd>1\) Check consistency first
Forgetting to reduce \(y_i=M_i^{-1}\bmod m_i\) Inverse is mod \(m_i\), not mod \(M\)
Uniqueness mod \(m\) or \(n\) only Uniqueness mod product (coprime case)
Arithmetic errors in \(M_i y_i\) Verify each congruence at the end
Pairwise vs overall coprimality Need pairwise for standard product theorem
Skipping verification Always plug back

Study notes — CRT decision tree

Two congruences x≡a (mod m), x≡b (mod n):
  d = gcd(m,n)
  if d does not divide (a-b): impossible
  if d = 1: unique mod mn; construct via M_i y_i
  if d > 1: unique mod lcm(m,n)=mn/d; use successive substitution
k pairwise coprime moduli: unique mod product; standard sum formula

Synthesis — CRT workout

S1. Solve \(x\equiv 3\pmod 8\), \(x\equiv 5\pmod 9\) by the formula; verify.

S2. Solve \(x\equiv 1\pmod 5\), \(x\equiv 2\pmod 6\), \(x\equiv 3\pmod 7\).

S3. Prove uniqueness mod \(mn\) when \(\gcd(m,n)=1\).

S4. Decide solvability of \(x\equiv 4\pmod{15}\), \(x\equiv 10\pmod{21}\); if yes, solve.

S5. Show \(x\equiv a\pmod m\) and \(x\equiv a\pmod n\) with coprime \(m,n\) ⇒ \(x\equiv a\pmod{mn}\).

S6. Secret sharing lite: reconstruct from \(s\equiv 1\pmod 4\), \(s\equiv 2\pmod 5\), \(s\equiv 3\pmod 7\).

S7. RSA CRT decrypt: explain equivalence in 5 sentences.

S8. Successive substitution on \(x\equiv 2\pmod 3\), \(x\equiv 3\pmod 5\), \(x\equiv 2\pmod 7\).

Checkpoint

  • Can solve two-congruence CRT constructively
  • Can run the general pairwise formula
  • Can test non-coprime consistency
  • Can prove uniqueness mod \(mn\) when coprime
  • Can narrate one application (calendar / RSA CRT / residues)
  • Exercises A–D done; synthesis attempted

Two personal takeaways:

  1. …
  2. …

Deeper theory — isomorphism view (why CRT is structural)

Map. \(\Psi:\mathbb{Z}/mn\mathbb{Z}\to\mathbb{Z}/m\mathbb{Z}\times\mathbb{Z}/n\mathbb{Z}\), \(\Psi([x]_{mn})=([x]_m,[x]_n)\).

Homomorphism. \(\Psi([x]+[y])=\Psi([x])+\Psi([y])\) and similarly for products — immediate from compatibility of congruences.

Injective when \(\gcd(m,n)=1\). If \(\Psi([x])=(0,0)\) then \(m\mid x\) and \(n\mid x\), so \(mn\mid x\) (coprime moduli). Kernel trivial.

Surjective. CRT existence: every pair \((a\bmod m,b\bmod n)\) is hit.

Moral. Solving systems is computing the inverse map \(\Psi^{-1}\). The formula \(x=\sum a_i M_i y_i\) is an explicit inverse.

Deeper theory — successive substitution always

Even for pairwise coprime systems, successive substitution is often less error-prone by hand than the big sum:

  1. Solve the first two congruences → one congruence mod \(m_1 m_2\).
  2. Incorporate the third mod \(m_3\), and so on.
  3. Verify at the end against every original congruence.

For non-coprime pairs, successive substitution plus the consistency check is the standard path.

Worked examples — more systems

Example 14 — \(x\equiv 3\pmod 8\), \(x\equiv 5\pmod 9\).
\(M=72\), \(M_1=9\), \(y_1\equiv 9^{-1}\equiv 1^{-1}\equiv 1\pmod 8\).
\(M_2=8\), \(y_2\equiv 8^{-1}\equiv (-1)^{-1}\equiv -1\equiv 8\pmod 9\)? \(8\cdot 8=64\equiv 1\pmod 9\) yes.
\(x_0=3\cdot 9\cdot 1+5\cdot 8\cdot 8=27+320=347\equiv 347-4\cdot 72=347-288=59\pmod{72}\).
Check: \(59\equiv 3\pmod 8\) (\(56+3\)), \(59\equiv 5\pmod 9\) (\(6\cdot 9=54\), rem \(5\)). ✓

Example 15 — Three moduli.
\(x\equiv 1\pmod 3\), \(x\equiv 2\pmod 4\), \(x\equiv 3\pmod 5\).
\(x=3t+1\equiv 2\pmod 4\) ⇒ \(3t\equiv 1\pmod 4\), inv of \(3\) is \(3\), \(t\equiv 3\pmod 4\), \(t=4s+3\), \(x=12s+10\).
\(12s+10\equiv 3\pmod 5\) ⇒ \(2s+0\equiv 3\pmod 5\) (\(10\equiv 0\)), \(2s\equiv 3\), inv of \(2\) is \(3\), \(s\equiv 9\equiv 4\pmod 5\).
\(s=5u+4\), \(x=12(5u+4)+10=60u+58\). So \(x\equiv 58\pmod{60}\).
Check: \(58\equiv 1\pmod 3\), \(58\equiv 2\pmod 4\), \(58\equiv 3\pmod 5\). ✓

Example 16 — Non-coprime solvable.
\(x\equiv 7\pmod{12}\), \(x\equiv 11\pmod{18}\). \(\gcd=6\), \(7\equiv 1\), \(11\equiv 5\pmod 6\) — inconsistent? \(1\not\equiv 5\). No solution.
Repair the exercise habit: always compute \(a-b\bmod d\) first. For \(x\equiv 7\pmod{12}\), \(x\equiv 13\pmod{18}\): \(7\equiv 1\), \(13\equiv 1\pmod 6\) — OK. Solve via \(x=12t+7\equiv 13\pmod{18}\) ⇒ \(12t\equiv 6\pmod{18}\). Divide by \(6\): \(2t\equiv 1\pmod 3\). Inv of \(2\) mod \(3\) is \(2\), \(t\equiv 2\pmod 3\), \(t=3s+2\), \(x=36s+31\). Mod \(\mathrm{lcm}(12,18)=36\).

Extra exercises — CRT drills

  1. Solve \(x\equiv 5\pmod 7\), \(x\equiv 3\pmod 8\).
  2. Solve \(x\equiv 2\pmod 5\), \(x\equiv 3\pmod 6\), \(x\equiv 4\pmod 7\).
  3. Prove injectivity of \(\Psi\) when \(\gcd(m,n)=1\).
  4. Characterize solvability for moduli \(10\) and \(15\).
  5. Reconstruct \(s\) from \(s\equiv 4\pmod 7\), \(s\equiv 1\pmod 8\), \(s\equiv 2\pmod 9\).
  6. Show \(x\equiv -1\pmod m\) and \(x\equiv -1\pmod n\) coprime ⇒ \(x\equiv -1\pmod{mn}\).
  7. RSA CRT literacy: write the three-line algorithm \(m_p,m_q\to m\bmod n\).
  8. Scheduling: \(x\equiv 0\pmod{12}\) and \(x\equiv 5\pmod{35}\) — solve or prove impossible.

Mini-solutions (selected)

  1. \(x=7k+5\equiv 3\pmod 8\) ⇒ \(7k\equiv -2\equiv 6\pmod 8\) ⇒ \(-k\equiv 6\) ⇒ \(k\equiv 2\pmod 8\) (since \(7\equiv -1\)); \(x=14+56t\equiv 14\pmod{56}\).
  2. Special case of “same residue mod each” ⇒ residue mod product.
  3. \(\gcd(12,35)=1\) always solvable; construct via formula.

Closing synthesis card

Task Method
Two coprime \(M_i y_i\) sum or substitution
\(k\) pairwise product modulus
Non-coprime \(d\mid(a-b)\); mod lcm
Verify plug into every congruence
Structure ring isomorphism literacy

Tomorrow

Day 79 — RNGs, LCGs, and randomness literacy.