Chinese Remainder Theorem — Two Clocks, One Unique Hour

The Chinese Remainder Theorem sounds ancient and mystical, and it is both. The statement is deceptively simple: if you know a number's remainder modulo m and its remainder modulo n, and m and n are coprime, then you can reconstruct its remainder modulo mn. But the visual — two clocks ticking side by side, their hands sweeping independently — makes what the theorem is really saying land with a thud. You are looking for the unique hour on a super-clock with mn positions where both sub-clocks show the readings you demand.

The setup: two clocks, two remainders, one unknown

Suppose somebody tells you: "I am thinking of an integer x. When divided by 3 it leaves remainder 2. When divided by 5 it leaves remainder 3. What is x modulo 15?"

Translate this into two clock readings. Clock A has 3 positions (0, 1, 2) and ticks at every integer. Clock B has 5 positions (0, 1, 2, 3, 4) and also ticks at every integer. Both clocks show position 0 at time x = 0, then advance together, each wrapping around with its own period. You want the earliest positive integer x where clock A reads 2 and clock B reads 3 simultaneously.

There are 15 candidate values between 0 and 14. Walking through them one by one is brute force. But with m and n coprime (here \gcd(3, 5) = 1), the two clocks never synchronise the same pair twice in a full cycle of mn. Exactly one hour within \{0, 1, \ldots, mn - 1\} satisfies any pair of demands. That is the Chinese Remainder Theorem.

Interactive: two clocks, hunt for the matching hour

x = 0 m = n =

Scan $x$ from $0$ to $mn - 1$. Clock A shows $x \bmod m$, Clock B shows $x \bmod n$. The strip below records the pair $(x \bmod m, x \bmod n)$ at every $x$. When $\gcd(m, n) = 1$, every pair appears exactly once — the CRT bijection. Change $m, n$ and try $m = 6, n = 4$ to watch the bijection collapse.

Why the pairs are in perfect bijection

Why does the theorem work only when \gcd(m, n) = 1? Here is the picture.

Walk through the integers 0, 1, 2, \ldots, mn - 1 and at each one, record the pair (x \bmod m, x \bmod n). You get a list of mn pairs. There are m \cdot n possible pairs in total. If all mn pairs you recorded are distinct, the map is a bijection, and every pair corresponds to exactly one x in the range \{0, \ldots, mn-1\}.

The condition \gcd(m, n) = 1 is exactly what forces distinctness. Suppose two integers x and y in \{0, \ldots, mn-1\} produced the same pair. Then m \mid (x - y) and n \mid (x - y). If \gcd(m, n) = 1, then \operatorname{lcm}(m, n) = mn, and any integer divisible by both m and n must be divisible by mn. But |x - y| < mn, so the only multiple of mn in that range is 0 — meaning x = y. Therefore the pairs are distinct, and the bijection holds.

The $3 \times 5$ grid of pairs $(x \bmod 3, x \bmod 5)$ as $x$ ranges over $\{0, 1, \ldots, 14\}$. Every one of the $15$ cells is filled, each with a unique $x$. The cell at row $2$, column $3$ contains $x = 8$ — the unique solution to $x \equiv 2 \pmod 3$ and $x \equiv 3 \pmod 5$. The filling is a bijection because $\gcd(3, 5) = 1$.

When m and n are not coprime

If \gcd(m, n) = d > 1, the bijection breaks. Consider m = 6, n = 4 (with \gcd = 2). The grid has 24 cells, but \operatorname{lcm}(6, 4) = 12, so as x ranges over \{0, \ldots, 11\}, you only hit 12 distinct pairs. The remaining 12 pairs are unreachable. For example, x \equiv 1 \pmod 6 and x \equiv 0 \pmod 4 has no solution — because 1 is odd and 0 is even, and if both moduli share a factor of 2, they impose consistent parity demands.

This is why CRT always comes with the "if \gcd(m, n) = 1" hypothesis. Without it, the two clocks are synchronised in a deeper way than just the modulus, and some demands are contradictory.

Finding the solution: the constructive method

Once you believe the solution exists, how do you find it?

Method 1 (scan). Write down the multiples of m that are congruent to a \pmod m: a, a + m, a + 2m, \ldots. Check each against the n-condition until one passes. For the example: x \equiv 2 \pmod 3 gives x \in \{2, 5, 8, 11, 14, \ldots\}. Check which is \equiv 3 \pmod 5: 2 \bmod 5 = 2, 5 \bmod 5 = 0, 8 \bmod 5 = 3. So x = 8.

Method 2 (Bezout). Since \gcd(m, n) = 1, Bezout gives um + vn = 1 for some integers u, v. Then

x = a \cdot v n + b \cdot u m \pmod {mn}

For our example: \gcd(3, 5) = 1 and 2 \cdot 3 + (-1) \cdot 5 = 1, so u = 2, v = -1. Then x = 2 \cdot (-1) \cdot 5 + 3 \cdot 2 \cdot 3 = -10 + 18 = 8 \pmod {15}. Same answer.

Method 2 scales gracefully to three or more coprime moduli; method 1 does not.

A worked example

Problem: Find $x$ such that $x \equiv 4 \pmod 7$ and $x \equiv 1 \pmod 9$

\gcd(7, 9) = 1, so CRT applies. The full period is 7 \cdot 9 = 63, and a unique x \in \{0, \ldots, 62\} works.

Scan: x \equiv 4 \pmod 7 gives \{4, 11, 18, 25, 32, 39, 46, 53, 60\}. Check each mod 9:

4 \bmod 9 = 4
11 \bmod 9 = 2
18 \bmod 9 = 0
25 \bmod 9 = 7
32 \bmod 9 = 5
39 \bmod 9 = 3
46 \bmod 9 = 1 — match.

So x \equiv 46 \pmod {63} is the unique solution.

Why: the two clocks synchronised the pair (4, 1) at time 46, and will do so again every 63 steps.

Why this visualisation is powerful

The two-clocks picture does three things at once:

Makes existence visual. You can literally see the clocks march through all mn pairs, and see each pair hit exactly once.
Makes uniqueness obvious. Each cell in the grid is visited once and only once — no two values of x in one period produce the same pair.
Explains the coprimality condition. When \gcd(m, n) > 1, the two clocks share a common rhythm, some pairs are forever unreachable, and CRT fails.

The algebraic proof using Bezout is tidy but opaque. The grid picture shows the theorem in action.

The one-line takeaway

Two clocks of periods m and n with \gcd(m, n) = 1 hit every pair of readings exactly once in mn steps. That is the Chinese Remainder Theorem — and the grid of (x \bmod m, x \bmod n) pairs is the proof you can draw.