Chinese Remainder Theorem proof

In my previous post I stated the Chinese Remainder Theorem, which says that if $m$ and $n$ are relatively prime, then the function

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

is a bijection between the set $[mn]$ and the set of pairs $[m] \times [n]$ (remember that the notation $[k]$ means the set $\{0, \dots, k - 1\}$ ). In other words, if we draw an $m \times n$ grid and trace out a diagonal path, wrapping around when we get to an edge, we will hit every grid square exactly once before returning to the start. In other other words, the set of equations $x \equiv a \pmod m$ , $x \equiv b \pmod n$ always has a unique solution $x$ (that is, unique $\pmod {mn}$ ) when $m$ and $n$ are relatively prime.

Let’s prove it! First, let’s prove that the function $c$ is one-to-one, that is, any two different values of $x$ are sent to different pairs $(x \bmod m, x \bmod n)$ . In other words, if $x_1$ and $x_2$ are not equal, then $c(x_1)$ and $c(x_2)$ will also not be equal. In symbols:

$x_1 \neq x_2 \Rightarrow c(x_1) \neq c(x_2)$

Notice how this is phrased negatively, in terms of things being not equal to each other. It is usually much easier to prove the contrapositive of this statement, namely

$c(x_1) = c(x_2) \Rightarrow x_1 = x_2$

That is, if $x_1$ and $x_2$ map to the same remainders $(a,b)$ , then $x_1$ and $x_2$ must in fact be the same. This is logically equivalent (you should try to convince yourself of this if you’re unsure!) but much easier to get a handle on.

So, suppose we have numbers $x_1$ and $x_2$ , both non-negative and less than $mn$ , and suppose they give the same results $\pmod m$ and $\pmod n$ , that is, $x_1 \equiv x_2 \equiv a \pmod m$ and $x_1 \equiv x_2 \equiv b \pmod n$ . Consider their difference $d = x_2 - x_1$ . Since $x_1$ and $x_2$ have the same remainder when divided by $m$ , it must be the case that $d$ is evenly divisible by $m$ ; likewise, $d$ is evenly divisible by $n$ . But since $m$ and $n$ are relatively prime, that is, they share no common factors, they cannot overlap at all in $d$ ’s prime factorization; so in fact $d$ must be divisible by their product, $mn$ . In theory, then, $d$ could be one of the values $-2mn, -mn, 0, mn, 2mn, 3mn\dots$ . Which is it? Well, remember that $d = x_2 - x_1$ , and $0 \leq x_1, x_2 < mn$ . Subtracting two nonnegative integers less than $mn$ could never produce any multiple of $mn$ other than $0$ . So in fact $d = x_2 - x_1 = 0$ , which means $x_1 = x_2$ .

So the function $c$ is one-to-one. But it maps between two finite sets of the same size—namely, $[mn]$ and $[m] \times [n]$ , both of which have exactly $mn$ elements. If a function between two finite sets of the same size is one-to-one, it must actually be a bijection. That is, if we have the same number of things on each side, and a way to send each item on the left to a distinct item on the right, then we in fact have a way to match up every element on both sides with exactly one on the other side.

As a final note, this proof certainly has simplicity going for it, but you may find it a bit unsatisfactory: although it tells us that the function $c$ has an inverse, it doesn’t tell us how to compute it. That is, given a particular pair of remainders $(a,b)$ where $x \equiv a \pmod m$ and $x \equiv b \pmod n$ , how do we find $x$ ? It can certainly be done. But for now I will let you look it up, and perhaps I’ll write about it at some point in the future!

About Brent

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

View all posts by Brent →