I've talked about the modular arithmetic before, especially as it related to the day for any date feat.

In this post, we're going to take it out of the calendar feat's shadow, and give it a starring role in its own feat!

If you remember doing division before you learned about fractions, you remember doing problems such as 21 ÷ 4 = 5 remainder 1. Modular arithmetic is simply focusing on the remainder exclusively. 21 modulo 4, for example, just equals 1, because when you divide 21 by 4, 1 is the remainder.

If we're talking at 10 AM, and I agree to call you in 5 hours, then you know to expect a call from at 3 PM. You did 10 + 5 = 15, but you know that hours aren't numbered any higher than 12, so you just subtracted 15 - 12 to get 3. This is modular arithmetic, and is also why it has the nickname “clock arithmetic.”

Let's try comparing the modular arithmetic patterns of two numbers, say, 2 and 4. Since 2 times 4 = 8, we'll compare the remainders as they run from 0 to 8:



What if I were to tell you that I was thinking of a number from 0 to 8. I then gave you a further clue that, when divided by 2, it has a remainder of 1, and when divided by 4, it has a remainder of 3, we run into a problem. Look at the chart. That description fits both 3 and 7, and there's no way to work out which of the two. The problem is that the pattern of remainders, when divided by 2 and 4, repeats 2 times from 0 to 8.

If we try this with, say, 3 and 6, and ran up to 18 (3 × 6) you can see in this chart that there are 3 times where a pattern of 3 remainders repeats.

If we want to identify a number by its remainders alone, is there some way to make sure that no repeating pattern emerges? Notice that, when we used 2 and 4 (and went up to 2 × 4, the remainder patterns repeated 2 times, and that 2 is the largest common factor of 2 and 4. Similarly, when we used 3 and 6 (and went up to 3 × 6), the remainder patterns repeated 3 times, and that 3 is the largest common factor of both 3 and 6.

If we want no repeating patterns, then what we're really saying is that, when performing modulo a and b, running from 0 up to a × b, we would like each number combination to only show up 1 time. For this to be true, we simply have to make sure that the greatest common factor of the numbers involved is 1!

This is the basic idea of the Chinese Remainder Theorem. Martin Gardner discusses this idea in more detail in his book Aha!: Aha! Insight and Aha! Gotcha (Spectrum). You can find the relevant pages online here and here, thanks to Google Books.

When using two numbers, it's pretty easy to make sure their only common factor is 1. If we use, say, 4 and 5, and go up to 20, we can already know that there won't be any repetitions, because the largest factor common to 4 (factors: 1, 2, 4) and 5 (factors: 1, 5) is 1.

The Chinese Remainder Theorem also tells us we can go further, and even use 3 or more numbers, and they won't repeat (up to a × b × c ×...) as long as their largest common factor is 1! The easiest way to do this, of course, is to turn to our old friend, prime numbers.

In the Martin Gardner book linked about, he talks about a version of a trick where someone thinks of a number from 1 to 1,000, and gives you the remainders after dividing by 7, 11, and 13. Since 7 × 11 × 13 = 1,001, you'll get a unique combination of remainders for any number given. But what about the version he mentions from 1 to 100 with 3, 5, and 7? What's the formula for that?

Let's take the approach in his article and apply it. For the remainder after dividing by 3, we need a multiple of 5 × 7 that's 1 greater than a multiple of 3. 35 doesn't work, because 34 isn't a multiple of 3. 70, being 69 + 1, works perfectly, though. OK, we start with 70 × a (or 70a for short).

What about 5? Let's look at the multiples of 3 × 7. There's 21...perfect! It's already 1 more than a multiple of 5. OK, now we've got 70a + 21b. What about 7? 3 × 5 = 15, and 15 is already 1 more than a multiple of 7. For all three numbers, we now have 70a + 21b + 15c. Divide that total by 105 (3 × 5 × 7), and the remainder will be the number you're looking for!

You could do that on a calculator, but if you're familiar at all with Grey Matters, you'll know that I encourage you to do things like that in your head. However, I understand that it can be tricky.

A magician named Tom Harris, back in 1958, proposed a different approach that required no calculation. You memorize the number combinations with help from the Peg/Major system, linking the combined numbers you get to the unique answer for that combination. For example, if someone gives you the numbers 1, 0, and 3, you would recall the phonetic equivalent “twosome”, and remember that you linked that to the word “toes,” which translates to 10.

This is a bit of work, but we have an advantage over someone trying to do this in 1958. Using a spreadsheet program makes an easy grid, and will handle listing the numbers from 1 to 100 for you, and will even handle working out the remainders for you. To find words for each combination, you can use some of the mnemonic generators listed here (My favorite for this would be pinfruit). Those familiar with the Peg System will already have 100 words ready for the answer numbers.

Naturally, I've developed a Wolfram|Alpha widget that can make things easier on your audience members:

I'll leave you with one last related challenge. James Grime needs help counting his juggling balls. Can you use what you've learned to help? When you're ready, here's the answer video.