Chinese Remainder Theorem, also known as Chinese Remainder Theorem and Sun Tzu’s Remainder Theorem.
From "Sun Zi Suan Jing" to Qin Jiushao's "Nine Chapters of the Book of Numbers", the research results on linear congruence problems began to receive attention from the Western mathematical community in the mid-19th century. In 1852, the British missionary William Alex introduced to Europe the "things are unknown" problem in "Sun Zi Suan Jing" and Qin Jiushao's "Dayan Qi Yi Technique"; in 1876, the German Mathisen pointed out that this problem in China The solution is completely consistent with the solution of linear congruence equations in Gauss's "Arithmetic Inquiry" in the 19th century in the West. Since then, this creation of ancient Chinese mathematics has gradually attracted the attention of scholars around the world, and is officially known as the "Chinese Remainder Theorem" in Western mathematics history books.
In the history of Chinese mathematics, there is a widely circulated story of "Han Xin's command of troops":
Han Xin was a general under Liu Bang, the emperor of the Han Dynasty. Established outstanding achievements. It is said that Han Xin was also very good at mathematics. When he was counting troops, in order to keep military secrets and prevent the enemy from knowing the strength of his troops, he ordered the soldiers to count from 1 to 3, and then recorded the number reported by the last soldier. ; Then ask the soldiers to count from 1 to 5, and also record the number reported by the last soldier; finally ask the soldiers to count from 1 to 7, and record the number reported by the last soldier; in this way, he can quickly calculate The total number of soldiers in his army was determined, and the enemy was never able to figure out how many soldiers there were in his army.
The calculation method of Han Xin's troops mentioned in this story is the linear congruence solution now known as the "Chinese Remainder Theorem". It is a major creation of ancient Chinese mathematicians and plays an important role in the history of world mathematics.
The first person to propose and describe this mathematical problem was the title "Things cannot be counted" in the mathematical work "Sun Zi Suan Jing" during the Southern and Northern Dynasties. The topic of "Uncountable Objects" is as follows:
"Today there are some objects whose quantity is unknown. If you count them three by three, there will be two left in the end; if you count five by five If you count it in seven places, there will be three left in the end; if you count it in seven places, there will be two left in the end."
The simple mathematical language is: find a number such that it is divided by 3 with a remainder of 2, divided by 5 with a remainder of 3, and divided by 7 with a remainder of 2. "Sun Zi Suan Jing" gives the solution and answer to this question, which is expressed as:
In modern mathematical terms, this "original diagram of the square root method" is actually a Table of binomial theorem coefficients with positive integer exponents. Readers who know a little bit about algebra know: "Sun Zi Suan Jing" actually gives a general solution to this type of linear congruence equation group:
Among them, the four numbers 70, 21, 15 and 105 are The key, so later mathematicians compiled this solution into the following poem for easy memorization:
"Three people walking together are seventy (70) rare,
Five trees Twenty-one plum blossoms (21).
Seven sons are reunited in the first half of the month (15).
It will be known after dividing one hundred and five (105). ”
Although the question "Things cannot be counted" in Sun Tzu's Suan Jing pioneered the study of primary congruence formulas, because the question is relatively simple and can even be solved by trial and error, it has not yet been upgraded to a complete set of calculation procedures. and theoretical height. It was Qin Jiushao, a mathematician from the Southern Song Dynasty, who really solved this problem from a complete calculation program and theory. Qin
Jiushao proposed a mathematical method "Dayan Qiuyi Technique" in his "Nine Chapters of the Book of Numbers" (see Figure 1-7-1), and systematically discussed the linear congruence formula Basic principles and general procedures of group solution.
Why did Qin Jiushao call his set of calculation procedures and basic principles the "Dayan Qiu Yi Technique"? This is because the core problem of its calculation program is to "find one". The so-called "finding one", in layman's terms, means finding "how many times of a number divided by another number, the remainder is one." So why do we need to "seek one"? We can find the following pattern from the key numbers 70, 21, and 15 in the question "I don't know the number of things":
Figure 1-7-1 Wenlange Siku Complete Book "Nine Chapters of the Book of Numbers" 》Book Shadow
Among them, 70 is a multiple of 5 and 7, but the remainder is 1 when divided by 3; 21 is a multiple of 3 and 7, but the remainder is 1 when divided by 5; 15 is a multiple of 3 and 5, but the remainder is 1. Divided by 7, the remainder is 1. For any group of linear congruences, as long as the key numbers are found according to this rule, then this group of linear congruences is not difficult to solve. To this end, Qin Jiushao proposed a series of mathematical concepts such as multiplication ratio, definite numbers, derivatives, derivatives, etc., and described in detail the complete process of "The Great Evolution to Find a Technique". (Because the solution is too complicated, we will not describe it here. Interested readers can refer to relevant books for further reference.) Up to this time, the linear congruence problem originated from the "Things are unknown" problem in "Sun Zi Suan Jing" , only then did a universal solution be obtained, and only then did it truly rise to the level of the "Chinese Remainder Theorem".