Chinese Remainder Theorem (intro): Worked examples

We will lean on three prerequisite ideas, so let us name them once:

Congruence $x \equiv a (mod m)$ means " $x$ and $a$ leave the same remainder when divided by $m$ " — equivalently, $m$ divides $x - a$ . (See Modular Arithmetic Basics.)
Modular inverse of $b$ modulo $m$ is the number $b^{- 1}$ with $b \cdot b^{- 1} \equiv 1 (mod m)$ . It exists exactly when $g cd (b, m) = 1$ , and we find it with the Extended Euclidean Algorithm (which is really Bezout's Identity in action).
Pairwise coprime moduli: every pair shares no common factor bigger than 1.
lcm ("least common multiple") of two numbers is the smallest positive integer that both divide into. For example $lcm (4, 6) = 12$ . When moduli are coprime, $lcm (m_{1}, m_{2}) = m_{1} m_{2}$ ; when they share a factor it is smaller. We only need it in the non-coprime cases (F below).

The one formula we will reuse

Every coprime example on this page runs the same five-step machine. Restate it once so we never apply it by rote.

The mnemonic for the five steps (Multiply–Divide–Invert–Add–Reduce) appears at the foot of the page.

Think of a CRT problem as a machine with dials. Each dial can be set to an "ordinary" position or an "edge" position. The table below lists every dial and its edge positions — and which example switches that dial.

#	Case class (the dial)	What is unusual	Example
A	Standard, two congruences	nothing — the baseline	Ex 1
B	Standard, three congruences	more equations, sum of three terms	Ex 2
C	A remainder is $0$	$a_{i} = 0$ : " $x$ divisible by $m_{i}$ "	Ex 3
D	Remainder $\geq$ modulus / negative	need to reduce $a_{i}$ first	Ex 4
E	Inverse is genuinely hard	must run Extended Euclid, not guess	Ex 5
F	Non-coprime, consistent	$g cd > 1$ but no conflict — the generalized case	Ex 6
G	Non-coprime, contradictory	no solution exists at all	Ex 7
H	Word problem (real world)	translate English into congruences	Ex 8
I	Exam twist (extra unknown)	find the value, given a range, not just the class	Ex 9

Every numeric answer below is machine-checked. Let us walk the map.

Case A — the baseline

Worked example Example 1 (Cell A): two congruences

Solve ${x \equiv 2 (mod 3) x \equiv 4 (mod 7)$

Forecast: guess a number that is $2$ more than a multiple of $3$ and $4$ more than a multiple of $7$ before reading on. (Try listing $4, 11, 18, 25, \dots$ and testing each mod $3$ .)

Step 1 — Check the moduli are coprime. $g cd (3, 7) = 1$ . ✓ Why this step? CRT's uniqueness and the inverses only work when moduli share no factor. If this failed we would be in Case F or G.

Step 2 — Total modulus. $M = 3 \cdot 7 = 21$ . Why? The answer will be unique in the window $0 \leq x < 21$ ; everything else is this answer plus multiples of $21$ .

Step 3 — Partial products $M_{i} = M / m_{i}$ . $M_{1} = 21/3 = 7$ , $M_{2} = 21/7 = 3$ . Why? $M_{1}$ is divisible by every modulus except $m_{1}$ , so its term will vanish in every congruence but the first — that is the whole trick.

Step 4 — Inverses $y_{i} = M_{i}^{- 1} mod m_{i}$ .

$7 y_{1} \equiv 1 (mod 3)$ . Since $7 \equiv 1$ , we need $y_{1} \equiv 1$ , so $y_{1} = 1$ .
$3 y_{2} \equiv 1 (mod 7)$ . Try $3 \cdot 5 = 15 \equiv 1$ , so $y_{2} = 5$ . Why? $M_{i} y_{i} \equiv 1$ makes the $i$ -th term contribute exactly $a_{i}$ , not $a_{i}$ times some stray factor.

Step 5 — Assemble. $x \equiv a_{1} M_{1} y_{1} + a_{2} M_{2} y_{2} = 2 \cdot 7 \cdot 1 + 4 \cdot 3 \cdot 5 = 14 + 60 = 74 \equiv 74 - 3 \cdot 21 = 11 (mod 21)$ Why this combination? By the on/off switch idea above: the term $2 \cdot 7 \cdot 1$ reads $2$ mod $3$ and $0$ mod $7$ ; the term $4 \cdot 3 \cdot 5$ reads $0$ mod $3$ and $4$ mod $7$ . Their sum therefore reads $2$ mod $3$ and $4$ mod $7$ — precisely the system.

Verify: $11 = 3 \cdot 3 + 2 \Rightarrow\equiv 2 (mod 3)$ ✓; $11 = 1 \cdot 7 + 4 \Rightarrow\equiv 4 (mod 7)$ ✓. Answer: $x \equiv 11 (mod 21)$ .

Reading the figure below (alt: a $3 \times 7$ grid of the numbers $0$ – $20$ ; the row is the remainder mod $3$ , the column the remainder mod $7$ ). Because $3$ and $7$ are coprime, every number $0$ – $20$ lands in a different cell — all $21$ cells are filled exactly once. Our first congruence " $x \equiv 2 (mod 3)$ " selects the pink row (remainder $2$ ); the second " $x \equiv 4 (mod 7)$ " selects the blue column (remainder $4$ ). They cross in exactly one cell, highlighted yellow, holding the number $11$ — the same $x$ our algebra produced. This is the geometric meaning of "unique solution modulo $21$ ": one row-times-column crossing per window.

Figure — Chinese Remainder Theorem (intro)

Case B — three congruences

Worked example Example 2 (Cell B): three at once

Solve $⎩ ⎨ ⎧ x \equiv 2 (mod 3) x \equiv 3 (mod 4) x \equiv 1 (mod 5)$

Forecast: the answer lives in $[0, 60)$ . Guess whether it is nearer $0$ or $60$ .

Step 1 — Coprime check. $g cd (3, 4) = g cd (3, 5) = g cd (4, 5) = 1$ ✓. Step 2 — $M = 3 \cdot 4 \cdot 5 = 60$ . Step 3 — Partial products. $M_{1} = 20, M_{2} = 15, M_{3} = 12$ . Why? Each drops exactly one modulus, so $M_{i}$ is divisible by the other two moduli. Step 4 — Inverses.

$20 y_{1} \equiv 1 (mod 3)$ : $20 \equiv 2$ , need $2 y_{1} \equiv 1$ , $y_{1} = 2$ .
$15 y_{2} \equiv 1 (mod 4)$ : $15 \equiv 3$ , need $3 y_{2} \equiv 1$ , $y_{2} = 3$ .
$12 y_{3} \equiv 1 (mod 5)$ : $12 \equiv 2$ , need $2 y_{3} \equiv 1$ , $y_{3} = 3$ . Step 5 — Assemble. $x \equiv 2 \cdot 20 \cdot 2 + 3 \cdot 15 \cdot 3 + 1 \cdot 12 \cdot 3 = 80 + 135 + 36 = 251 \equiv 251 - 4 \cdot 60 = 11 (mod 60)$ Why this combination? Same on/off switch idea, now with three switches: $2 \cdot 20 \cdot 2$ reads $2$ mod $3$ and $0$ mod $4, 5$ ; $3 \cdot 15 \cdot 3$ reads $3$ mod $4$ and $0$ mod $3, 5$ ; $1 \cdot 12 \cdot 3$ reads $1$ mod $5$ and $0$ mod $3, 4$ . The sum inherits one live remainder from each.

Verify: $11 \equiv 2 (mod 3)$ ✓; $11 \equiv 3 (mod 4)$ ✓; $11 \equiv 1 (mod 5)$ ✓. Answer: $x \equiv 11 (mod 60)$ — near the bottom of the window.

Case C — a remainder is zero

Case D — remainder too big or negative

Worked example Example 4 (Cell D): reduce

$a_{i}$ first Solve ${x \equiv 9 (mod 5) x \equiv - 1 (mod 6)$

Forecast: a remainder of $9$ modulo $5$ ? A negative remainder $- 1$ ? Neither is in the "normal" range $0 \leq a < m$ . What is the honest way to fix this?

Step 0 — Normalise the remainders.

$9 \equiv 9 - 5 = 4 (mod 5)$ , so the first line is really $x \equiv 4 (mod 5)$ .
$- 1 \equiv - 1 + 6 = 5 (mod 6)$ , so the second is $x \equiv 5 (mod 6)$ . Why this step? $\equiv$ only cares about the remainder; we may add or subtract the modulus freely. Doing this first stops arithmetic slips later. (This is pure Modular Arithmetic Basics.)

Step 1 — Coprime. $g cd (5, 6) = 1$ ✓. Step 2 — $M = 30$ . Step 3 — $M_{1} = 6, M_{2} = 5$ . Step 4 — Inverses.

$6 y_{1} \equiv 1 (mod 5)$ : $6 \equiv 1$ , $y_{1} = 1$ .
$5 y_{2} \equiv 1 (mod 6)$ : $5 \cdot 5 = 25 \equiv 1$ , $y_{2} = 5$ . Step 5 — Assemble (using the reduced remainders $4$ and $5$ ): $x \equiv 4 \cdot 6 \cdot 1 + 5 \cdot 5 \cdot 5 = 24 + 125 = 149 \equiv 149 - 4 \cdot 30 = 29 (mod 30)$ Why this combination? Each term is again a switch: $4 \cdot 6 \cdot 1$ reads $4$ mod $5$ and $0$ mod $6$ ; $5 \cdot 5 \cdot 5$ reads $5$ mod $6$ and $0$ mod $5$ . The sum reads the reduced remainders on each line.

Verify: $29 = 5 \cdot 5 + 4 \Rightarrow\equiv 4 \equiv 9 (mod 5)$ ✓; $29 = 4 \cdot 6 + 5 \Rightarrow\equiv 5 \equiv - 1 (mod 6)$ ✓. Answer: $x \equiv 29 (mod 30)$ .

Case E — the inverse needs Extended Euclid

Worked example Example 5 (Cell E): no lucky guess

Solve ${x \equiv 4 (mod 11) x \equiv 9 (mod 13)$

Forecast: the inverses here are not small. We will earn them with the Extended Euclidean Algorithm.

Step 1 — Coprime. $11, 13$ are distinct primes, $g cd = 1$ ✓. Step 2 — $M = 143$ . Step 3 — $M_{1} = 13, M_{2} = 11$ . Step 4 — Inverses by Extended Euclid.

Need $13 y_{1} \equiv 1 (mod 11)$ , i.e. $2 y_{1} \equiv 1 (mod 11)$ (since $13 \equiv 2$ ). Extended Euclid on $2, 11$ : $2 \cdot 6 = 12 = 11 + 1$ , so $2 \cdot 6 \equiv 1$ . Thus $y_{1} = 6$ .
Need $11 y_{2} \equiv 1 (mod 13)$ . Run Euclid: $13 = 1 \cdot 11 + 2, 11 = 5 \cdot 2 + 1$ . Back-substitute (this is Bezout's Identity): $1 = 11 - 5 \cdot 2 = 11 - 5 (13 - 11) = 6 \cdot 11 - 5 \cdot 13$ . So $11 \cdot 6 \equiv 1 (mod 13)$ , giving $y_{2} = 6$ . Why Extended Euclid and not trial? For a modulus like $13$ , guessing wastes time and hides errors. Euclid's back-substitution produces the Bezout combination $6 \cdot 11 - 5 \cdot 13 = 1$ , which is the inverse, provably.

Step 5 — Assemble. $x \equiv 4 \cdot 13 \cdot 6 + 9 \cdot 11 \cdot 6 = 312 + 594 = 906 \equiv 906 - 6 \cdot 143 = 906 - 858 = 48 (mod 143)$ Why this combination? The switch idea once more: $4 \cdot 13 \cdot 6$ reads $4$ mod $11$ (since $13 \cdot 6 \equiv 1$ ) and $0$ mod $13$ ; $9 \cdot 11 \cdot 6$ reads $9$ mod $13$ and $0$ mod $11$ . Their sum matches both lines.

Verify: $48 = 4 \cdot 11 + 4 \Rightarrow\equiv 4 (mod 11)$ ✓; $48 = 3 \cdot 13 + 9 \Rightarrow\equiv 9 (mod 13)$ ✓. Answer: $x \equiv 48 (mod 143)$ .

Case F — non-coprime but consistent

The intro note warned that the plain formula fails when moduli share a factor. But solutions can still exist — you just need the compatibility check. This is the generalized CRT.

Worked example Example 6 (Cell F): shared factor, still solvable

Solve ${x \equiv 3 (mod 4) x \equiv 5 (mod 6)$

Forecast: $g cd (4, 6) = 2$ . Both say $x$ is odd ( $3$ is odd mod $4$ , $5$ is odd mod $6$ ). Compatible? Guess yes — then find it.

Step 1 — Compatibility. $g = g cd (4, 6) = 2$ . Check $a_{1} \equiv a_{2} (mod 2)$ : $3 \equiv 1$ and $5 \equiv 1$ , so $3 \equiv 5 (mod 2)$ ✓. A solution exists. Why this step? Both congruences constrain $x mod 2$ . If they disagreed there (Case G), no $x$ could satisfy both. Step 2 — Merge by hand. From line one, $x = 3 + 4 k$ . Substitute into line two: $3 + 4 k \equiv 5 (mod 6) \Rightarrow 4 k \equiv 2 (mod 6) .$ Now divide the whole congruence — both sides and the modulus — by $g = 2$ , giving $2 k \equiv 1 (mod 3)$ . Why is dividing by $g$ legal? A congruence $c a \equiv c b (mod c n)$ literally says $c n ∣ (c a - c b)$ , i.e. $c n ∣ c (a - b)$ . Cancel the common factor $c$ from both the divisor and the quantity divided: this is equivalent to $n ∣ (a - b)$ , that is $a \equiv b (mod n)$ . So dividing sides and modulus by their shared factor $c$ preserves truth exactly. Here $c = 2$ : $4 k \equiv 2 (mod 6)$ becomes $2 k \equiv 1 (mod 3)$ . (Note: you may only cancel a factor from a modulus when it also divides both sides — cancelling from sides alone is a different, riskier rule.) Now $2^{- 1} \equiv 2 (mod 3)$ , so $k \equiv 2 \cdot 1 = 2 (mod 3)$ , i.e. $k = 2 + 3 t$ . Step 3 — Back-substitute. $x = 3 + 4 (2 + 3 t) = 11 + 12 t$ . So $x \equiv 11 (mod 12)$ , and $12 = lcm (4, 6)$ .

Verify: $11 = 2 \cdot 4 + 3 \Rightarrow\equiv 3 (mod 4)$ ✓; $11 = 1 \cdot 6 + 5 \Rightarrow\equiv 5 (mod 6)$ ✓. Answer: $x \equiv 11 (mod 12)$ — unique modulo the lcm, not the product.

Case G — non-coprime and contradictory

Case H — a word problem

Worked example Example 8 (Cell H): the basket puzzle

A basket holds fewer than $100$ eggs. Counting them in groups of $5$ leaves $3$ over; in groups of $6$ leaves $4$ over; in groups of $7$ leaves $1$ over. How many eggs?

Forecast: the answer is a single number below $100$ . Guess a rough size before solving.

Step 1 — Translate. Let $x$ = number of eggs. $x \equiv 3 (mod 5), x \equiv 4 (mod 6), x \equiv 1 (mod 7) .$ Why? "Leaves 3 over when grouped in 5s" is literally "remainder 3 mod 5." Step 2 — Coprime? $g cd (5, 6) = g cd (5, 7) = g cd (6, 7) = 1$ ✓, so standard CRT applies. $M = 5 \cdot 6 \cdot 7 = 210$ . Step 3 — Partial products. $M_{1} = 42, M_{2} = 35, M_{3} = 30$ . Step 4 — Inverses.

$42 y_{1} \equiv 1 (mod 5)$ : $42 \equiv 2$ , $2 y_{1} \equiv 1$ , $y_{1} = 3$ .
$35 y_{2} \equiv 1 (mod 6)$ : $35 \equiv 5$ , $5 y_{2} \equiv 1$ , $y_{2} = 5$ .
$30 y_{3} \equiv 1 (mod 7)$ : $30 \equiv 2$ , $2 y_{3} \equiv 1$ , $y_{3} = 4$ . Step 5 — Assemble. $x \equiv 3 \cdot 42 \cdot 3 + 4 \cdot 35 \cdot 5 + 1 \cdot 30 \cdot 4 = 378 + 700 + 120 = 1198 (mod 210) .$ Why this combination? Three switches: $3 \cdot 42 \cdot 3$ reads $3$ mod $5$ only; $4 \cdot 35 \cdot 5$ reads $4$ mod $6$ only; $1 \cdot 30 \cdot 4$ reads $1$ mod $7$ only. The sum reads all three remainders at once. $1198 - 5 \cdot 210 = 1198 - 1050 = 148, so x \equiv 148 (mod 210) .$ Step 6 — Apply the real-world constraint. "Fewer than $100$ eggs" — but $148 > 100$ and the next candidate down is $148 - 210 < 0$ . So the only value in $[0, 210)$ is $148$ , which violates " $< 100$ ."

Verify: $148 = 29 \cdot 5 + 3 \Rightarrow\equiv 3 (mod 5)$ ✓; $148 = 24 \cdot 6 + 4 \Rightarrow\equiv 4 (mod 6)$ ✓; $148 = 21 \cdot 7 + 1 \Rightarrow\equiv 1 (mod 7)$ ✓. Answer: the congruences force $x \equiv 148 (mod 210)$ ; there is no valid count below $100$ (the smallest positive solution is $148$ ). Lesson: CRT gives the residue class; the word problem's range then filters which member (if any) is legal.

Case I — the exam twist

Worked example Example 9 (Cell I): pin down the exact value

An integer $N$ satisfies $N \equiv 1 (mod 3)$ , $N \equiv 4 (mod 5)$ , and $N \equiv 6 (mod 7)$ . Given that $200 \leq N \leq 300$ , find $N$ exactly.

Forecast: CRT gives a class mod $105$ ; the range $[200, 300]$ selects one member. Which?

Step 1 — $M = 3 \cdot 5 \cdot 7 = 105$ . Step 2 — $M_{1} = 35, M_{2} = 21, M_{3} = 15$ . Step 3 — Inverses.

$35 y_{1} \equiv 1 (mod 3)$ : $35 \equiv 2$ , need $2 y_{1} \equiv 1$ , $y_{1} = 2$ .
$21 y_{2} \equiv 1 (mod 5)$ : $21 \equiv 1$ , so $y_{2} = 1$ .
$15 y_{3} \equiv 1 (mod 7)$ : $15 \equiv 1$ , so $y_{3} = 1$ . Step 4 — Assemble. $N \equiv 1 \cdot 35 \cdot 2 + 4 \cdot 21 \cdot 1 + 6 \cdot 15 \cdot 1 = 70 + 84 + 90 = 244 (mod 105) .$ Why this combination? Three switches: $1 \cdot 35 \cdot 2$ reads $1$ mod $3$ only; $4 \cdot 21 \cdot 1$ reads $4$ mod $5$ only; $6 \cdot 15 \cdot 1$ reads $6$ mod $7$ only. The sum reads all three. $244 - 2 \cdot 105 = 34, so N \equiv 34 (mod 105) .$ Step 5 — Select using the range. List the members of the class $34, 139, 244, 349, \dots$ (each is the previous plus $105$ ). The one lying in $[200, 300]$ is $244$ . Why this step? CRT alone answers "which class"; the exam's extra interval answers "which representative." Without the interval the answer would just be " $N \equiv 34 (mod 105)$ ."

Verify: $244 = 81 \cdot 3 + 1 \Rightarrow\equiv 1 (mod 3)$ ✓; $244 = 48 \cdot 5 + 4 \Rightarrow\equiv 4 (mod 5)$ ✓; $244 = 34 \cdot 7 + 6 \Rightarrow\equiv 6 (mod 7)$ ✓; and $200 \leq 244 \leq 300$ ✓. Answer: $N = 244$ .

The matrix, filled in

Recall Checklist: have you covered every dial?

A/B standard 2- and 3-congruence ::: Ex 1, Ex 2 C zero remainder ::: Ex 3 (term vanishes) D oversized / negative remainder ::: Ex 4 (reduce first) E hard inverse via Extended Euclid ::: Ex 5 F non-coprime consistent (answer mod lcm) ::: Ex 6 G non-coprime contradictory (no solution) ::: Ex 7 H word problem + range filter ::: Ex 8 I exam twist: select exact value in an interval ::: Ex 9

Recall Where this leads next

When one modulus is a product of two primes and you invert modulo it, you are doing exactly the step RSA Cryptography uses to speed up decryption via CRT. And the inverses you computed are guaranteed to exist by Fermat's Little Theorem / Bezout's Identity whenever moduli are coprime — see Systems of Linear Congruences for the fully general merge procedure used in Case F.

Which cases require the compatibility check

a_{i} \equiv a_{j} (mod g cd)

Only non-coprime cases (F and G); coprime systems have

g cd = 1

so it is automatic.

In a non-coprime consistent system, the solution is unique modulo what?

lcm (m_{1}, m_{2})

, not the product

m_{1} m_{2}

Why does a zero remainder

a_{i} = 0

simplify the CRT sum?

Its term

a_{i} M_{i} y_{i} = 0

drops out entirely.

Worked examples — Chinese Remainder Theorem (intro)