BIG MOUTH for Quanta Magazine

In this situation hot dogs and buns don’t match up before you reach 40, because 40 is the least common multiple of 5 and 8. This is because 5 and 8 are "relatively prime" — they have no factors in common. And when two numbers are relatively prime, their LCM is just their product. When you start listing the multiples of 8 — 8 × 1, 8 × 2, 8 × 3, 8 × 4, 8 × 5 — you can see that you won’t get a multiple of 5 until you reach 8 × 5.

When two numbers aren’t relatively prime, their multiples have a chance to match up before they reach their full product. In the first case we looked at, 10 and 8 aren’t relatively prime because they share a factor, 2: 10 = 2 × 5, and 8 = 2 × 4. Since 8 is already divisible by 2, you only need a multiple of 8 to be divisible by 5 for that number to be divisible by 10. This is why the multiples first match up at 8 × 5 = 40, long before they reach 8 × 10 = 80.

Now imagine starting with one leftover hot dog in the refrigerator. How many packs of each must you buy to match up dogs and buns now? This new problem takes us beyond simply finding LCMs and into the more complicated realm of the Chinese remainder theorem, a result first identified by the Chinese mathematician Sun Tzu nearly 2,000 years ago. The Chinese remainder theorem resides in a field of math called modular arithmetic that studies numbers by analyzing their remainders when they are divided by other numbers. It is used in applications from cryptography to astronomy. Let’s see how hot dogs and LCMs can help us understand this ancient algorithm.

If you’ve got one hot dog in the refrigerator and you can purchase packs of five hot dogs at the store, here’s a list of the possible numbers of hot dogs you could take to the cookout:

Since the number of hot dogs will always be 1 plus a multiple of 5, all these numbers have a remainder of 1 when divided by 5. Letting x equal the number of hot dogs, you can write this relationship as

x ≡ 1 mod 5.

You read this as "x is congruent to 1 mod 5," and it means when you divide x by 5 you get a remainder of 1. You can also say "x has a remainder of 1 mod 5."

Since the number of buns is always a multiple of 8, it will always have a remainder of zero when divided by 8. If y is the number of hot dog buns, you can write this relationship as

y ≡ 0 mod 8.

We want the number of hot dogs and the number of buns to be equal, so we want x = y. To find out when that happens, we can solve the following "system of congruences":

x ≡ 1 mod 5
x ≡ 0 mod 8

As in a system of equations, the goal of solving a system of congruences is to satisfy all the congruences simultaneously. We want to find a number x that has a remainder of 1 when divided by 5 and a remainder of zero when divided by 8. If we can do that, we can match up our hot dogs and buns perfectly.

The Chinese remainder theorem is designed to handle exactly these kinds of systems. It tells us that as long as the numbers you are dividing by — the "moduli" — are relatively prime, there is a unique solution greater than or equal to zero but less than the product of the moduli, regardless of the remainders. (If the moduli are not relatively prime, there may be no answer at all. For example, the system x = 1 mod 6 and x = 2 mod 8 has no solution, either below 24 or above.) Since 5 and 8 are relatively prime, there should be a unique solution to this system that is less than 40.

The numbers in this problem are small, so we can find the solution just by lining up the possible numbers of hot dogs and buns:

As you can see, 16 is on both lists, is less than 40 and solves our system of congruences. We can quickly check that 16 has a remainder of 1 when divided by 5 and a remainder of zero when divided by 8. (Notice that if you add 40, the LCM of 5 and 8, to 16, you get 56, the next number that solves our system of congruences.)

The Chinese remainder theorem not only guarantees that a solution exists, it gives us a plan for finding it. The algorithm relies on the fact that if two numbers are relatively prime, you can always find an integer combination of them that is equal to 1. Let’s see how this works with another cookout challenge.

Imagine that in addition to starting with one leftover hot dog, you also have two leftover buns. How many packs of hot dogs and buns would you have to buy to match everything up now? To answer this we need to solve the following system of congruences:

x ≡ 1 mod 5
x ≡ 2 mod 8

To find the solution guaranteed by the Chinese remainder theorem we’ll use the fact that since 5 and 8 are relatively prime, some integer combination of them is 1. This means we can find integers a and b such that 5a + 8b = 1. You can easily check that a = −3 and b = 2 works:

5 × (-3) + 8 × 2 = 1.

To find our solution, the Chinese remainder theorem algorithm tells us to multiply 5 × (-3) by the bun remainder, 2, and multiply 8 × 2 by the hot dog remainder, 1, and then add the results:

2 × 5 × (-3) + 1 × 8 × 2 = -14.

