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.
This entry was posted in modular arithmetic, number theory and tagged , , , . Bookmark the permalink.

2 Responses to Chinese Remainder Theorem proof

  1. There’s a typo in the wikipedia url 🙂

Comments are closed.