The Chinese Remainder Theorem by Example

I learned some math today. What happened was during lunch I was trying problems on Alcumus and I came across a problem I absolutely hated. It went like this:

The marching band has more than 100 members but fewer than 200 members. When they line up in rows of 4 there is one extra person; when they line up in rows of 5 there are two extra people; and when they line up in rows of 7 there are three extra people.

How many members are in the marching band?

I sighed loudly to no one in particular and started working it out. I wrote down a lot of numbers that fit the “two extra people when there are rows of 5” constraint (which I know as “2 mod 5”). I wrote 102, 112, 122, 132, 142, 152, 162, 172, 182, 192, 107, 117, 127, 137, 147, 157, 167, 187, and — wait for it — 197. And then I started crossing numbers off the list that didn’t work for the “rows of 7” constraint (the first ten numbers) and then searched one by one to find the last one.

I showed it to my friend who I was sitting next to, he said that there has got to be a better way to do this.

Anyway, I find the solution and punch it into the website. I got it right (woohoo) and start trying to make sense of the solution, which is a truly awful Wall of Text. See?:

OK, but it mentions the Chinese Remainder Theorem, which I know as “that thing from group theory that I didn’t understand.”

I wanted to learn about the Chinese Remainder Theorem so I went to wikipedia, which is useless for this sort of thing, and then I said to my friend (who was still sitting nearby): I’ve got to find an example.

So I search, looking for something I can make sense of without already understanding it, and then I find this. It’s not great but it’s thankfully mostly-free of symbols, so I invest some effort into making sense of it. I work this through, step-by-step on paper.

My friend and I keep talking about it, and I think I figured out how it worked. And then I thought that I’d write the sort of examples that I wish I had been able to find in my initial search. So, while I’m no fan of Search Engine Optimization, I want to help this post make its way into Google Image search so I’m going to (Chinese Remainder Theorem Example) try my best (Chinese Remainder Theorem Example) to (Chinese Remainder Theorem Example) help Google (Chinese Remainder Theorem Example) find it.

This is not a complete explanation — there are definitely some gaps, and I’m sure it could be improved — but hopefully it’ll give you a start.

So here’s the explanation, with examples in the style of my favorite example resource, which is also the style of example I mostly use in my teaching.

---

This all begins with linear congruences. For example, there are lots of numbers that are 2 mod 5 (i.e. they have a remainder of 2 when you divide them by 5). 12 is congruent to 2 mod 5. So is 22. So is 1002, 10000002, etc., etc., there are a lot such numbers.

There are likewise numbers that have a remainder of 1 when you divide them by 3. Like 4, which is congruent to 1 mod 3. So is 34, 667, 333333333334, etc., etc.

So are there numbers that are both? And how do you find them? The Chinese Remainder Theorem says that there is a process that works for finding numbers like these. Here is an example of that process in action:

There’s probably no way to understand this without working through each step of the example — sorry! — but part of what I think is cool here is that this is a constructive process. What you’re doing is building this number, and the number is pieced together from parts that are designed to work. The reason this has to work comes in two parts:

1. Ingredient A: Anything times 7 is 0 mod 7. Anything 5 times anything is 0 mod 5. Anything times 13 is 0 mod 13. 156 x 45 x 23 x 8 is 0 mod 45.
2. Ingredient B: You can multiply numbers and get back to 1. So if you start with 3 mod 4, you can get back to 1 by doing 3 x 3 mod 4. If you start with 2 mod 5, you can get back to 1 by doing 2 x 3 mod 5. Can you always do this? Good question, it had better work for us here though.

These are the two ingredients that we use in that example. We make a number that is a sum of a multiple of 7 and a multiple of 3, which I imagine in this case to be little self-destruct signals waiting to be activated. When you want the number to be 2 mod 3, the multiple of 3 part is activated and it blows up, counting for 0, leaving just the multiple of 7 that you multiply by the thing that sets it back to 1 (thanks Ingredient B) and is then scaled by 2. Tada: 2 mod 3.

And you can do it again to get 1 mod 7. This time the mod 7 part explodes, counting for 0. You’ve multiplied 3 by the number that makes it 1, mod 7, and that’s perfect. You get 1 mod 7.

There are subtleties here. To test yourself, you might want to see if you can spot the mistake in this example:

One other little twist is that so far, we’ve just discussed how to find any number that fits both conditions. But what if you’re looking for the smallest positive number that fits the bill? In short, just count backwards, though at first you may be surprised by what you have to count backwards by…

A beautiful thing is that this process works exactly the same way when there are three conditions instead of two. That is, it almost exactly works the same way. Because we now want to plant even more little self-destruct signals in each part of the number. We want to rig things so that there are three terms, two of which self destruct every time we consider one of those congruence conditions.

Here we go:

And that’s that! The procedure just keeps going for more and more terms.

---

One thing I haven’t thought a great deal about yet is where to go from here, mathematically. What would be fun ways to extend or apply this idea? What are some good problems to try next?

I don’t know, I just started understanding this a few hours ago. But here are a few ideas:

• If you can do it, do it backwards. (I learned this from Kate Nowak.) But it’s not so much fun to start with a number and find some congruency conditions. Like, yes, divide 46 by 5 and you get remainder 1 and divide it by 7 you get 4, big whoop. But what’s kind of cool is that each of these uses of the Chinese Remainder Theorem end up partitioning the number. So can you know how to partition the number without going all the way through? Does each partition work for some initial conditions?
• The process always works for producing a number that fits the congruency conditions, but it doesn’t always produce the smallest. What’s up with that? How much bigger do they end up? Is there a way to know how many times bigger your number will be than the smallest possible integer?
• Does any of this relate to a procedure for solving systems of linear equations? Could you solve this graphically? Is there a nice graphical way of representing any of this?

I’ll keep thinking!

Advertisement