How Ancient War Trickery Is Alive in Math Today

Imagine you’re a general in ancient times and you want to keep your troop counts secret from your enemies. But you also need to know this information yourself. So you turn to a math trick that allows you to achieve both aims.

In a morning drill you ask your soldiers to line up in rows of five. You note that you end up with three soldiers in the last row. Then you have them re-form in rows of eight, which leaves seven in the last row, and then rows of nine, which leaves two. At no point have you counted all your soldiers, but now you have enough information to determine the total number without having to state an explicit count that an enemy could intercept.

Legend suggests ancient Chinese generals actually employed this technique, though it’s unclear if they really did. What we do know is that the mathematical technique now known as the Chinese remainder theorem was devised sometime between the third and fifth centuries CE by the Chinese mathematician Sun Tzu (not to be confused with Sun Tzu who wrote The Art of War almost 1,000 years earlier).

The theorem allows you to find an unknown number if you know its remainders when it’s divided by certain numbers that are “pairwise coprime,” meaning they do not have any prime factors in common. Sun Tzu never proved this formally, but later the Indian mathematician and astronomer Aryabhata developed a process for solving any given instance of the theorem.

“The Chinese remainder theorem gives you an actual recipe for making a number,”said Daniel Litt of the University of Georgia.

To better understand how the theorem works, let’s return to our example. Our goal is to find a whole number, X, that has a remainder of 3 when divided by 5 and a remainder of 7 when divided by 8 (later we’ll add in the third condition, that it has a remainder of 2 when divided by 9). Mathematicians call this a system of congruences, and they write it like this:

X ≡ 3(mod 5)
X ≡ 7(mod 8)

The first solution of the first congruence is 3, because 5 goes into 3 zero times and leaves a remainder of 3. Or, as mathematicians state it: 3 modulo 5 is 3. If we increase 3 by multiples of 5, those sums will also satisfy the first congruence. X could be any number in the sequence 3, 8, 13, 18, 23 and so on.

But the presence of a second congruence allows us to refine our solution. Numbers that satisfy this congruence — leaving a remainder of 7 when divided by 8 — are 7, 15, 23, 31 and so on. Now we need to find a number that appears on both lists of numbers:

3, 8, 13, 18, 23, 28, 33
7, 15, 23, 31, 39, 47, 55

And we see one. Our mystery number could be 23. But it’s not the only possibility.

We can always find another number that works by taking the product of our divisors and adding multiples of it to 23. Our divisors are 5 and 8. Their product is 40. Add 40 to 23 and we get 63, which also satisfies both congruences. As do 103, 143, 183, 223 and so on. So you can find a solution every 40 numbers by plugging in different whole numbers for K in the following formula:

X = 23 + 40 × K

However, the smallest whole number that satisfies these individual congruences is 23.

If you’re a general, though, and you know from experience that you have at most 300 soldiers, 23 or 63 or 103 might not be precise enough. So you add a third congruence to the first two (again, making sure that your new number is pairwise coprime with 5 and 8):

X ≡ 3(mod 5)
X ≡ 7(mod 8)
X ≡ 2(mod 9)

What is the mystery number that satisfies all three congruences? We return to our list of numbers that satisfy our first two congruences: 23, 63, 103, 143, 183, 223. None of these leaves a remainder of 2 when divided by 9. However, the next number in the sequence does: 263. And if we wanted more precision, we could add a fourth congruence — or as many congruences as we wanted.

“This approach can be generalized to several congruences, provided the divisors are pairwise coprime,” said Antonella Perucca of the University of Luxembourg.

Until now we’ve used divisors that are coprime. But what if we can’t choose the divisors? For instance, let’s say we’re astronomers following two comets with orbital periods of four years and 10 years. They last reached their perihelions — the point where a comet is closest to the sun — in the years 1991 and 1997, respectively. How do we determine the next time they will both reach their perihelions in the same year?

The Chinese remainder theorem can still help us. When the divisors are not coprime, instead of using multiples of their product to determine possible solutions, we use multiples of their least common multiple. So in this case, instead of multiplying 4 and 10, we use their least common multiple: 20.

We are now looking for a mystery year, X, that satisfies the following system of congruences:

X ≡ 1991(mod 4)
X ≡ 1997(mod 10)

If we follow the same process we used in the previous examples — in this case adding multiples of 20 to the smallest whole number that satisfies both congruences (which happens to be 7) — we find the shared year in which both comets reach their perihelions: 2007.

This example demonstrates the widespread applicability of the theorem, making it useful in practical settings such as astronomy, calculating ancient calendars and choosing the right size bricks for a building (the theorem likely helped with construction of the Great Wall of China). More than 1,500 years later, it remains a useful way of working through modern problems, including RSA encryption, the main security protocol safeguarding online communication.

But the Chinese remainder theorem is much more than a practical tool. It also underlies an operation in a fundamental branch of number theory called modular arithmetic, which is a way of doing math in smaller number systems, just as we did in the examples we worked through above involving troops and comets.

Mathematicians employ modular arithmetic all the time to investigate the deepest questions in their field. For centuries, a central line of inquiry in number theory has been determining when different types of polynomial equations like x² + y² = z² have integer solutions. For any polynomial equation there are infinitely many combinations you could try, which makes a brute-force search unworkable.

But to get started, you can first try to answer the question in a modular number system where you can actually check every possible value. There are many examples of this approach in action. To take one, in the 17th century Pierre de Fermat challenged British mathematicians to prove that the equation y² = x³ − 2 has only two pairs of integer solutions: (3, 5) and (3, −5). As it turned out, mathematicians discovered that the first step toward solving this was to study the problem in mod 4, which provided them with a foothold and established that at the very least, x needs to be odd.

In other cases, modular arithmetic can rule out the possibility that a polynomial equation has any whole-number solutions. First, look for solutions in modular number systems. If you don’t find them, you can take what you learned and translate it into statements about the lack of solutions to the same equation among all whole numbers.

“If there are no solutions modulo a prime, then you know there are no solutions,” said Litt.

It’s another example of how more than 1,000 years on, the Chinese remainder theorem is still providing clues to bigger truths — making it a potent tool in math, even if it’s no longer needed to pass secrets among generals.