Making Friends with the Chinese Remainder Theorem

(in which a comparison of an oddly-named theorem and a procedure for solving a simple congruence system by hand sheds some light and inspires confidence that the theorem can be used AND understood)

The longer I teach high school students, the more I become convinced that a formula is a dangerous thing. It is far too easy for a student to settle for “just show me where to plug in the numbers and I’ll turn the crank” and call it competence – especially if that suffices to get the homework done.

A far stronger learning experience results from initially doing something the hard way (as in the tedious, time-consuming, grungy number crunching, almost-as-much-eraser-as-pencil-lead method) and either discovering the formula oneself, or receiving it as a gift that can be properly appreciated.

For example, when I teach differentiation, I do not just hand my students the Power Rule. We find many derivatives using the limit definition and get lots of exposure to the idea of the limit of a difference quotient before I say “Oh, by the way …” Sneaky? A little. Effective? Yes. Insight building? You betcha. I rarely have to explain more than once why continuity is a requirement for differentiability.

So as I ponder the possibility of teaching a new Discrete Math course at the high school next year, and think about how I would go about engendering an appreciation for this Chinese Remainder Theorem (which has nothing to do with how rapidly the take-out leftovers disappear from my refrigerator), I put together this expansion of what Prof. Walther presented on 1/24/12, as documented in class notes taken by D. Lee.

A typical congruence problem might look like this:

$ \begin{align} x & = {a_1}\,\bmod\,{m_1} \\ & = {a_2}\,\bmod\,{m_2} \\ & = \vdots \\ & = {a_n}\,\bmod\,{m_n}\\ \end{align} $

If the notation is scary, perhaps it helps to realize that a familiar "find the Least Common Multiple" problem could be staged in this notation, like this:

$ \begin{align} x & = 0\,\bmod\,{m_1} \\ & = 0\,\bmod\,{m_2} \\ & = \vdots \\ & = 0\,\bmod\,{m_n} \\ \end{align} $

Recall that the Chinese Remainder Theorem (CRT) requires that the moduli be pairwise relatively prime, and notice that all of the $ {a_i} = 0. $ The sum of products generated by the CRT is then $ x = 0\,\bmod\, {m_1}{m_2}\dots{m_n} $ or, in English, a number that is divisible by the product of the moduli, exactly as we would expect.

An Example

Consider the system of congruences

$ \begin{align} x & = 2\,\bmod\,3 \\ & = 4\,\bmod\,5 \\ & = 5\,\bmod\,7\\ \end{align} $

This system meets the requirements for applying the CRT because 3,5 and 7 are pairwise relatively prime. I could easily plug into the CRT and generate $ x $. But what would I do if I did not have the CRT? Well, I'd do what you would do -- I'd pick two of the equivalences, find a number that worked for them, and then figure out what I would need to do to get a number that would satisfy all three equivalences.

Given that the moduli are so small, I don't have to do anything more complicated than a quick list to find that 14 is both 2mod3 and 4mod5

$ 2\,\bmod\,3 \equiv 5,8,11,14,17,20,23,26,29, ... $

$ 4\,\bmod\,5 \equiv 9, 14, 19, 24, 29, 34, ... $

Notice that this is technically 14mod15 (because the product of the moduli involved so far is 15). Even if my mental math landed me at 29, 29 is also equivalent to 14mod15 so I'd still be working with 14, the value that falls into the [0,15) interval.

This is one of the differences I noted between the CRT and "by hand" -- when working by hand I could use the modulus to reduce the value I was working with as I went along. As you'll see, the CRT can overshoot the desired interval, requiring a final modular reduction at the end of the process.

So now my task is to find a number that also satisfies the 5mod7 equivalence. Notice that 14 (my "so far" solution) is 0mod7 and 15 (my "so far" product of moduli) is 1mod7. My light bulb moment came in realizing that I can add multiples of 15 to 14 WITHOUT CHANGING ITS NATURE IN mod3 OR mod5, and every time I add 15 I ratchet the remainder mod7 up by one. That is

$ \begin{align} 14+k\cdot15 & = ??? \\ 14+0\cdot15 & = 14 \equiv 0\,\bmod\,7 \\ 14+1\cdot15 & = 29 \equiv 1\,\bmod\,7 \\ 14+2\cdot15 & = 44 \equiv 2\,\bmod\,7 \\ 14+3\cdot15 & = 59 \equiv 3\,\bmod\,7 \\ 14+4\cdot15 & = 74 \equiv 4\,\bmod\,7 \\ 14+5\cdot15 & = 89 \equiv 5\,\bmod\,7 \\ \end{align} $

That number 89 is the smallest positive value that meets the 5mod7 requirement, and since it also meets the 2mod3 and 4mod5 requirements, it is the solution to my system.

