Math & Physics Problems Wikia
Advertisement

The following number theory problem is from the Shushu Jiuzhang (数书九章) by Qin Jiushao (秦九韶, 1202 - 1261 AD). The solution presented here outlines Qin Jiushao's version of the Euclidean algorithm (大衍求一术 dayan qiuyi shu) and his generalized Chinese Remainder Theorem (大衍总数术 dayan zongshu shu).

Qin jiushao.jpg

Problem

Traditional Chinese

問有上農三人,力田所收之米,系用足鬥均分,各往他處出糶,甲糶與本郡官場,餘三鬥二昇。乙果與安吉鄉民,餘七鬥。丙糶與平江攬戶,餘三鬥。欲知共米及三人所分各糶石數幾何?

Simplified Chinese

问有上农三人,力田所收之米,系用足斗均分,各往他处出粜,甲粜与本郡官场,余三斗二升。乙果与安吉乡民,余七斗。丙粜与平江揽户,余三斗。欲知共米及三人所分各粜石数几何?

English Translation

There are three farmers of the highest class. As for the grain they harvested from their fields, when making use of a full standard dou, the amounts are the same. All of them go to different places to sell their grain. After selling his grain on the official markets of his own prefecture, A has 3 dou 2 sheng remaining. After selling his grain to the villagers of Anji, B has 7 dou remaining. After selling his grain to an agent from Pingjiang, C has 3 dou remaining. How much grain did the farmers have altogether, and how much did each farmer sell in terms of the respective capacity rates in dan?

In the solution, Qin Jiushao reveals that each market has a different unit of volume called hu (斛): the official market hu is 8 dou 3 sheng, the Anji hu is 1 dan 1 dou, and the Pingjiang hu is 1 dan 3 dou 5 sheng.

Since 1 dan = 10 dou = 100 sheng and 1 dou = 10 sheng, this problem is a system of indeterminate equations:

Calculate the lowest positive integer solution.


Solution

Part 1: Determine the dingshu 求定数

The initial problem begins with the moduli, which Qin Jiushao called wenshu (问数), are . Since the moduli are natural numbers, they are referred to as yuanshu (元数) and the remainders .

Notice that the second and third moduli are not coprime because 110 and 135 share a common divisor 5. This is determined by an often lengthy procedure called the lianhuan qiudeng (连环求等). Qin Jiushao’s algorithm prescribes that the congruence of odd moduli be reduced, which in this case is the third moduli. The new moduli, called dingshu (定数), are . Because , the new remainder of the third congruence is 3. Hence, the new remainders are .

Subsequently, the new problem with coprime moduli to solve is:


Part 2: Determine the yanmu and the yanshu 求衍母和衍数

First calculate the yanmu (衍母) , which is the product of the coprime moduli.

Divide the yanmu(衍母) by each moduli to obtain each yanshu(衍数) .


Part 3: Determine the chenglü 求乘率

The next step is to determine the qishu (奇数) , which satisfies .

Next solve each congruence , where is called the chenglü (乘率). Qin Jiushao solves each congruence with what he calls the dayan qiuyi shu (大衍求一术), which is the Euclidean algorithm.

Dayan method.png

For this problem, we will demonstrate how the dayan qiuyi shu works for .

Step 1: Set up the tianyuan (天元), qishu (奇数), and dingshu (定数).

天元1 奇数65
        0 定数83


Step 2: Perform the calculations and sequencing of the dayan qiuyi shu.

1 65 83 / 65 = 1 r 18

1(1) + 0 = 1

1 65
0 83 1 18


1 65 65 / 18 = 3 r 11

3(1) + 1 = 4

4 11
1 18 1 18


4 11 18 / 11 = 1 r 7

1(4) + 1 = 5

4 11
1 18 5 7


4 11 11 / 7 = 1 r 4

1(5) + 4 = 9

9 4
5 7 5 7


9 4 7 / 4 = 1 r 3

1(9) + 5 = 14

9 4
5 7 14 3


9 4 4 / 3 = 1 r 1

1(14) + 9 = 23

23 1
14 7 14 3


The solution for this system is .

Part 4: Determine the yongshu and the zongshu 求用数和总数

The yongshu (用数) are the products

The zongshu (总数) is the sum

5. Determine the minimum non-negative solution

So the total amount of rice each farmer sold 24600 sheng or 246 dan, and the total amount sold is 738 dan.

Advertisement