Chinese Remainder Theorem (intro): Visual walkthrough

We will solve one concrete pair of clues the whole way down:

$x \equiv 2 (mod 3) and x \equiv 3 (mod 5)$

Read out loud: "the number I want leaves remainder $2$ when divided by $3$ , and remainder $3$ when divided by $5$ ." (Again — the $\equiv \dots (mod)$ notation is defined precisely in Step 1.)

Step 1 — Draw each clue as a ladder of dots

WHAT. A congruence like $x \equiv 2 (mod 3)$ does not name one number — it names a whole family: $2, 5, 8, 11, 14, \dots$ , each one $3$ apart. Same for $x \equiv 3 (mod 5)$ : the family $3, 8, 13, 18, \dots$ , each $5$ apart.

WHY. Before hunting for a single answer, we must see that each clue is not a point but an evenly-spaced comb of allowed positions. The answer is wherever two combs line up.

PICTURE. Look at the figure. The number line runs $0$ to $15$ . Cyan dots mark the family that satisfies clue 1 (spacing $3$ ). Amber dots mark clue 2 (spacing $5$ ). Notice how each comb has its own rhythm.

Figure — Chinese Remainder Theorem (intro)

Step 2 — The answer is where the two combs collide

WHAT. Overlay the two combs. There is exactly one column, inside $0 \leq x < 15$ , where a cyan dot and an amber dot land together. That column is our solution.

WHY. A number satisfies both clues precisely when it belongs to both families — a shared tooth. Finding $x$ is nothing more mysterious than finding the overlap.

PICTURE. The amber highlight ring sits at $x = 8$ : $8 = 2 \cdot 3 + 2$ (remainder $2$ mod $3$ ✓) and $8 = 1 \cdot 5 + 3$ (remainder $3$ mod $5$ ✓). And the overlap repeats every $15$ — the next shared tooth is $23$ , then $38$ .

Step 3 — Stop guessing: build the answer from clue 1 outward

WHAT. Instead of scanning for the overlap, we construct it. Start by obeying clue 1 automatically: write

$x = remainder we want mod 3 2 + unknown integer k \cdot the modulus m_{1} 3$

Any whole-number choice of $k$ keeps $x$ on the cyan comb.

WHY. We reduce a two-condition puzzle to a one-condition puzzle. Clue 1 is now free — satisfied for every $k$ . All that remains is to pick the $k$ that also lands on amber.

PICTURE. Each value of $k$ slides us one cyan tooth to the right: $k = 0 \to 2$ , $k = 1 \to 5$ , $k = 2 \to 8$ . The figure shows $x$ as an arrow whose base is pinned at $2$ and whose length is $3 k$ .

Step 4 — Force clue 2, and a division problem appears

WHAT. Demand that our sliding $x = 2 + 3 k$ also satisfies clue 2:

$2 + 3 k \equiv 3 (mod 5)$

Subtract the $2$ from both sides (allowed — you may add/subtract the same thing in modular arithmetic):

$3 k \equiv 1 (mod 5)$

WHY. We turned "find $x$ " into "find $k$ ": which slide-count lands us on amber? The left side is now a clean multiplication we can attack.

PICTURE. The figure lists the candidate values of $3 k mod 5$ as $k = 0, 1, 2, 3, 4$ : they cycle $0, 3, 1, 4, 2$ . We want the entry equal to $1$ — it happens at $k = 2$ (amber box).

Step 5 — Why the inverse always exists (and why coprimality is the hinge)

WHAT. In Step 4 the cycle $0, 3, 1, 4, 2$ hit every remainder $0..4$ exactly once. That is the whole miracle: because $3$ and $5$ share no factor, multiplying by $3$ shuffles the remainders without repeats — so the value $1$ is guaranteed to appear, meaning the inverse must exist.

WHY. Bezout's Identity says: if $g cd (3, 5) = 1$ then there are integers $u, v$ with $3 u + 5 v = 1$ . Read that mod $5$ : $3 u \equiv 1 (mod 5)$ , so $u$ is the inverse. The Extended Euclidean Algorithm is the machine that spits out $u, v$ ; for small numbers we just read them off the cycle.

PICTURE. Two rings. The left ring (multiplying by $3$ , coprime to $5$ ) has arrows visiting all five spots — one clean cycle, so $1$ is reachable. The right ring shows the failure: multiplying by, say, $2$ modulo $4$ only ever lands on $0$ and $2$ — the odd remainders $1, 3$ are never hit, so $2^{- 1} mod 4$ does not exist.

Step 6 — Slide back and read off the answer

WHAT. We found $k \equiv 2 (mod 5)$ , so the smallest slide is $k = 2$ . Plug back into $x = 2 + 3 k$ :

$x = 2 + 3 \cdot 2 = 8$