If I wanted to add a fourth congruence to my system, say $ x \equiv 3 \,\bmod\,13 $, I would note that 89 (my "so far" solution) is 11mod13, and 105 (my "so far" product of moduli) is 1mod13. If, in a mod13 framework, my remainder starts at 11 and has to end up at 3, I need to add 5(105) to 89 to get the value that satisfies all four equivalences. Check it out!

Now,it is important to notice that both times we added on a new congruence, it just so happened that the "so far" product of moduli was congruent to ONE in the newly added modulus. This is delightfully convenient, but it doesn't always happen. For example, if I had picked a different pair to start with from the original three congruences, I would have seen something different.

Same Example, Different Starting Place

Let's say I started with 4mod5 and 5mod7 instead. Here are the lists:

$ \begin{align} 4\,\bmod\,5 & \equiv 9, 14, 19, 24, 29, 34, 39, 44, 49, 54 ... \\ 5\,\bmod\,7 & \equiv 12, 19, 26, 33, 40, 47, 54, ... \\ \end{align} $

My "so far" solution is 19, and my "so far" product of moduli is 35. I'm ready to add the third equivalence to the mix, and it is mod3. I find 19 is 1mod3, and 35 is 2mod3. Recall that I am going to seek my new solution by adding multiples of 35 to 19. Every time I add 35, I will be ratcheting the remainder of my "solution in process" by TWO, and not by one as in the earlier cases. I'm already at 19=1mod3. Adding 35 once puts me at 54=0mod3 and I have to add 35 a second time to get 89=2mod3. In effect, because I am in mod3 and am limited (by 35mod3) to adding exactly two each time, I have to add four to achieve adding one. That is

$ \begin{align} 19+k\cdot35 & = ??? \\ 19+0\cdot35 & = 19 \equiv 1\,\bmod\,3 \\ 19+1\cdot35 & = 54 \equiv 0\,\bmod\,3 \\ 19+2\cdot35 & = 89 \equiv 2\,\bmod\,3 \\ \end{align} $

Now we are ready to pick apart the CRT and see what those addends represent. Here's what we are looking at:

$ x \equiv {a_1}{M_1}{y_1} + {a_2}{M_2}{y_2} + \dots + {a_n}{M_n}{y_n} \,(\bmod\,m) $

where

$ \begin{align} {a_i} & = \mathrm{the\ remainder\ in\ the\ i^{th}\ congruence} \\ {m_i} & = \mathrm{the\ i^{th}\ modulus} \\ {m} & = \mathrm{the\ product\ of\ all\ the\ moduli} \\ {M_i} & = \frac {m}{m_i} \\ {y_i} & = \mathrm{an\ integer\ that\ satisfies\ } {M_i}{y_i}\equiv 1\,\bmod\,{m_i} \\ \end{align} $

Look first at $ {M_i} $. These are the same idea as the "so far" products of moduli in the by-hand process. Each is the product of all the moduli in the system except the $ {i^{th}} $ one.

When we worked by hand, we found $ {M_i}\,\bmod\,{m_i} $ (the value that was 1 for 15mod7 and 105mod13 but 2 for 35mod3). This is $ {y_i} $ -- it is the multiplier that increments $ {M_i} $ until its remainder is one in $ \bmod {m_i} $.

The final piece is $ {a_i} $. These play the role of $ k $ above, and describe how many time we need to add $ {M_i}{y_i} $ to adjust the remainder to the desired value for each modulus. $ {M_i}{y_i} $ is equivalent to $ 1\,\bmod\,{m_i} $, so adding $ {a_i} $ of them together gives me something equivalent to $ {a_i}\,\bmod\,{m_i} $.

Comparing "By Hand" to the CRT

To finish up, then, let's see what the CRT does with our system of three congruences.

$ {a_1}=2 \qquad {a_2}=4 \qquad {a_3}=5 $

$ {M_1}=35 \qquad {M_2}=21 \qquad {M_3}=15 $

$ {y_1}=2 \qquad {y_2}=1 \qquad {y_3}=1 $

$ \begin{align} x & = 2\cdot35\cdot2 + 4\cdot21\cdot1 + 5\cdot15\cdot1 \\ &= 140 + 84 +75 = 299 \\ \end{align} $

Here's the cool part. We have three moduli involved: 3, 5, and 7. Look at how the remainders of the three addends and their sum play out:

You could think of it like this: 140 gets the mod 3 remainder to the right value without affecting the remainders for mod 5 and mod 7. 84 gets the mod 5 remainder to the right value without affecting the remainders for mod 3 and mod 7, and 75 takes care of mod 7 without messing up mod 3 or mod 5. One more step ...

$ 299 \equiv 89\,\bmod\,105 $

and we're done. The CRT simply does what I would do by hand. It incorporates some overlap that results in a final answer that must be reduced, but definitely improves on the one-new-modulus-at-a-time “by hand” method with an all-moduli-at-once approach.

Theresa

Back to MA375, Spring 2012, Prof. Walther