Shushu Jiuzhang Dayanlei 5

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

Figure 1. Qin JIushao (1202 - 1261 AD)

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:

$$\begin{cases} N &\equiv 32 \pmod{83} \\ N &\equiv 70 \pmod{110} \\ N &\equiv 30 \pmod{135} \end{cases}$$

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 $m_1 = 83, m_2 = 110, m_3 = 135$. Since the moduli are natural numbers, they are referred to as yuanshu (元數) and the remainders $r_1 = 32, r_2 = 70, r_3 = 30$.

$$\begin{cases} N &\equiv 32 \pmod{83} \\ N &\equiv 70 \pmod{110} \\ N &\equiv 30 \pmod{135} \end{cases}$$

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 $m_{1}^{'} = 83, m_{2}^{'} = 110, m_{3}^{'} = 27$. Because $30 \equiv 3 \pmod{27}$, the new remainder of the third congruence is 3. Hence, the new remainders are $r_{1}^{'} = 32, r_{2}^{'} = 70, r_{3}^{'} = 3$.

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

$$\begin{cases} N &\equiv 32 \pmod{83} \\ N &\equiv 70 \pmod{110} \\ N &\equiv 3 \pmod{27} \end{cases}$$

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

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

$M = 83 \times 110 \times 27 = 246510$

Divide the yanmu (衍母) by each moduli to obtain each yanshu(衍數) $M_i$.

$$M_1 = \frac{M}{m_{1}^{'}} = \frac{246510}{83} = 2970$$

$$M_2 = \frac{M}{m_{2}^{'}} = \frac{246510}{110} = 2241$$

$$M_3 = \frac{M}{m_{3}^{'}} = \frac{246510}{27} = 9130$$

Part 3: Determine the chenglü 求乘率

The next step is to determine the qishu (奇數) $K_i$, which satisfies $M_i \equiv K_i \pmod{m_{i}^{'}}$.

$$2970 \equiv 65 \pmod{83} \Rightarrow K_1 = 65$$

$$2241 \equiv 41 \pmod{110} \Rightarrow K_2 = 41$$

$$9130 \equiv 4 \pmod{27} \Rightarrow K_3 = 4$$

Next solve each congruence $K_i x_i \equiv 1 \pmod{m_{i}^{'}}$, where $x_i$ is called the chenglü (乘率). Qin Jiushao solves each congruence with what he calls the dayan qiuyi shu (大衍求一術), which is the Euclidean algorithm.

$$\begin{cases} 65 x_1 &\equiv 1 \pmod{83} \\ 41 x_2 &\equiv 1 \pmod{110} \\ 4 x_3 &\equiv 1 \pmod{28} \end{cases}$$

Figure 2. Dayan method

For this problem, we will demonstrate how the dayan qiuyi shu works for $65 x_1 \equiv 1 \pmod{83}$.

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

This process is also used for computing the other two linear congruences. The solution for this system is $x_1 = 23,\, x_2 = 51,\, x_3 = 7$.

Part 4: Determine the yongshu and the zongshu 求用數和總數

The yongshu (用數) are the products $M_i x_i$

$$M_1 x_1 = 2970 \times 23 = 68310$$

$$M_2 x_2 = 2241 \times 51 = 114271$$

$$M_3 x_3 = 9131 \times 7 = 63910$$

The zongshu (總數) is the sum $\sum_{i=1}^{n} M_i x_i r_{i}^{'}$

$$68310 \times 32 + 114291 \times 70 + 63910 \times 3 = 10378020$$

Part 5: Determine the minimum non-negative solution

$$10378020 \equiv 24600 \pmod{246510}$$

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