The Chinese Remainder Theorem

Jin Yong's "The Legend of the Condor Heroes" has been a best-selling novel worldwide, and many people are familiar with the story of Guo Jing and Huang Rong. However, it is interesting to note that within "The Legend of the Condor Heroes," there is also a mathematical problem known as the "Sūnzi's theorem," also referred to as "Guiguzi's algorithm" or "Han Xin's troop dispositions." In modern mathematics, it is known as the "Chinese Remainder Theorem."

 

In the story, Guo Jing and Huang Rong, while leaving a swamp, challenged Ying Gu, who was renowned as a "mathematical genius." The third problem presented by Huang Rong was the famous "Guiguzi's algorithm":

 

There is an unknown quantity,
Divided by 3, the remainder is 2,
Divided by 5, the remainder is 3,
Divided by 7, the remainder is 2.

What is the minimum value of this unknown quantity? (Taken from "Sūnzi Suanjing," Volume 2, Problem 26)

 

In simpler terms, the question asks for the minimum value of an unknown quantity that, when divided by 3, leaves a remainder of 2; when divided by 5, leaves a remainder of 3; and when divided by 7, leaves a remainder of 2.

 

Ying Gu easily arrived at the answer, which is 23, and even people who are quick at mental calculations can figure it out. However, she still sought advice from Huang Rong because her answer was obtained by trial and error, and she couldn't find a general method to solve the problem. The essence of mathematical research is to discover the characteristics of problem-solving and develop universal solutions.

 

The solution to "Guiguzi's algorithm" has been turned into a folk song:

 

Three people travel together, seventy is rare,
Twenty-one plum blossoms on five trees,
Seven children form a circle on the fifteenth day of the first month,
Divide by 105, and the answer will be known. (Taken from "Suanfa Tongzong," Volume 4)

 

The term "fifteenth day" represents 15. The solution suggests multiplying 70 by the remainder obtained when divided by 3, multiplying 21 by the remainder obtained when divided by 5, multiplying 15 by the remainder obtained when divided by 7, and then adding them up. If the sum is greater than 105, subtract 105 repeatedly until it becomes less than 105. The final number obtained is the answer. Using the remainders from "Guiguzi's algorithm" as an example: 2x70 + 3x21 + 2x15 - 105 - 105 = 23.

 

You can try using different remainders to verify this solution and you will find that it is indeed an incredible method. However, there are two questions: (1) How can we derive this result? (2) What if the divisors change or there are more remainders? In short, can this method be generalized?