349
pages

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).

## Problem

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.

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.