And because $k$ could be $2, 7, 12, \dots$ (any $k \equiv 2 (mod 5)$ ), $x$ jumps by $3 \cdot 5 = 15$ each time:

$x \equiv 8 (mod 15)$

WHY. This closes the loop with Step 2: we predicted the collision at $8$ by pure construction, no scanning. The repeat-period $15 = m_{1} m_{2}$ falls out automatically from the leftover freedom in $k$ .

PICTURE. The arrow from Step 3, now locked at length $3 \cdot 2 = 6$ , lands its tip exactly on the amber-ringed dot at $8$ from Step 2. The two views agree.

Step 7 — Repackage the same work as the parent's formula

WHAT. The parent's formula reads $x \equiv \sum_{i} a_{i} M_{i} y_{i} (mod M)$ . Here $a_{i}$ is simply the remainder demanded by clue $i$ — the numbers on the right of each congruence. In our problem $a_{1} = 2$ (remainder mod $3$ ) and $a_{2} = 3$ (remainder mod $5$ ). Let us recognise our hand-work inside the formula.

$M = 3 \cdot 5 = 15$ — the repeat period we already met.
$M_{1} = M / m_{1} = 15/3 = 5$ : divisible by $5$ , so it vanishes mod $5$ but not mod $3$ .
$M_{2} = M / m_{2} = 15/5 = 3$ : divisible by $3$ , so it vanishes mod $3$ but not mod $5$ .
$y_{1} = M_{1}^{- 1} mod 3 = 5^{- 1} mod 3 = 2$ and $y_{2} = M_{2}^{- 1} mod 5 = 3^{- 1} mod 5 = 2$ .

WHY. Each term $a_{i} M_{i} y_{i}$ is an on/off switch: it equals $a_{i}$ (the demanded remainder) in its own modulus and $0$ in every other. Adding them stacks the clues without interference — because the $M_{i}$ are built to be zero elsewhere.

PICTURE. Two horizontal bars. Term $a_{1} M_{1} y_{1} = 2 \cdot 5 \cdot 2 = 20$ shows " $\equiv 2$ mod 3, $\equiv 0$ mod 5". Term $a_{2} M_{2} y_{2} = 3 \cdot 3 \cdot 2 = 18$ shows " $\equiv 0$ mod 3, $\equiv 3$ mod 5". Their sum $38 \equiv 8 (mod 15)$ .

The one-picture summary

WHAT. Everything on one canvas: two combs (clue 1 cyan, clue 2 amber) collide at $8$ ; the "build from clue 1, solve for the slide $k$ " arrow reaching that dot; and the switch-term bars stacking to the same $8$ . Three routes, one answer.

Recall Feynman retelling — say it back in plain words

Two clues, each a comb of evenly-spaced allowed numbers — one comb every $3$ steps, one every $5$ . I want a spot on both combs. Rather than search, I stand on the first comb by writing my number as "start at $2$ , then hop $3$ at a time." Now I just need the right number of hops so I also land on the second comb. That "right number of hops" is a division-in-disguise, $3 k \equiv 1 (mod 5)$ , whose answer is the modular inverse of $3$ . That inverse is guaranteed to exist only because $3$ and $5$ share no factor — coprimality means multiplying shuffles all remainders, so the value I need is always reachable; if they shared a factor, multiplication would skip remainders and my inverse could be missing. I take the hops, land on $8$ , and because leftover freedom repeats every $3 \times 5 = 15$ , the answer is $x \equiv 8 (mod 15)$ . The textbook's $\sum a_{i} M_{i} y_{i}$ formula is just the same idea prewrapped: each term is a switch that says my remainder in its own comb and stays invisible in the others. This is the engine behind RSA Cryptography and Fermat's Little Theorem speed-ups.

Recall

Why is there exactly one answer between $0$ and $15$ ? ::: The two combs (spacing $3$ and $5$ ) only re-sync after the least common multiple (lcm — the smallest number both $3$ and $5$ divide) $lcm (3, 5) = 15$ , and since $g cd = 1$ that lcm equals $3 \times 5$ , so each block of $15$ holds exactly one collision. What equation must $k$ solve in the slide method? ::: $3 k \equiv 1 (mod 5)$ , whose solution is the modular inverse of $3$ mod $5$ , namely $k \equiv 2$ . Where does coprimality actually get used? ::: It guarantees the modular inverse in Step 4 exists — multiplication by a coprime number visits every remainder, so remainder $1$ is reachable. How does term $a_{1} M_{1} y_{1}$ avoid disturbing clue 2? ::: $M_{1} = M / m_{1}$ is a multiple of $m_{2}$ , so the term is $\equiv 0 (mod m_{2})$ — it is switched off outside its own modulus. (Here $a_{1} = 2$ is the remainder demanded by clue 1.)