More words about PWW #25: The Chinese Remainder Theorem

In a previous post I made images like this:

And then in the next post I explained how I made the images: starting in the upper left corner of a grid, put consecutive numbers along a diagonal line, wrapping around both from bottom to top and right to left. The question is then why some grids get completely filled in, like the one above, and why some have holes, like this:

Commenter ZL got the right answer: the grid will be completely filled in if and only if the width and height of the grid are relatively prime.

In fact, this is (a special case of¹) the Chinese remainder theorem (as commenter Jon Awbrey foresaw). In more traditional terms, the Chinese remainder theorem says that if we have a system of two modular equations

$\begin{array}{rcl}x &\equiv& a \pmod m \\ x &\equiv& b \pmod n\end{array}$

then as long as $m$ and $n$ are relatively prime, there is a unique solution for $x$ in the range $0 \leq x < mn$ .

Here’s another way to think about this. Suppose I have a number $x$ in the range $0 \leq x < mn$ . If I tell you only $x \bmod m$ , that is, the remainder when dividing $x$ by $m$ , you can’t tell for sure what $x$ is; there may be multiple possibilities for $x$ . Likewise, if I only tell you $x \bmod n$ , you don’t know $x$ . But if I tell you both—as long as $m$ and $n$ are relatively prime—it’s enough information to precisely pin down the value of $x$ ; there is only one value of $x$ which has a certain remainder modulo $m$ and at the same time a certain remainder modulo $n$ .

Yet another way to state the theorem is to consider the function

$c(x) = (x \bmod m, x \bmod n)$

which sends an integer $x \in \{0, \dots, mn-1\}$ to a pair of integers where the first is in the range $\{0, \dots, m-1\}$ and the second is in the range $\{0, \dots, n-1\}$ . If we use the notation $[n] = \{0, \dots, n-1\}$ then we can write this concisely as

$c : [mn] \to [m] \times [n]$

The Chinese Remainder Theorem just says that this function is actually a bijection, that is, it is onto (every pair $(a,b)$ has some solution $x$ such that $c(x) = (a,b)$ ) and one-to-one (the $x$ for a given $(a,b)$ is unique).

But this function $c$ is exactly what the grid diagrams are visualizing! We start at $x = 0$ in the upper left, and every time we step to the next value of $x$ , we take a step down; so in general the number $x$ will be on row $x$ (if we number the rows starting with row $0$ at the top)—except that we wrap around when we get to the bottom. So if there are $m$ rows, that means $x$ will be on row $x \bmod m$ . Similarly, we take a step to the right with each next value of $x$ , and wrap around; so $x$ will be in column $x \bmod n$ . Hence each $x$ will end up at grid coordinates $(x \bmod m, x \bmod n)$ , which is exactly the function $c$ . And $c$ being a bijection is exactly the same thing as the grid being completely filled in: every value of $x$ corresponds to a different grid square, and every grid square has a value of $x$ .

In my next post I’ll go over a simple proof of the theorem.

The full Chinese Remainder Theorem actually says something about the situation where you have an arbitrary number of these equations, not just two; but the version with only two equations has all the essential features. (Indeed, once you believe the version with two equations, you can “bootstrap” your way to dealing with an arbitrary number just by applying the two-equation version repeatedly.)↩

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

View all posts by Brent →