There was a general named Han Xin in the Han Dynasty in China. Every time he assembled his troops, he asked his men to report three times, the first time was 1 ~ 3, the second time was 1 ~ 5, and the third time was 1 ~ 7. After each report, he asked the last person to report the contents of his report, so that Han Xin would know how many people came. His ingenious algorithms are called "ghost valley calculation", "partition calculation" and "Qin Wang secretly points soldiers" This kind of problem is also recorded in Sun Tzu's mathematical classics: "I don't know the number of things today: three, three, five, seven, seven, the geometry of things?" It means that there are some items, if there are three numbers of three, there are two left in the end; If there are five numbers of five, there are three left at last; If there are seven numbers of seven, there are two left at last; How many of these projects are there? This problem is usually called "Sun Tzu problem", and western mathematicians call it "China's remainder theorem". Today, this problem has become a famous problem in the history of mathematics in the world. Cheng Dawei, a mathematician in the Ming Dynasty, compiled the algorithm of this problem into four songs: three people walk seventy miles, five trees and twenty-one branches; The seven sons were reunited for half a month, and they didn't know until 105. In the current words, it is: a number is divided by 3, and the remainder of the division is multiplied by 70; Divide by 5 and multiply the remainder by 21; Divide by 7 and multiply the remainder by 15. Finally, add up these products and subtract the multiple of 105, and you will know what this number is. The algorithm of this problem in Sun Zi's calculation is: 70× 2+21× 3+15× 2 = 233 233-105-105 = 23, so there are at least 23 items. According to the above algorithm, when Han Xin points soldiers, he must first know the approximate number of troops, otherwise the number cannot be accurately calculated. Do you know what this is about? This is because the smallest positive integer that 1 can be divisible by 5 and 7 and 3 is 70. 1 is divisible by 3 and 7, and the smallest positive integer divisible by 5 is 21; 1 is divisible by 3 and 5, and the smallest positive integer divisible by 7 is15; Therefore, the sum of these three numbers, 15× 2+2 1× 3+70× 2, must be divisible by 3, 5 and 7. The reason for the above solution is that the smallest positive integer of 1 divided by 3 and 5 is15; 1 is divisible by 3 and 7, and the smallest positive integer divisible by 5 is 21; 1 The smallest positive integer divisible by 5 and 7 and 3 is 70. So the smallest positive integer that can be divisible by 3 and 5 and 7 is15× 2 = 30; Divided by 3 and 7, the smallest positive integer of 3 divided by 5 is 21× 3 = 63; The smallest positive integer divisible by 5 and 7 and 3 is 70× 2 = 140. Therefore, the sum number 15× 2+2 1× 3+70× 2 must be divided by 3, 5 and 7. However, the result 233 (30+63+ 140 = 233) is not necessarily the smallest positive integer satisfying the above properties, so the least common multiple of 3, 5 and 7 105 is subtracted from it until the difference is less than 105, that is, 233-105. So 23 is the smallest positive integer divided by 3, divided by 5 and divided by 7. In fact, the above four rhymes given in China's ancient arithmetic books are all theorems that give the solution of the first congruence formula under special circumstances. 1247, Qin wrote "Nine Chapters", initiated the "big winding method to find the technique", and gave a general solution to the congruence group. In Europe, until 18th century, Euler and Lagrange (1736 ~ 18 13, French mathematician) were studying a congruence problem. Gauss, a German mathematician, clearly wrote a theorem for solving congruence groups in "Arithmetic Inquiry" published in 180 1 year. When the solution to the problem of "I don't know how many there are" in the mathematical classics of Sun Tzu's Art of War was spread to Europe in 1852 by the British missionary Alexander Wylie (18 15 ~ 1887), German Tai Sen (65474) was in/kloc-0. Therefore, in western mathematical works, the solution theorem of linear congruence group is called "China remainder theorem".