This tells us we can solve our problem by having −14 hot dogs and −14 buns, which sounds like the punchline to a bad joke about mathematicians planning a picnic. But our actual solution is hiding in here. Remember, we know eight packs of hot dogs and five packs of buns will always match up at 40 (the way our previous example had solutions of 16 and 56), so we just add 40 to −14. This gives us 26, the unique solution larger than zero but less than 40 that’s guaranteed by the Chinese remainder theorem.

You can see that 26 hot dogs and 26 buns solves the problem if you line up the possible numbers of each:

There’s a simple but clever reason the Chinese remainder theorem works. To see why, think about all the multiples of 5 under 40, the least common multiple of 5 and 8.

The multiples are 0 × 5, 1 × 5, 2 × 5, 3 × 5, …, and 7 × 5, so there are eight multiples of 5 greater than or equal to zero but less than 40. Since these multiples of 5 are all smaller than the LCM, they must all have different remainders when divided by 8. If any two of them had the same remainder when divided by 8, then their difference would be divisible by 8. But the difference of two multiples of 5 is also a multiple of 5, so the difference would have to be divisible by both 5 and 8, which would make it divisible by 40. This is impossible, since two multiples of 5 less than 40 can’t be 40 apart. Take a look at all the different remainders here:

Since there are only eight possible remainders when you divide by 8, all of the possible remainders show up on this list. This means the multiples of 5 under 40 cover all the possible remainders mod 8. In other words, if you start out with any leftover buns from the last pack in your refrigerator, you will be able to make a matching number of fewer than 40 hot dogs. In math terms, the system of congruences

x ≡ 0 mod 5
x ≡ a mod 8

always has a solution less than 40 for any a. Just check the list of remainders above: For a = 1, the solution is x = 25 ; for a = 2, the solution is x = 10, and so on.

What if you start out with one additional hot dog? This increases every hot dog number by 1, which increases every remainder by 1. But since all the remainders are shifted over by 1, all eight possible remainders will still be represented.

Notice that shifting a remainder of 7 up by 1 makes it 7 + 1 = 8, and if a number has a "remainder" of 8 when divided by 8, it’s actually a multiple of 8, so its remainder is really 0 mod 8.

This means that the system of congruences

x ≡ 1 mod 5
x ≡ a mod 8

also has a solution less than 40 for every a: For a = 1, the solution is x = 1; for a = 2, the solution is x = 26, and so on.

This reasoning can be generalized to show that

x ≡ b mod 5
x ≡ a mod 8

has a solution less than 40 for every a and b, and generalized further to show that every system of congruences of the form

x ≡ b mod m
x ≡ a mod n

has a solution less than m × n, as long as m and n are relatively prime. This is the most basic version of the Chinese remainder theorem.

This theorem, like a lot of number theory tricks, is useful in cryptography, the mathematics of encoding and decoding secret messages. For example, you can use the theorem to keep a number secret until a group of people agree to collaborate to identify it.

Suppose you want a number to stay secret unless your friends Alex and Bo agree that they both want to know it. First assign them a pair of relatively prime numbers — say, 13 for Alex and 17 for Bo — whose product is greater than your secret number. Now divide your secret number by each of their numbers and give each of them their individual remainder. Neither will know your number, but they are guaranteed to be able to figure it out together thanks to the Chinese remainder theorem!

Let’s say you tell Alex the number 11 and Bo the number 15. This means that Alex knows your number x satisfies x ≡ 11 mod 13 and Bo knows x satisfies x ≡ 15 mod 17. Neither of these congruences alone is enough to specify your secret number, but together they form the system

x ≡ 11 mod 13
x ≡ 15 mod 17

and the Chinese remainder theorem guarantees that this system has a unique solution less than 13 × 17 = 221. Working together, Alex and Bo can figure out your number is 219.

You probably won’t need the Chinese remainder theorem to plan your next picnic, but in case you need to distribute access to information among your friends or secretly share troop strength with your generals, make sure this extension of least common multiples is on your list.

Exercises

1. Explain why this system of congruences has no solution:

x ≡ 1 mod 4
x ≡ 0 mod 6

Why doesn’t this violate the Chinese remainder theorem?

2. In solving the hot dog problem

x ≡ 1 mod 5
x ≡ 2 mod 8

we used the fact that (-3) × 5 + 2 × 8 = 1. It’s also true that 13 × 5 + (-8) × 8 = 1. What would have happened if we had used this integer combination of 1 instead?

3. Consider this system of congruences:

x ≡ 1 mod 3
x ≡ 2 mod 4

Find three positive solutions to this system. All of these numbers have the same remainder mod 12. What is it?

4. Use the result of exercise 3 to solve this system of congruences:

x ≡ 1 mod 3
x ≡ 2 mod 4
x ≡ 3 mod 5

Click for Answer 1:

Click for Answer 2:

Click for Answer 3:

Click for Answer 4:

geometry

Insights puzzle

information theory