Chinese Remainder Theorem History (韩信点兵)



In Ancient China, there was a General named Han Xin, who led an army of 1500 soldiers in a battle. An estimated 400-500 soldiers died in the 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.”

Amazing! How did Han Xin do that?

Han Xin was not only a brilliant mathematician and general, he was also a very magnanimous guy full of wisdom.

Once, when he was suffering from hunger, he met a woman who provided him with food. He promised to repay her for her kindness after he had made great achievements in life, but it was rebuffed by her. On another occasion, a hooligan saw Han Xin carrying a sword and challenged him to either kill him or crawl through between his legs. Han Xin knew that he would become a criminal if he killed him, hence instead of responding to the taunts, he crawled through between the hooligan’s legs and was laughed at.

Several years later, after becoming the King of Chu, Han Xin returned to his hometown and found the woman who fed him and rewarded her with 1,000 taels of gold. Han Xin also found the hooligan and instead of taking revenge, he appointed the hooligan as a zhongwei (中尉; equivalent to a present-day lieutenant). He said, “This man is a hero. Do you think I could not have killed him when he humiliated me? I would not become famous even if I killed him then. Hence, I endured the humiliation to preserve my life for making great achievements in future.”

Mathematical Explanation by Guest Blogger Mathtuition88:

In modern notation, the problem can be stated as

x \equiv 2 \pmod 3

x\equiv 4 \pmod 5

x\equiv 6 \pmod 7

We may then use the theory of the Chinese Remainder Theorem to conclude that a solution is:

x = a(5)(7) + b(3)(7) + c(3)(5) , where

35a \equiv 2 \pmod 3

21b \equiv 4 \pmod 5

15c \equiv 6 \pmod 7

Simplifying, we get

2a \equiv 2 \pmod 3, which we may take a=1.

b \equiv 4 \pmod 5, which we may take b=4.

c \equiv 6 \pmod 7, which we may take c=6.

Hence, x = 1(5)(7)+4(3)(7)+6(3)(5) = 209 is a solution.

We know by the theory of Chinese Remainder Theorem that this solution is unique congruent modulo (3x5x7=105).

Hence 209 + 8 x 105 = 1049 is also a solution and indeed the most likely one since it is estimated that 400-500 soldiers died.

How exactly did the military genius Han Xin calculated it remains a mystery though.

More on the story of Han Xin:


4 thoughts on “Chinese Remainder Theorem History (韩信点兵)”

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: