In my previous post I stated the Chinese Remainder Theorem, which says that if and are relatively prime, then the function
is a bijection between the set and the set of pairs (remember that the notation means the set ). In other words, if we draw an 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 , always has a unique solution (that is, unique ) when and are relatively prime.
Let’s prove it! First, let’s prove that the function is one-to-one, that is, any two different values of are sent to different pairs . In other words, if and are not equal, then and will also not be equal. In symbols:
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
That is, if and map to the same remainders , then and 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 and , both non-negative and less than , and suppose they give the same results and , that is, and . Consider their difference . Since and have the same remainder when divided by , it must be the case that is evenly divisible by ; likewise, is evenly divisible by . But since and are relatively prime, that is, they share no common factors, they cannot overlap at all in ’s prime factorization; so in fact must be divisible by their product, . In theory, then, could be one of the values . Which is it? Well, remember that , and . Subtracting two nonnegative integers less than could never produce any multiple of other than . So in fact , which means .
So the function is one-to-one. But it maps between two finite sets of the same size—namely, and , both of which have exactly 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 has an inverse, it doesn’t tell us how to compute it. That is, given a particular pair of remainders where and , how do we find ? 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!
There’s a typo in the wikipedia url 🙂
Ah, thanks, fixed!