What is the use of the Chinese Remainder Theorem

Question

What is the most tangible way to introduce the Chinese Remainder Theorem? What are the practical and really interesting examples of this theorem. I am looking for examples which have a real impact on students.

Answer 1

I call the CRT the "modular coordinates theorem".

If you have a bunch of numbers $m_1...m_n$, then any number $k$ can be given a "coordinate" by giving the $n$-tuple of its remainders modulo each $m_i$: $(k \mod m_1,\ ...\ k \mod m_n)$. The question is: can we uniquely determine a number from its coordinate tuple?

Well, of course not, not if our number $k$ is any arbitrary integer. There's only $\prod m_i$ possible tuples and an infinite number of values of $k$. In fact, we can show that the coordinate tuples are $\prod m_i$-periodic as follows. First note that the coordinate tuple of $k$ uniquely determines the coordinate of $k+1$, since you can obtain the latter by adding $1$ and taking a remainder to each value in the coordinate tuple of $k$. Next, obviously the coordinate tuple of $\prod m_i$ is $0$ - it's congruent to $0$ modulo any of the $m_i$. Any sequence that both deterministic (every value depends only on the previous value) and eventually goes back to its initial value is obviously periodic after that point.

So if our coordinate system resets and starts repeating after $\prod m_i$, then we can certainly only hope to determine a number $k$ from its coordinates if we know that $k$ is between $0$ and $\prod m_i$. But can we always do that? Maybe some numbers in that range will have the same coordinate.

First of all, we'll obviously run into problems if the $m_i$ aren't pairwise distinct. Imagine if we had $m_1=m_2=2$. Then the coordinate "tuple" of $k$ is really just a single value - the remainder of $k$ modulo $2$. You certainly can't uniquely identify any number between $0$ and $m_1m_2=4$ with that information. If the coordinate is $0$ then $k$ could be either $0$ or $2$, and if it's $1$ it could be either $1$ or $3$.

We're also in trouble if $m_1=2$ and $m_2=4$, as the following table shows:

As you can see, there are multiple numbers that share coordinate tuples. The trouble here is that, although the coordinate tuples are indeed $m_1m_2=8$-periodic, that's not their smallest period. They're also $4$-periodic, and $4$ is the smallest period of the coordinate tuples. Furthermore, you can see that for $k<4$, we can uniquely determine $k$ from its coordinates. $4$, incidentally, happens to be the LCM of $m_1$ and $m_2$.

We can show in general that the coordinate tuples modulo $m_1...m_n$ are injective between $0$ and $\mathrm{LCM}(m_1,...m_n)$, i.e. numbers in that range are uniquely determined by their coordinate tuple. Furthermore, this is also the maximum range on which coordinates are injective. This in particular implies the standard statement of the Chinese Remainder Theorem, since the LCM of a set of coprime integers is their product.

Proof:

My favorite proof is similar to the argument I gave above, showing that the coordinates are $\prod m_i$-periodic. Let's say we're working with the modulos $m_1...m_n$. I'll abbreviate $\mathrm{LCM}(m_1,...m_n)$ by $M$. Obviously, the coordinate tuples are $M$-periodic, since the coordinate tuple of $M$ is all zeros. By the above argument, the coordinate tuples must repeat after that point. Also, is the coordinate tuple of $k$ is all zeros, then $k$ must be a common multiple of $m_1, ... m_n$. Therefore, there is no number less than $M$ whose tuple is all zeros.

Now, suppose we had $k < k' < M$, such that the coordinate tuples of $k$ and $k'$ were identical. Again, since the coordinate tuple of a number determines the coordinate tuple of the next number, we know that the coordinate tuples must repeat after $k'$. In particular, the coordinates of the numbers $k...k'$ are going to repeat infinitely. Since $M>k'$, this means that the coordinate of $M$ must be the same as the coordinate of some number between $k$ and $k'$. But this is impossible, since the coordinate tuple of $M$ is all zeros, and no smaller number has all zero coordinates, as was shown previously. Therefore the coordinates of $k$ and $k'$ are not identical. $\blacksquare$

This "coordinate system" point of view leads to the interesting question as to, if we had an infinite set $m_1, m_2, ...$ of coprime modulos (say, the set of prime numbers), would the resulting coordinate system be injective over $\Bbb N$?