"Three people walk seventy times, five trees and twenty-one sticks.
The seven sons were reunited for half a month, and they didn't know until 105. "
These interesting math games introduced the solution to the world-famous "grandson problem" in various forms, and popularly reflected an outstanding achievement of ancient mathematics of the Han nationality. Sun Tzu's problem is a congruence problem in modern number theory, which first appeared in Sun Tzu's mathematical classics in the fourth century A.D.. The title of Sun Tzu's Mathematical Classics, Unknown Things, says: If there are unknown things, three counts as more than two, five counts as more than three, and seven counts as more than two. What is the total number of things? Obviously, this is equivalent to solving indefinite equations.
N=3x+2，N=5y+3，N=7z+2
The positive integer solution of n, or expressed by modern number theory symbols, is equivalent to solving the following linear congruence groups.
n = 2(mod 3)； n = 3(mod 5)； N=2 (mode 7)
The answer given in Sun Tzu's calculation is N=23. Because Sun Tzu's question data is relatively simple, this answer can also be obtained through trial calculation. But Sun Tzu's calculations failed to do this. The skill of "I don't know how to count things" points out that there are three ways to solve problems, taking 70 and multiplying it by the remainder 2; Among five or five numbers, take the number twenty-one and multiply it by the remainder three; For the number 77, multiply the remainder 2 by 15. Add up the products and subtract the multiple of 105. The column formula is:
n = 70×2+2 1×3+ 15×2-2× 105 = 23 .
Where 105 is the least common multiple of module 3, module 5 and module 7. It is easy to see that Sun Tzu has given the smallest positive integer that meets the conditions. For the general remainder, Sun Tzu's Art of War points out that it is only necessary to replace the remainder 2, 3 and 2 in the above algorithm with new ones respectively. R 1, R2, R3 are used to represent these remainders, and Sun Tzu's calculation is equivalent to giving a formula.
N = 70× r1+2/kloc-0 /× R2+15× R3-p×105 (p is an integer).
The key of Sunzi algorithm lies in the determination of three numbers: 70,21,15. The words "seventy rarities", "twenty-one skills" and "full half moon" in Sun Tzu's Art of War later spread alluded to these three key figures. Sun Tzu's calculations did not explain the origin of these three numbers. In fact, they have the following characteristics:
That is to say, these three numbers can be obtained by subtracting the moduli 3, 5 and 7 from the least common multiple M=3×5×7= 105, and then multiplying by the integers 2, 1 and 1 respectively. Assuming that k 1=2, K2= 1 and K3= 1, then the integer Ki(i= 1, 2,3) is selected so that the three numbers obtained are divided by the corresponding ones. From this, we can immediately deduce the situation when the remainder is R 1, R2, R3.
Applying the above reasoning, Sun Tzu's algorithm can be completely similar to the general situation: there is a number n, and the remainder R 1, R2, ... ……Rn is obtained by pairwise prime numbers a 1, a2, ... Ann, that is.
N≡Ri(mod ai)(i= 1、2、……n)，
Only a set of numbers k is needed to satisfy.
1(mod ai)(i= 1、2、……n)，
Then the smallest positive solution suitable for a given congruence group is
(p is an integer, m = a 1× a2× …× an),
This is the famous remainder theorem in modern number theory. As mentioned above, its basic form has been included in the solution of the problem of "I don't know how to count things" in the Art of War. However, this universal theorem is not clearly stated in Sun Tzu's Calculations.
It is no accident that the grandson problem appeared in China's calculation in the 4th century. From the data of ancient astronomical calendars in China, it is obvious that the study of congruence is driven by the needs of astronomy and calendars, especially closely related to the calculation of the so-called "Shangyuan Accumulated Year" in ancient calendars. As we all know, calendars need to specify a start time. Ancient calendar mathematicians in China called this starting point "Era" or "Shangyuan", and the accumulated time from the era to the calendar year was called "Shangyuan calendar year". The calculation of the cumulative number of years in the last element needs to solve a group of linear congruences. Take Jing promoted by Wei in the Three Kingdoms period in the 3rd century A.D. as an example. This calendar stipulates that the time when the winter solstice, the new moon (midnight of the new moon) and Jiazi meet at 0: 00 is the era. Let A be the number of days in the tropic year, and B be the number of days in the first month of the lunar calendar. When the winter solstice is Jiazi day R 1 and Pingshuo is R2 day, the number n of elements in the Jingchu calendar is the solution of the congruence group.
Anli (Type 60) R2 (Type B)
In the Northern and Southern Dynasties, Zu Chongzhi's Da Li Ming (AD 462) required that the era should be the beginning of Jiazi year at the same time, and the moon should pass through its perigee and ascending intersection. Under such conditions, calculating the cumulative year of the last element is equivalent to finding the solution of ten congruences. Astronomical calendar data are generally very complicated. Therefore, in the Wei, Jin, Southern and Northern Dynasties before and after the book Sunzi Suanjing, China's astronomical calendar calculator was undoubtedly able to work out a much more complicated congruence formula than the problem of "unknown things" in Sunzi Suanjing, so they must have mastered the method of calculating a congruence formula according to certain procedures. This fact is summarized and reflected in the form of proportional problem in Sun Zi Shu Jing. In the future, astronomers will use Sun Tzu's algorithm to calculate the cumulative year of the last element for a long time, which will surely lead to more in-depth discussions. In the13rd century, the great mathematician Qin finally made brilliant achievements in the study of congruence.
Qin Jiu Shao, with an ancient word, lived in the Southern Song Dynasty. He likes math since he was a child. After long-term accumulation and painstaking research, he wrote Shu Shu Jiu Zhang in A.D. 1247. This medieval mathematical masterpiece was created in many ways. Among them, "solving the great derivative of a congruence group" and "extracting positive and negative squares" for solving numerical solutions of higher order equations are even more significant achievements in the world.
This paper mainly introduces Qin's great contribution to congruence theory.
Qin clearly and systematically described how to solve a congruence group in Shu Shu Jiu Zhang.
General calculation steps of. Qin's method is exactly the remainder theorem mentioned above. As we know, the residue theorem reduces the general first-order congruence problem to choosing a set of numbers Ki that meet the conditions. Qin named these numbers as "multiplication rate", and introduced the calculation method of multiplication rate in detail in Volume I of Nine Books-"Great Circle Method".
In order to introduce the skill of "seeking a skill by expanding greatly", we take the calculation of arbitrary ratio ki as an example. If Gi => Qin first divides Ai by GI to get the remainder Gi.
gi gi(mod ai)，
So kiGi kiGi(mod ai),
But because kiGi 1(mod ai),
So the problem boils down to making ki fit kigi≡ 1(mod ai). Qin called Ai a "fixed number" and Ji an "odd number". His theory of "seeking a skill by big deduction" is explained in modern language. In fact, the odd number gi is divided by the fixed number ai, and the quotient q 1, q2, ...... ……qn and the remainder r 1, r2, ........ ……rn are obtained successively. When the odd number GI and the fixed number AI are divided, they will be divided immediately.
Qin pointed out that when rn= 1 and n is an even number, the final cn is the required multiplication rate ki. If rn= 1, and n is an odd number, divide rn- 1 by rn, and formally set qn+ 1 = RN- 1, then the remainder rn+ 1 is still 1, and then make CN+. In either case, the remainder 1 appears in the last step, and the whole calculation ends here. So Qin called his method "seeking a skill" (as for the meaning of "great Yan", Qin himself attached it to the "number of great Yan" in Zhouyi in the preface of "Nine Chapters"). It can be proved that Qin's algorithm is completely positive. The theory and careful consideration of all these systems are not simple even today, which fully shows Qin's superb mathematical level and calculation skills. When Qin was a child, he followed his father to Hangzhou, the capital of the Southern Song Dynasty, and went to Taishi Gongfu (in charge of the sky, he was very strict.
In the era of Qin dynasty, calculation was still used. On a small square plate, Qin arranged the odd number G in the upper right corner, the fixed number A in the lower right corner, and 1 in the upper left corner (he called it "Tianyuan 1"), and then interacted up and down in the right row to divide the less by the more. The obtained quotient is multiplied by the upper left corner (or bottom) and merged into the lower left corner (or top) until 1 appears in the upper right corner. The next page is Qin's general calculation schema, and on the right is a numerical example (g=20, a=27, K=C4=23).
Qin collected a large number of examples in Shu Shu Jiu Zhang, such as "ancient calendar must accumulate", "seeking sources according to regulations", "calculating earthwork" and "calculating land work", and widely used the method of "one skill at a time" to solve practical problems such as calendar, engineering, taxation and military service. In these practical problems, modular ai is not always a pairwise coprime integer. Qin distinguished different situations such as "unary number" (ai is an integer), "received number" (ai is a decimal) and "passing number" (ai is a fraction), and gave the treatment methods of each situation. The "total method" calculates the situation that "received number" and "general number" are transformed into "elements", but for the case that elements are not pairwise coprime, a reliable program is given, and the factors of those elements are appropriately selected as constants, thus turning the problem into pairwise coprime.
The official of the Institute of Literature and History studied astronomical calendars, and "seeking a skill" is probably the result of his summary of the calculation method of the cumulative years of astronomical calendars. However, it seems that "developing greatly and seeking a skill" has not been fully understood by his contemporaries. Almost lost after the middle of Ming dynasty. Until the Qing Dynasty, the theory of "seeking a skill through great development" was rediscovered, which aroused the interest of many scholars (Zhang Dunren, Li Rui, Luo, Huang Zongxian, etc. ). They explained, improved and simplified the theory of "seeking skills by extensive extension", among which Huang Zongxian's "Seeking skills by general solution" gave a more concise method for the case that the modulus was not pairwise, but the era was in the late Qing Dynasty.
From "I don't know how many" in Sun Tzu's calculation to "by extension" in Qin Dynasty, the study of a congruence formula by mathematicians in Han Dynasty occupies a glorious position not only in the history of Chinese mathematics, but also in the history of world mathematics. In Europe, the Italian mathematician Peponacci (1 170- 1250), who was contemporary with Qin, first came into contact with the first congruence formula. He gave two linear congruence problems in The Book of Algorithms, but there is no general algorithm. These two problems are similar to Sun Tzu's problems in form and data, and the overall level does not exceed Sun Tzu's calculation. Until 18 and 19 centuries, the great mathematicians Euler (1707- 1783) and Gauss (1777- 1855) lived in1855. Euler and Gauss didn't know China's work beforehand. 1815-1887 British missionary (1852) published Notes on China Science, which introduced the unknown problems in Sun Tzu's calculation and Qin's solution, and attracted the attention of European scholars. 1876, German Ma Xisen (1830- 1906) first pointed out that the solution of the grandson problem is consistent with the Gaussian method. At that time, Cantor (1829- 1920), a famous German mathematical historian, spoke highly of Da Yan Shu after reading Ma Xisen's article. Up to now, the theory of "seeking skills through extensive exploration" still arouses the strong research interest of western mathematical historians. For example, 1973, a monograph on the history of mathematics published by the United States, China Mathematics in the 13th Century, systematically introduces the achievements of China scholars in a congruence theory. Commenting on Qin's contribution, the author Libbrecht (Belgian) said: "Qin's works on indefinite analysis are quite early. With this in mind, we will see that Sutton called Qin Wei's "his nation, his that".
Indian scholars have also made important contributions to congruence theory. From the 6th century to12nd century, they developed an algorithm called "Kutaka" to solve an indefinite equation equivalent to a linear congruence. "Kutaka" method appeared after Sun Tzu's algorithm. In the works of Indian mathematicians Brahman Vodo (7th century), Mokvero (9th century) and others, there is a congruence problem, which is the same as the problem of unknowns. Of course, this is not to assert that Kutaka method must be influenced by Sun Tzu's algorithm, but that some people (such as Louis van Hée, etc. It is groundless to insist that China's "seeking a skill from great development" comes from Kutaka. Louis van Hée wrote the numbers in China's algorithm horizontally from left to right as an important basis for Indians to influence Dayan Shu. As we all know, China began to use counting and counting in ancient times at the latest from the Spring and Autumn Period and the Warring States Period. Today, we can also see this counting method from left to right from the existing money in the third century BC. This shows how ridiculous Wan Haiyi's statement is. Ancient mathematicians in China have obvious originality and inheritance in the study of a congruence theory. There is no doubt that the lofty position of "seeking a skill by extension" in the history of world mathematics. Because of this, the remainder theorem for solving a congruence group is naturally called "China's remainder theorem" in western works on the history of mathematics. Among the ancient arithmetic books in China, Sunzi Suanjing has always occupied an important position in the history of Chinese mathematics, and there are many interesting and ingenious arithmetic programs such as "insufficient skills" and "swinging cups".
Sun Tzu's calculation. The title 17 of volume 2 describes the famous "cup-throwing" program. The title is like this: "There is a woman shaking a cup on the river today. Li Jing asked, "Why are there so many cups?" The woman said,' There are guests.' Li Jing said,' What is guest geometry?' The woman said,' two people share a meal, three people share a soup, four people share meat, and each person uses a glass of 65. I don't know the guest geometry? "
Obviously, what we are told here is the number of people in 65 bowls. Among them, the information about the number of guests is that two people share a bowl of rice, three people share a bowl of soup and four people share a bowl of meat. Through these values, the problem of the number of passengers is naturally solved. Because the number of passengers is a fixed value, it is easy to get 60 passengers if it is listed as N/2+N/3+N/4=65.
The solution to this problem is exactly the same as today's solution, which can be proved by "the technique says: take 65 cups, multiply them by 12, and you get 780, and divide them by 13".