# Has Chinese Remainder Theorem ever been used by Chinese military?

The Chinese Remainder Theorem says, in rough terms, that if you know the remainders of an integer $n$ modulo $m_1,m_2,\dots,m_r$, you also know $n$ modulo $\mathrm{lcm}(m_1,m_2,\dots,m_r)$.

In the mathematical folklore, I've often heard it associated to the problem of counting the size of an army. That comes in two flavours. The first (which seems pretty unlikely) is that instead of counting troops, the Chinese generals would order them to assemble in rows of different depths (hence obtaining the remainder of the number of soldiers modulo different integers) and then they would use the Chinese Remainder Theorem to compute the size of the army. Another version which I've heard says that the Chinese Remainder Theorem was used to guard against spies. Instead of recording the number of soldiers in an army, the Chinese would record remainders modulo various numbers (presumably in hope that the intended recipient would be able to apply the theorem to compute the original number, but the spy would not).

Has any of these things actually happened?

• One thing to note is that mathematicians love word problems, they aren't necessarily meant to be real (or even realistic). – PyRulez Nov 2 '17 at 19:20

Is it possible that "Chinese remainder theorem" was used by the Chinese military? Who knows. But we know that the proliferation of Chinese generals and soldiers in connection with it comes from late fables. The original source of the "theorem" is Sunzi Suanjing, which has nothing to say about counting soldiers. The problem is stated thus:

"There are certain things whose number is unknown. If we count them by threes, we have two left over; by fives, we have three left over; and by sevens, two are left over. How many things are there?"

The book is dated to 3-5th century AD, and nothing is known about the author, but the name Sun Zi is spelled the same way as Sun Tzu, the famous Chinese general who wrote The Art of War. That Sun Tzu lived c. 500 BC does not stop some modern enthusiasts from attributing Sunzi Suanjing to him anyway.

Another Chinese general associated with the theorem is Han Xin, who lived c. 200 BC. A Singaporean blogger tells an "amazing" story of him and his army of 1500 soldiers estimated 400-500 of which died in a battle:

"When the soldiers stood 3 in a row, there were 2 soldiers left over. When they lined up 5 in a row, there were 4 soldiers left over. When they lined up 7 in a row, there were 6 soldiers left over. Han Xin immediately said, “There are 1049 soldiers".

No source for this amazing story is given (it is repeated or mentioned in many other places though), but from Volkov's paper in From China to Paris, p.402 we learn that Han Xin dian bing (Han Xin's way of counting soldiers) dates to 13th century AD, when Cheng Dawei mentions it as a name of a rhymed stanza. Qin wang an dian bing (Prince of Qin's method of secretly counting soldiers) occurs somewhat earlier in Yang Hui's Xiangjie Jiuzhang Suanfa (c. 1265 AD), better known for magic squares, magic circles and Yang Hui's (a.k.a. Pascal's) triangle.

This explosion of popularizations seems to follow Qin Jiushao's Shùshū Jiǔzhāng (c.1245 AD), which presented a complete solution to the remainder systems of equations with multiple examples. As usual with anecdotes, memorable illustrations were then invented and ascribed to famous historical figures, acquiring more and more details over the subsequent centuries. The name "Chinese Remainder Theorem" comes from 19th century Europe, see What is the history of the name “Chinese remainder theorem”?

For a more mathematically focused history see Kangsheng's Historical development of the Chinese remainder theorem.

I am not able to prove that it was never used in the ways that you mentioned, but it's highly unlikely, to say the least.

The oldest known appearence of that theorem is in a Chinese text, the Sunzi Suanjing (3rd to 5th centuries AD). It is stated as a purely mathematical problem:

There are certain things whose number is unknown. A number is repeatedly divided by $3$, the remainder is $2$; divided by $5$, the remainder is $3$; and by $7$, the remainder is $2$. What will the number be?

As you can see, there is no reference to counting soldiers here. The theorem only reappears in a Chinese text in the 13th century, in two books: the Mathematical Treatise in Nine Sections written by Qin Jiushao in 1247 and in a book written by Yang Hui around 1275. Again, there is no reference to applications.

So, again, I very much doubt that it has ever been used for counting soldiers in ancient China.

• In 13th century Qin Jiushao discusses CRT earlier and much more than Yang Hui. – Conifold Oct 29 '17 at 22:48
• @Conifold You are right, of course. I've edited my answer. – José Carlos Santos Oct 29 '17 at 22:55