# Qin Jiushao's dayan method: the general remainder algorithm of 1247, in Python

> Qin Jiushao's dayan method from the Shushu jiuzhang (1247): the Chinese text and a translation, his rice and dike problems, the qiuyi step and tested Python.

Published 2026-11-13, 18 min read, Ancient algorithms

Source: https://prasad.tech/blog/qin-jiushao-dayan-method/

---

In 1247 Qin Jiushao (<span lang="zh-Hant">秦九韶</span>, Ch'in Chiu-shao) dated the preface of his *Shushu jiuzhang* (<span lang="zh-Hant">數書九章</span>, *Mathematical Treatise in Nine Sections*). The book opens with the dayan method (<span lang="zh-Hant">大衍總數術</span>, *dàyǎn zǒngshù shù*), a general procedure for finding a number from its remainders by several divisors, including divisors that share factors. He worked it through 9 problems on divination, the calendar, money, grain, building works and couriers.

The [Sunzi Suanjing](/blog/chinese-remainder-theorem-sunzi-suanjing/), 8 to 10 centuries earlier, gave the multipliers 70, 21 and 15 for the divisors 3, 5 and 7 and said nothing about how to find them. Qin's method finds them for any divisors. I read the rule and 4 of his problems in Chinese, translated the core procedure, and coded it in Python. The code reproduces every number from the definite numbers to the answer in his worked solutions to the rice, dike and couriers problems ([dayan.py on GitHub](https://github.com/prasadus92/ancient-algorithms/blob/main/src/ancient_algorithms/dayan.py)). The series is [Ancient algorithms, implemented](/ancient-algorithms/).

## The problem: Qin's rice thieves

This is Qin's rice problem (<span lang="zh-Hant">餘米推數</span>), in my paraphrase:

> A rice shop reports a theft. It had 3 baskets, each filled to the brim with the same amount, which nobody recorded. The left basket now has 1 *ge* of rice left, the middle 1 *sheng* 4 *ge*, the right 1 *ge*. 3 thieves are caught. The first says he scooped from the left basket with a ladle, the second from the middle basket with a wooden shoe, the third from the remaining basket with a lacquer bowl. They ate the rice over many days and do not know how much they took. The ladle holds 1 *sheng* 9 *ge*, the shoe 1 *sheng* 7 *ge*, the bowl 1 *sheng* 2 *ge*. How much rice was lost, and how much did each thief take?

1 *sheng* is 10 *ge*, so the measures are 19, 17 and 12 *ge*, and the leftovers are 1, 14 and 1 *ge*. Each basket held a number `N` with

$$N \equiv 1 \pmod{19}, \qquad N \equiv 14 \pmod{17}, \qquad N \equiv 1 \pmod{12}$$

Qin's answer (<span lang="zh-Hant">答曰</span>): the thieves took 3,192, 3,179 and 3,192 *ge*, 9,563 *ge* in all, which he writes as 9 *shi* 5 *dou* 6 *sheng* 3 *ge*. His worked solution (<span lang="zh-Hant">草</span>) finds on the way that each basket held 3,193 *ge*.[^units]

The Sunzi recipe would solve this if someone handed you the 3 multipliers. Here they are 3,060, 1,140 and 3,553, and nothing in the Sunzi text tells you how to get them. Qin's method does.

## Who was Qin Jiushao?

- **Qin Jiushao** lived from about 1202 to 1261; both dates are uncertain. He was an official of the Southern Song. In his preface he signs himself as from Lu commandery, says he studied with the astronomical bureau in the capital as a young man and with a recluse scholar, and says he wrote in years of war.
- **The book** has 81 problems in 9 categories, by Qin's own count in the preface. The first category, *dayan*, is the remainder problem. His preface is dated the 9th month of the 7th year of Chunyou, which is 1247.
- **Why he wrote it down.** The preface says the *dayan* method is the one method missing from the *Nine Chapters*, the classic of Chinese mathematics, that nobody had been able to work it out, and that calendar makers used it a good deal while mistaking it for *fangcheng*, the array method for linear equations.

The text I read is the *Siku Quanshu* copy of 1784, titled <span lang="zh-Hant">數學九章</span> (*Shuxue jiuzhang*), which its editors rebuilt from the *Yongle dadian*. They added notes after many paragraphs, corrected numbers, and moved the general rule from after the first problem to the head of the chapter.

## The source text

### The qiuyi procedure

The core is the procedure for the multiplier, the *dayan qiuyi shu* (<span lang="zh-Hant">大衍求一術</span>), "the great extension method of finding 1". The *Siku* copy writes the variant <span lang="zh-Hant">竒</span> for <span lang="zh-Hant">奇</span>, and <span lang="zh-Hant">數</span> for <span lang="zh-Hant">術</span> in this heading. I give the standard forms, with my punctuation.

<p lang="zh-Hant">大衍求一術云：置奇右上，定居右下，立天元一於左上。先以右上除右下，所得商數與左上一相生，入左下。然後乃以右行上下，以少除多，遞互除之，所得商數隨即遞互累乘，歸左行上下。須使右上末後奇一而止，乃驗左上所得，以為乘率。</p>

<span lang="zh-Latn-pinyin">*Dàyǎn qiú yī shù yún: zhì jī yòu shàng, dìng jū yòu xià, lì tiānyuán yī yú zuǒ shàng. Xiān yǐ yòu shàng chú yòu xià, suǒ dé shāng shù yǔ zuǒ shàng yī xiāng shēng, rù zuǒ xià. Ránhòu nǎi yǐ yòu háng shàng xià, yǐ shǎo chú duō, dìhù chú zhī, suǒ dé shāng shù suíjí dìhù lěi chéng, guī zuǒ háng shàng xià. Xū shǐ yòu shàng mò hòu jī yī ér zhǐ, nǎi yàn zuǒ shàng suǒ dé, yǐ wéi chénglǜ.*</span>

| Chinese | Pinyin | Meaning |
|---|---|---|
| <span lang="zh-Hant">奇</span> | jī | the remainder, the odd amount left over |
| <span lang="zh-Hant">定</span> | dìng | the definite number, the divisor after reduction |
| <span lang="zh-Hant">右上, 右下</span> | yòu shàng, yòu xià | upper right, lower right, places on the counting board |
| <span lang="zh-Hant">天元一</span> | tiānyuán yī | the "celestial element" 1, a unit set on the board |
| <span lang="zh-Hant">商數</span> | shāng shù | the quotient |
| <span lang="zh-Hant">相生</span> | xiāng shēng | to generate together, here to multiply |
| <span lang="zh-Hant">以少除多</span> | yǐ shǎo chú duō | divide the larger by the smaller |
| <span lang="zh-Hant">遞互</span> | dìhù | in turn, alternately |
| <span lang="zh-Hant">累乘</span> | lěi chéng | multiply and accumulate |
| <span lang="zh-Hant">右上末後奇一</span> | yòu shàng mò hòu jī yī | the upper right finally has remainder 1 |
| <span lang="zh-Hant">乘率</span> | chénglǜ | the multiplier |

My translation:

> The great extension method of finding 1 says: put the remainder upper right and the definite number lower right, and set up the celestial element 1 upper left. First divide the lower right by the upper right; multiply the quotient by the 1 upper left and enter it lower left. Then divide the upper and lower numbers of the right column by each other, the smaller into the larger, in turn. Multiply each quotient as it comes by the left-hand number of the other row and add it into the left-hand number of the row that was divided. You must make the upper right end at 1, and then stop. Read the number upper left: that is the multiplier.

The text says <span lang="zh-Hant">累乘</span>, "multiply and accumulate", and leaves the addition implicit. Qin's worked solutions show it. In his first problem the last step multiplies the quotient 2 by the 1 lower left to get 2, and adds that into the 1 upper left, making 3. Wylie's 1852 summary, in his own words, calls the procedure "Finding Unity" and describes it as the alternate division of the 2 numbers by each other "till the remainder is reduced to 1".

### The reduction

Before the multipliers come the definite numbers (<span lang="zh-Hant">定數</span>). Qin's rule for divisors given as plain whole numbers begins:

<p lang="zh-Hant">元數者，先以兩連環求等，約奇弗約偶。</p>

<span lang="zh-Latn-pinyin">*Yuán shù zhě, xiān yǐ liǎng liánhuán qiú děng, yuē jī fú yuē ǒu.*</span>

> For original numbers: first take them 2 at a time, round the chain, and find their common measure; divide it out of the odd, and not out of the even.

Qin's paragraph on divisors ending in tens or hundreds (<span lang="zh-Hant">復數</span>) adds the continued common measure (<span lang="zh-Hant">續等</span>) for numbers that still share a factor: divide 1 number by it and multiply the other by it. A *Siku* editors' note applies the same move to plain whole numbers and adds that the text does not explain it in detail. Further paragraphs cover divisors with fractions.

## What the text leaves open, and what is debated

1. **What "the odd" means.** In Qin's first problem, the pair 2 and 4 has common measure 2, both numbers are even, and Qin reduces the 2. Wylie reads the rule as: divide the common measure out of the number that gives an odd quotient. The *Siku* editors read it as applying when the common measure is even, with the reverse when it is odd. The code follows Wylie. In the 4 problems of Qin's that I tested, each prime's highest power sits in only 1 of the original numbers, so the definite numbers are the same whichever number of a pair the common measure is divided out of.
2. **When the reduction is finished.** The rule gives no test for completion. The code repeats the continued common measure until the pair shares no factor.
3. **The extra steps.** Qin also takes a common divisor out of all the numbers at once (<span lang="zh-Hant">總等</span>) and adjusts the use numbers afterward (<span lang="zh-Hant">泛用</span> to <span lang="zh-Hant">正用</span>). In the divination problem the adjustment adds the extension mother 12 to the 2nd use number, turning 12, 12, 4, 9 into 12, 24, 4, 9, which add to 49, the number of yarrow stalks in the *Book of Changes*. The *Siku* editors call this fit forced. The code leaves both steps out and returns 12, 12, 4, 9; the answers do not change.
4. **Errors.** The *Siku* editors flag numbers in the text that do not work. In the pursuit problem (<span lang="zh-Hant">程行相及</span>), Qin's definite numbers for 300, 250 and 200 are 3, 125 and 16, but 16 does not divide 200; the editors correct them to 3, 125 and 8, whose product 3,000 is the least common multiple. They also say the answers to the calendar problem (<span lang="zh-Hant">古曆會積</span>) do not agree with the data, and that Qin's procedure for divisors ending in tens and hundreds cannot be fixed into a single rule; they offer a revised one.
5. **Transmission between India and China.** The sources I read document no route by which the method passed in either direction, and I treat the kuttaka and qiuyi as separate developments.

## Working the rice problem

The 3 measures, 19, 17 and 12, share no factor, so they are already the definite numbers. Then Qin's steps, with his names:

1. **Extension mother** (<span lang="zh-Hant">衍母</span>): 19 × 17 × 12 = 3,876.
2. **Extension numbers** (<span lang="zh-Hant">衍數</span>): 3,876 divided by each definite number: 204, 228 and 323.
3. **Remainders** (<span lang="zh-Hant">奇</span>): each extension number reduced by its own definite number. 204 leaves 14 with 19, 228 leaves 7 with 17, and 323 leaves 11 with 12.
4. **Multipliers** (<span lang="zh-Hant">乘率</span>), by qiuyi: 15, 5 and 11. Check: 14 × 15 = 210 = 11 × 19 + 1.
5. **Use numbers** (<span lang="zh-Hant">用數</span>): extension number times multiplier: 3,060, 1,140 and 3,553.
6. **Total** (<span lang="zh-Hant">總數</span>): each leftover times its use number, added: 1 × 3,060 + 14 × 1,140 + 1 × 3,553 = 22,573.
7. **Take away the extension mother as often as it goes**: 22,573 - 5 × 3,876 = 3,193.

Every number above is in Qin's worked solution.

Here is the qiuyi board for the first multiplier, remainder 14 and definite number 19:

<figure class="dg" aria-label="The qiuyi counting board for remainder 14 and definite number 19, in 5 states. Set-up: upper left 1, upper right 14, lower left 0, lower right 19. After 19 divided by 14: lower right 5, lower left 1. After 14 divided by 5: upper right 4, upper left 3. After 5 divided by 4: lower right 1, lower left 4. After 4 divided by 1 with quotient 3, leaving 1: upper right 1, upper left 15. The multiplier is 15.">
<div class="dg-canvas">
</div>
<figcaption>In step 4 the remainder would be 0, so the quotient is 1 smaller and the upper right ends at 1, as the text requires.</figcaption>
</figure>

## Working the reduction: the dike problem

In the dike problem (<span lang="zh-Hant">推計土功</span>), 4 counties build equal lengths of an embankment. From their labor quotas, the 4 crews build 54, 57, 75 and 72 *zhang* a day. The first 2 counties finish on a full day; the 3rd has 51 *zhang* left over and the 4th 18 *zhang*, less than a day's work. How long is each county's share?

The divisors share factors, so the Sunzi recipe cannot start. The code reduces them in pairs:

- 54 and 57 share 3. 57 ÷ 3 = 19 is odd, so 57 becomes 19.
- 54 and 75 share 3. 75 ÷ 3 = 25 is odd, so 75 becomes 25.
- 54 and 72 share 18. 54 ÷ 18 = 3 is odd, so 54 becomes 3. But 3 still shares 3 with 72, so the continued common measure moves it across: 3 and 72 become 9 and 24, then 27 and 8.
- The other pairs already share no factor.

The definite numbers are 27, 19, 25 and 8, the same as in Qin's solution.[^route] In terms of prime factors, each prime goes in full to the divisor where it appears to the highest power: 2<sup>3</sup> from 72, 3<sup>3</sup> from 54, 5<sup>2</sup> from 75, 19 from 57. Their product, 102,600, is the least common multiple of 54, 57, 75 and 72.

Then the steps run as for the rice: extension numbers 3,800, 5,400, 4,104 and 12,825; remainders 20, 4, 4 and 1; multipliers 23, 5, 19 and 1; use numbers 87,400, 27,000, 77,976 and 12,825. The total is 51 × 77,976 + 18 × 12,825 = 4,207,626, and taking away 102,600 as often as it goes leaves **1,026 *zhang*** for each county. Qin gets the same. Check: 1,026 = 19 × 54 = 18 × 57 = 13 × 75 + 51 = 14 × 72 + 18.

## Why it works

**The board.** At every step the 4 numbers keep 2 relations, modulo the definite number `m`, with remainder `a`:

$$\text{upper left} \times a \equiv \text{upper right}, \qquad \text{lower left} \times a \equiv -\,\text{lower right}$$

At the set-up, `1 × a ≡ a` and `0 × a ≡ -m ≡ 0`. A division of the lower right by the upper right subtracts `q` times the upper row from the lower row on the right, and adds `q` times the upper left to the lower left, and the minus sign makes both relations survive. The same holds for a division in the other direction. When the upper right is 1, the first relation reads `upper left × a ≡ 1`, so the upper left is the multiplier.

**Why the 1 has to be upper right.** In the board for 14 and 19, step 3 already reaches a 1, in the lower right, where the lower left is 4. By the second relation, 14 × 4 = 56 leaves `-1` with 19, which is 57 - 1. That 4 is the extended Euclidean algorithm's coefficient `-4`, without its sign. Qin's rule that the 1 must end upper right, with the last quotient made 1 smaller, flips it to `+1`: 15 = 19 - 4. All the numbers on the board stay positive, and the sign never needs tracking.

**The use numbers.** Qin checks his use numbers by adding them: the sum must be 1 more than a multiple of the extension mother (<span lang="zh-Hant">併泛課衍母多一者為正用</span>). For the rice, 3,060 + 1,140 + 3,553 = 7,753 = 2 × 3,876 + 1.

**The reduction.** Each pair step gives a prime's full power to 1 of the 2 numbers, so each prime ends in exactly 1 definite number, at its highest power. An answer for the definite numbers is then an answer for the originals, provided the original remainders agree on their shared factors.[^consistency]

## The Python

This is the method in a short form. It reproduces the rice and dike answers.

```python
from math import gcd, prod


def qiuyi(qi: int, m: int) -> int:
    """Qin's multiplier: k with qi * k leaving 1 when divided by m."""
    upper_left, upper_right, lower_left, lower_right = 1, qi, 0, m
    while upper_right > 1:
        if lower_right > upper_right:
            q = lower_right // upper_right
            lower_right -= q * upper_right
            lower_left += q * upper_left
        else:
            q = (upper_right - 1) // lower_right  # leave 1 in the upper right
            upper_right -= q * lower_right
            upper_left += q * lower_left
    return upper_left


def definite_numbers(original: list[int]) -> list[int]:
    """Coprime divisors of the originals whose product is their lcm."""
    nums = list(original)
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            g = gcd(nums[i], nums[j])
            if g > 1:
                nums[i] //= g
                while (k := gcd(nums[i], nums[j])) > 1:  # the continued common measure
                    nums[i], nums[j] = nums[i] * k, nums[j] // k
    return nums


def dayan(pairs: list[tuple[int, int]]) -> int:
    """Smallest N >= 0 leaving each remainder r with its divisor m."""
    definite = definite_numbers([m for _, m in pairs])
    mother = prod(definite)
    total = 0
    for (r, _), d in zip(pairs, definite):
        extension = mother // d
        qi = extension % d or d  # a definite number 1 gives remainder 1, as in Qin
        total += r * extension * qiuyi(qi, d)
    return total % mother


print(qiuyi(14, 19))  # 15
print(definite_numbers([54, 57, 75, 72]))  # [27, 19, 25, 8]
print(dayan([(1, 19), (14, 17), (1, 12)]))  # 3193
print(dayan([(0, 54), (0, 57), (51, 75), (18, 72)]))  # 1026
```

This short version always divides the common measure out of the first number of the pair. The [repo version](https://github.com/prasadus92/ancient-algorithms/blob/main/src/ancient_algorithms/dayan.py) follows Wylie's reading of "divide the odd", returns a record of every intermediate number, and raises an error when the remainders contradict each other. The tests check:

- Qin's own numbers: every number from the definite numbers to the answer in his rice, dike and couriers solutions, his qiuyi board for 3 and 4, the divination use numbers before his adjustment, and the *Siku* editors' correction in the pursuit problem;
- property tests with Hypothesis: qiuyi equals Python's `pow(a, -1, m)`, the kuttaka's inverse and the extended Euclidean coefficient up to 10<sup>12</sup>, and the dayan answer matches `crt` for up to 6 divisors that share factors.

## Against the kuttaka and the extended Euclidean algorithm

All 3 run the same chain of divisions. They differ in what they carry:

- **The extended Euclidean algorithm** carries 2 coefficients forward, `s` and `t`, with signs, and throws the quotients away.
- **Aryabhata's [kuttaka](/blog/kuttaka-method-extended-euclidean-algorithm/)** (499 CE) keeps every quotient in a column and folds the column from the bottom once the divisions stop. It then adds or subtracts depending on whether the count of quotients is even or odd.
- **Qin's qiuyi** carries 1 coefficient forward, the one for the remainder, split over 2 cells so that every number stays positive. Forcing the final 1 into the upper right takes the place of the sign.

The repo's [benchmark](https://github.com/prasadus92/ancient-algorithms/blob/main/benchmarks/qiuyi_vs_euclid.py) counts divisions on 1,000 random coprime pairs at each of 4 sizes, from 16 to 1,024 bits. Qiuyi used the same number of divisions as Euclid's algorithm in 506 to 521 pairs of each 1,000, and 1 fewer in the rest. It saves the last division whenever the 1 first appears in the upper right, because Euclid's algorithm goes on to divide by 1 to reach 0.

## Parallels and lineage

These are the connections I can support from sources:

- **Chinese calendar computation.** Wylie names the Tang monk Yi Xing, author of the *Dayan* calendar, as the reputed first to apply the dayan method in astronomy, and Qin's own problem 2 asks for the cycle in which the solar year, the lunar month and the 60-day cycle start together.
- **Aryabhata (499) and Bhaskara I (629).** The kuttaka solves the same problem with the same divisions in Sanskrit, about 750 years earlier.
- **Libbrecht (1973).** Ulrich Libbrecht's *Chinese Mathematics in the Thirteenth Century* studies the *Shushu jiuzhang*, including the dayan problems.

## Key takeaways

- Qin Jiushao's dayan method, from the *Shushu jiuzhang* (preface dated 1247), is a complete algorithm for the remainder problem, including divisors that share factors.
- It reduces the divisors to coprime definite numbers, finds each multiplier with the qiuyi procedure, and combines them the way Sunzi's 70, 21, 15 recipe does.
- Qiuyi runs the extended Euclidean chain of divisions and carries only the multiplier, with every number positive. It uses the same number of divisions as Euclid or 1 fewer.
- The Python reproduces every number from the definite numbers to the answer in Qin's rice, dike and couriers solutions and agrees with the incremental construction, `crt`, on random inputs.
- The code and tests are in [ancient-algorithms](https://github.com/prasadus92/ancient-algorithms). The earlier posts cover the [Sunzi problem](/blog/chinese-remainder-theorem-sunzi-suanjing/) and the [kuttaka](/blog/kuttaka-method-extended-euclidean-algorithm/).

## Sources

- Qin Jiushao, *Shushu jiuzhang* (<span lang="zh-Hant">數書九章</span>), preface dated 1247. *Siku Quanshu* copy, titled <span lang="zh-Hant">數學九章</span>, 18 juan, 1784. E-text: [Chinese Wikisource](https://zh.wikisource.org/wiki/%E6%95%B8%E5%AD%B8%E4%B9%9D%E7%AB%A0_(%E5%9B%9B%E5%BA%AB%E5%85%A8%E6%9B%B8%E6%9C%AC)). The dayan rule and problems are in juan 1, parts 1 and 2.
- A. Wylie, "Jottings on the science of the Chinese arithmetic", first published in 1852. Reprinted in [*Chinese Researches*](https://archive.org/details/chineseresearche00wyliuoft), Shanghai, 1897, pp. 159 to 194. The dayan rule is on pp. 175 to 179.
- U. Libbrecht, *Chinese Mathematics in the Thirteenth Century: The Shu-shu chiu-chang of Ch'in Chiu-shao*. MIT Press, 1973.
- *Sunzi Suanjing* (<span lang="zh-Hant">孫子算經</span>), *Siku Quanshu* copy. E-text: [Chinese Wikisource](https://zh.wikisource.org/wiki/%E5%AD%AB%E5%AD%90%E7%AE%97%E7%B6%93).

[^units]: 10 *ge* make 1 *sheng*, 10 *sheng* 1 *dou*, and 10 *dou* 1 *shi*. So 3,193 *ge* is 3 *shi* 1 *dou* 9 *sheng* 3 *ge*, as in Qin's worked solution.

[^route]: Qin's own route differs in order: he first takes 3 out of 57, 75 and 72 together, then reduces 54 by 6 to 9, then moves a 3 from 24 to 9.

[^consistency]: Qin does not check this. With divisors 4 and 6, remainders 0 and 1 have no solution, because the first makes the number even and the second odd. The repo version raises an error in that case.

---

## Common questions

**What is the dayan method?**

The dayan method (dayan zongshu shu) is Qin Jiushao's general procedure, from the Shushu jiuzhang of 1247, for finding a number that leaves given remainders with given divisors. It reduces the divisors to ones that share no factor, finds a multiplier for each with the qiuyi procedure, and combines the remainders the way the Sunzi Suanjing's 70, 21, 15 recipe does.

**Who was Qin Jiushao?**

Qin Jiushao (Ch'in Chiu-shao, c. 1202 to 1261) was a Southern Song official and mathematician. His Shushu jiuzhang, or Mathematical Treatise in Nine Sections, has a preface dated the 9th month of 1247. In it he says he studied with the astronomical bureau in the capital and with a recluse scholar.

**What does dayan qiuyi mean?**

Dayan qiuyi shu means the great extension method of finding 1. Given a remainder and a divisor that share no factor, it finds the multiplier that makes the remainder leave 1 with the divisor. Today this number is called a modular inverse.

**Is the dayan method the same as the Chinese remainder theorem?**

The dayan method is a complete algorithm for the problem the Chinese remainder theorem describes. It goes further than the Sunzi Suanjing's recipe in 2 ways: it says how to find the multipliers for any divisors, and it handles divisors that share factors.

**How does Qin Jiushao handle divisors that share a factor?**

He takes the divisors 2 at a time, divides their common factor out of one of them, and moves any factor still shared from one to the other. The result is a set of divisors with no common factor whose product is the least common multiple of the originals. In his dike problem, 54, 57, 75 and 72 become 27, 19, 25 and 8.
