# The Chinese remainder theorem from the Sunzi Suanjing, worked and implemented in Python

> The Chinese remainder theorem from its oldest known source, the Sunzi Suanjing: the Chinese text with a translation, the 70, 21, 15 recipe and tested Python.

Published 2026-11-12, 16 min read, Ancient algorithms

Source: https://prasad.tech/blog/chinese-remainder-theorem-sunzi-suanjing/

---


Take a pile of things. Counted by 3s, 2 are left over. Counted by 5s, 3 are left over, and counted by 7s, 2 are left over. How many are there? The answer, 23, comes from the *Sunzi Suanjing* (<span lang="zh-Hant">孫子算經</span>), *Master Sun's Mathematical Manual*, usually dated to the 3rd to 5th century CE. It's the oldest known source of what we now call the Chinese remainder theorem.

The theorem says that if a whole number leaves known remainders when divided by several divisors that share no factor, the number is fixed up to a multiple of the product of those divisors, and there's a recipe to find it. Sunzi's recipe uses 3 fixed numbers, 70, 21 and 15, and doesn't say where they come from. I translated the problem from the Chinese, worked out where the numbers come from, and coded both the recipe as written and its general form in Python, tested against the modern construction ([sunzi.py on GitHub](https://github.com/prasadus92/ancient-algorithms/blob/main/src/ancient_algorithms/sunzi.py)). This post is part of my series [Ancient algorithms, implemented](/ancient-algorithms/).

## The problem

Call the unknown number `N`. The 3 counts say:

$$N \equiv 2 \pmod 3, \qquad N \equiv 3 \pmod 5, \qquad N \equiv 2 \pmod 7$$

The notation `N ≡ 2 (mod 3)` reads "N leaves remainder 2 when divided by 3". You can find the answer by trying numbers. The ones that leave 2 by 7s are 2, 9, 16, 23, 30 and so on, and the first of those that also leaves 3 by 5s and 2 by 3s is 23.

Trying numbers works here because 3 × 5 × 7 = 105, so there are only 105 cases. The answers repeat every 105, so 23, 128, 233 and so on all fit. With divisors in the thousands, trying numbers gets impractical. For 3, 5 and 7, the recipe below needs 3 multiplications, 2 additions and at most 2 subtractions.

## Who wrote the Sunzi Suanjing, and when

The book doesn't name an author. What we know about who wrote it and when comes from other sources:

- **The Sui dynasty history** (*Suishu*, 7th century) lists a *Sunzi Suanjing* in 2 juan (scrolls) with no author or date. The editors of the 18th-century imperial library, the *Siku Quanshu*, start from this in their summary of the book.
- **The same editors** reject the old idea that the author was Sun Wu, the military writer of the 5th century BCE. The book mentions Buddhist scriptures and the distance from Chang'an to Luoyang, which they take as language from after the Han emperor Ming (1st century CE).
- **Alexander Wylie**, writing in 1852, reports that Chinese scholars disagreed and that the more likely view put the author at the end of the Han or in the Wei, in the 3rd century.
- **Modern references** give the 3rd to 5th century CE. The date is an inference from details in the book, and it is uncertain.

The book was taught in the Tang dynasty, when the *Siku* summary says students of mathematics spent 1 year on it together with the *Wucao Suanjing*. The *Siku* editors say the old editions were long lost (<span lang="zh-Hant">舊本久佚</span>). The text I read is their copy, which they rebuilt from the *Yongle dadian*, the encyclopedia of 1408, in 3 juan.

The problem is in the third juan. It is usually cited as problem 26 of that juan; in the *Siku* copy it is the 25th, and problem numbers differ between editions.

## The text and a translation

The Chinese below follows the *Siku Quanshu* copy as transcribed on Chinese Wikisource, with Wikisource's punctuation. Pinyin is in citation tones.

**The problem.**

<p lang="zh-Hant">今有物，不知其數。三三數之，賸二；五五數之，賸三；七七數之，賸二。問：物幾何？答曰：二十三。</p>

<span lang="zh-Latn-pinyin">*Jīn yǒu wù, bù zhī qí shù. Sān sān shǔ zhī, shèng èr; wǔ wǔ shǔ zhī, shèng sān; qī qī shǔ zhī, shèng èr. Wèn: wù jǐ hé? Dá yuē: èrshísān.*</span>

**The recipe.**

<p lang="zh-Hant">術曰：三三數之，賸二，置一百四十；五五數之，賸三，置六十三；七七數之，賸二，置三十。并之，得二百三十三，以二百一十減之，即得。</p>

<span lang="zh-Latn-pinyin">*Shù yuē: sān sān shǔ zhī, shèng èr, zhì yībǎi sìshí; wǔ wǔ shǔ zhī, shèng sān, zhì liùshísān; qī qī shǔ zhī, shèng èr, zhì sānshí. Bìng zhī, dé èrbǎi sānshísān, yǐ èrbǎi yīshí jiǎn zhī, jí dé.*</span>

**The general rule.**

<p lang="zh-Hant">凡三三數之，賸一，則置七十；五五數之，賸一，則置二十一；七七數之，賸一，則置十五。一百六以上，以一百五減之，即得。</p>

<span lang="zh-Latn-pinyin">*Fán sān sān shǔ zhī, shèng yī, zé zhì qīshí; wǔ wǔ shǔ zhī, shèng yī, zé zhì èrshíyī; qī qī shǔ zhī, shèng yī, zé zhì shíwǔ. Yībǎi liù yǐshàng, yǐ yībǎi wǔ jiǎn zhī, jí dé.*</span>

### Word by word

| Chinese | Pinyin | Meaning |
|---|---|---|
| <span lang="zh-Hant">今有</span> | jīn yǒu | "now there are", the usual opening of a problem |
| <span lang="zh-Hant">物</span> | wù | things |
| <span lang="zh-Hant">不知其數</span> | bù zhī qí shù | (we) do not know their number |
| <span lang="zh-Hant">三三數之</span> | sān sān shǔ zhī | count them 3 by 3. Here <span lang="zh-Hant">數</span> is the verb *shǔ*, to count |
| <span lang="zh-Hant">賸</span> | shèng | to be left over. A variant of <span lang="zh-Hant">剩</span>, which some editions print |
| <span lang="zh-Hant">幾何</span> | jǐ hé | how many |
| <span lang="zh-Hant">答曰</span> | dá yuē | the answer says |
| <span lang="zh-Hant">術曰</span> | shù yuē | the method says |
| <span lang="zh-Hant">置</span> | zhì | set down, as counting rods on the board |
| <span lang="zh-Hant">并</span> | bìng | put together, add |
| <span lang="zh-Hant">減</span> | jiǎn | take away |
| <span lang="zh-Hant">即得</span> | jí dé | then you have it |
| <span lang="zh-Hant">凡</span> | fán | in general, whenever |
| <span lang="zh-Hant">一百六以上</span> | yībǎi liù yǐshàng | 106 or more |

### My translation

> There are some things whose number we do not know. Counted by 3s, 2 are left over; by 5s, 3 are left over; by 7s, 2 are left over. How many things are there? Answer: 23.
>
> Method: counted by 3s with 2 left over, set down 140. Counted by 5s with 3 left over, set down 63. Counted by 7s with 2 left over, set down 30. Add them to get 233, take away 210, and you have it.
>
> In general: for each 1 left over by 3s, set down 70; for each 1 left over by 5s, set down 21; for each 1 left over by 7s, set down 15. If the sum is 106 or more, take away 105, and you have it.

Alexander Wylie's 1852 English version, in his "Jottings on the science of the Chinese arithmetic", is in the public domain:

> Dividing by 3 with a remainder of 2, set down 140; dividing by 5 with a remainder of 3, set down 63; dividing by 7 with a remainder of 2, set down 30; adding these sums together gives 233, from which subtract 210, and the remainder is the number required.
>
> For 1 obtained by 3, set down 70; for 1 obtained by 5, set down 21; for 1 obtained by 7, set down 15; when the sum is 106 or above subtract 105 from it, and the remainder is the number required.
>
> A. Wylie, *Chinese Researches* (1897 reprint), p. 175

Wylie reads <span lang="zh-Hant">數之</span> as "dividing by", where I keep "counting by". The arithmetic is the same. For a complete modern English translation of the *Sunzi Suanjing* with commentary, see Lam Lay Yong and Ang Tian Se, *Fleeting Footsteps* (1992, revised 2004), which treats this problem as the earliest known statement of the remainder problem.

## What the text leaves open

The text gives the numbers but never explains them. It doesn't say:

1. **Where 70, 21 and 15 come from.** The text states them and moves on.
2. **What to do with other divisors.** The general rule covers 3, 5 and 7 only.
3. **How often to take away 105.** The rule says to take away 105 once the sum is 106 or more. The worked line takes away 210, which is 105 twice. So the rule means "as often as it goes", and the code reads it that way.
4. **Why the result is right, or that it is the only answer below 105.** There is no proof.

Wylie wrote that the general rule, the *dayan*, is met with "in embryo" in Sunzi. The full method, with a procedure for finding the multipliers for any divisors, appears in Qin Jiushao's *Shushu jiuzhang* of 1247, the subject of [the next post](/blog/qin-jiushao-dayan-method/).

## Working the example

Each of Sunzi's 3 numbers handles 1 of the 3 counts:

| Multiplier | Leaves with 3 | Leaves with 5 | Leaves with 7 |
|---|---|---|---|
| 70 | 1 | 0 | 0 |
| 21 | 0 | 1 | 0 |
| 15 | 0 | 0 | 1 |

70 leaves 1 over when counted by 3s, and 0 when counted by 5s or 7s. So 2 × 70 = 140 leaves 2 by 3s and nothing by 5s or 7s. In the same way, 3 × 21 = 63 contributes 3 left over by 5s only, and 2 × 15 = 30 contributes 2 left over by 7s only.

Adding them gives 140 + 63 + 30 = 233. That leaves 2 by 3s, 3 by 5s and 2 by 7s, because each term only affects its own count. Taking away 105, which leaves 0 with all 3 divisors, doesn't change any of the remainders. Taking it away twice gives 233 - 210 = 23.

Check: 23 = 7 × 3 + 2 = 4 × 5 + 3 = 3 × 7 + 2.

The rule works for any remainders. For a number leaving 1 by 3s, 2 by 5s and 3 by 7s: 70 + 42 + 45 = 157, and 157 - 105 = 52. Check: 52 = 17 × 3 + 1 = 10 × 5 + 2 = 7 × 7 + 3.

## How do you find the multipliers?

For 70, start from the other 2 divisors. A number that leaves 0 with both 5 and 7 is a multiple of 35. The multiples of 35 leave these remainders with 3:

- 35 leaves 2,
- 70 leaves 1.

So 70 is the first multiple of 35 that leaves 1 with 3. In the same way, 21 is the first multiple of 3 × 7 = 21 that leaves 1 with 5, since 21 = 4 × 5 + 1. And 15 is the first multiple of 3 × 5 = 15 that leaves 1 with 7, since 15 = 2 × 7 + 1.

In general, with divisors `d1, d2, ..., dk` that share no factor and product `P`, the multiplier for `di` is

$$e_i = \frac{P}{d_i} \cdot u_i, \qquad \text{where } \frac{P}{d_i} \cdot u_i \text{ leaves 1 when divided by } d_i$$

Finding `u_i` is finding a modular inverse: the number that, multiplied by `P/di`, leaves 1 with `di`. For 3, 5 and 7 you can find it by trying 1 or 2 numbers. For large divisors you need a method, and the 2 older methods in this series are Aryabhata's [kuttaka](/blog/kuttaka-method-extended-euclidean-algorithm/) of 499 CE and Qin Jiushao's *qiuyi* of 1247. Today we use the extended Euclidean algorithm.

## Why it works

Write the answer as

$$N = r_1 e_1 + r_2 e_2 + \dots + r_k e_k$$

Divide by `d1`. Every `e_i` except `e1` is a multiple of `d1`, so those terms leave nothing. `e1` leaves 1, so `r1 × e1` leaves `r1`. So `N` leaves `r1` with `d1`, and the same argument works for each divisor.

The answer is fixed up to a multiple of `P`. If 2 numbers leave the same remainders with every `di`, their difference is divisible by every `di`, and since the `di` share no factor, the difference is divisible by their product `P`. So exactly 1 answer lies between 0 and `P - 1`, and taking away `P` as often as it goes finds it. For Sunzi, `P = 105`.

The recipe needs divisors that share no factor. With divisors 4 and 6, no number leaves 0 with 4 and 1 with 6, because the first makes it even and the second makes it odd. And no multiple of 6 leaves 1 with 4, so the recipe has no multiplier to give.

## The Python

Below is the recipe as the text states it, then the general form.

```python
from math import prod


def sunzi_recipe(by_threes: int, by_fives: int, by_sevens: int) -> int:
    """Sunzi's recipe as stated, for counts by 3s, 5s and 7s."""
    total = 70 * by_threes + 21 * by_fives + 15 * by_sevens
    while total >= 106:  # "106 or more, take away 105"
        total -= 105
    return total


def sunzi_multipliers(divisors: list[int]) -> list[int]:
    """For each divisor, the multiple of all the others that leaves 1 with it."""
    period = prod(divisors)
    return [period // d * pow(period // d, -1, d) for d in divisors]


def sunzi_general(pairs: list[tuple[int, int]]) -> int:
    """Smallest N >= 0 with N % d == r for each (r, d); the d must share no factor."""
    multipliers = sunzi_multipliers([d for _, d in pairs])
    total = sum(r * m for (r, _), m in zip(pairs, multipliers))
    return total % prod(d for _, d in pairs)


print(sunzi_recipe(2, 3, 2))  # 23
print(sunzi_multipliers([3, 5, 7]))  # [70, 21, 15]
print(sunzi_general([(1, 19), (14, 17), (1, 12)]))  # 3193
```

`pow(x, -1, d)` is Python's built-in modular inverse. The [repo version](https://github.com/prasadus92/ancient-algorithms/blob/main/src/ancient_algorithms/sunzi.py) checks its inputs and uses `mod_inverse_euclid` from the kuttaka module. The tests check:

- Sunzi's answer, 23, and each line of the worked recipe: 140, 63, 30, 233 and 210;
- that 70, 21 and 15 each leave 1 with their own divisor and 0 with the others, and that `sunzi_multipliers` rebuilds them from 3, 5 and 7;
- Qin Jiushao's rice problem, 3,193, through the general recipe;
- all 105 combinations of remainders: the recipe as stated gives a number below 105 with those remainders, the same as `crt` and the kuttaka's `remainder_problem`;
- property tests with Hypothesis: for random pairwise coprime divisors up to 10,000, the general recipe agrees with `crt`.

## Against the modern method

The textbook statement of the Chinese remainder theorem is Sunzi's recipe with letters in place of numbers. Carl Friedrich Gauss gave it in this form in his *Disquisitiones Arithmeticae* of 1801, articles 32 to 36, the book that introduced the `≡` notation for congruences. I call this the sum-of-products form: `N = r1 e1 + ... + rk ek` with `e_i = (P/d_i) × u_i`. It is the construction in number theory courses today.

The other common form is incremental. It folds the congruences in 1 at a time: solve the first 2, replace them with 1 congruence modulo their least common multiple, add the next, and so on. `crt` in the kuttaka module works this way, and Bhaskara I combined 3 divisors this way in 629 CE. The 2 forms give the same answer:

```python
>>> from ancient_algorithms.sunzi import sunzi_general
>>> from ancient_algorithms.kuttaka import crt
>>> pairs = [(2, 3), (3, 5), (2, 7)]
>>> sunzi_general(pairs), crt(pairs)
(23, 23)
```

In practice they differ in 2 ways:

- **The sum-of-products form** computes all the multipliers first, from the divisors alone. If the same divisors come up again with new remainders, the multipliers are reused, and the answer costs k multiplications and a reduction. That is the situation Sunzi's general rule describes: 70, 21 and 15 serve every problem with 3, 5 and 7.
- **The incremental form** handles divisors that share a factor, as long as the remainders agree on it, and its numbers stay smaller along the way. RSA decryption uses it with 2 divisors: it computes modulo each secret prime separately and recombines with 1 precomputed constant.[^rsa]

## Can you give an example question for the Chinese remainder theorem?

Sunzi's problem is the oldest known one. Bhaskara I and Qin Jiushao each posed one later:

- **Bhaskara I (629 CE).** Which number leaves 5 when divided by 12, and 7 when divided by 31? The answer is 317. The [kuttaka post](/blog/kuttaka-method-extended-euclidean-algorithm/) works it through.
- **Qin Jiushao (1247).** 3 baskets held the same amount of rice. Thieves emptied them with a ladle of 19 *ge*, a wooden shoe of 17 *ge* and a bowl of 12 *ge*, leaving 1, 14 and 1 *ge*. How much did each basket hold? The answer is 3,193 *ge*. The [dayan post](/blog/qin-jiushao-dayan-method/) works it through with Qin's own numbers.

## Parallels and lineage

These are the connections I can back up with sources:

- **Aryabhata, *Aryabhatiya* (499 CE), and Bhaskara I's commentary (629 CE).** A general procedure for the 2-divisor remainder problem, extended by Bhaskara I to 3 or more divisors. See the [kuttaka post](/blog/kuttaka-method-extended-euclidean-algorithm/).
- **Qin Jiushao, *Shushu jiuzhang* (1247).** The general Chinese method, with a procedure for the multipliers and a way to handle divisors that share factors. Wylie, in 1852, says Qin's text first lets a reader see how Sunzi's numbers were obtained.
- **Gauss, *Disquisitiones Arithmeticae* (1801).** The general statement in the language of congruences.
- **Wylie (1852).** His "Jottings" brought Sunzi's problem and Qin's method to readers of English.

## What is debated

- **The date of the *Sunzi Suanjing*.** The 3rd to 5th century range rests on internal evidence and on the Sui bibliography. No dated manuscript of the period survives, and the text we read was rebuilt in the 18th century.
- **The problem number.** Editions differ in how they divide and count the problems.
- **What Sunzi knew.** The book gives 1 problem and fixed multipliers. Whether its author had a general method for finding multipliers, or found 70, 21 and 15 by trial, cannot be read from the text.
- **Whether to call it a theorem.** The text states no general claim and no proof. The name "Chinese remainder theorem" is modern and refers to the problem's origin.
- **Transmission.** Remainder problems appear in Chinese, Indian and later European sources. The sources I have read document no route by which this problem or its method passed between them.

## Key takeaways

- The Chinese remainder theorem's oldest known source is a problem in the *Sunzi Suanjing* (3rd to 5th century CE, uncertain): remainders 2, 3 and 2 by 3s, 5s and 7s give 23.
- Sunzi's 70, 21 and 15 are numbers that leave 1 with their own divisor and 0 with the other 2. Multiplying each remainder by its number and adding gives the answer, up to multiples of 105.
- Finding such numbers for any divisors needs a modular inverse. The text doesn't show how. Aryabhata's kuttaka (499) and Qin Jiushao's qiuyi (1247) do.
- Gauss's 1801 statement is the same sum-of-products construction for any coprime divisors. The incremental form folds the congruences in 1 at a time and gives the same answer.
- The code and tests are in [ancient-algorithms](https://github.com/prasadus92/ancient-algorithms). The next post in the series covers [Qin Jiushao's dayan method](/blog/qin-jiushao-dayan-method/).

## Sources

- *Sunzi Suanjing* (<span lang="zh-Hant">孫子算經</span>), *Siku Quanshu* copy, 3 juan. E-text: [Chinese Wikisource](https://zh.wikisource.org/wiki/%E5%AD%AB%E5%AD%90%E7%AE%97%E7%B6%93). The *Siku* summary of the book is printed at the head of the page.
- 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 remainder problem is on pp. 175 to 176.
- Lam Lay Yong and Ang Tian Se, *Fleeting Footsteps: Tracing the Conception of Arithmetic and Algebra in Ancient China*. World Scientific, 1992; revised edition 2004. A full English translation of the *Sunzi Suanjing*.
- U. Libbrecht, *Chinese Mathematics in the Thirteenth Century: The Shu-shu chiu-chang of Ch'in Chiu-shao*. MIT Press, 1973. On Qin Jiushao's book, including its remainder problems.
- C. F. Gauss, *Disquisitiones Arithmeticae*, 1801, articles 32 to 36.

[^rsa]: PKCS #1 (RFC 8017) stores the constant in the private key as `qInv`, the inverse of `q` modulo `p`, and recombines with Garner's formula `m = m2 + q × ((m1 - m2) × qInv mod p)`.

---

## Common questions

**What is the Chinese remainder theorem?**

If you know the remainders of a whole number when it is divided by several divisors that share no factor, the number is fixed up to a multiple of the product of the divisors, and there is a construction that finds it. With divisors 3, 5 and 7 and remainders 2, 3 and 2, the number is 23, or 23 plus any multiple of 105.

**Can you give an example question for the Chinese remainder theorem?**

The oldest known one is in the Sunzi Suanjing (3rd to 5th century CE): find a number that leaves 2 when counted by 3s, 3 when counted by 5s and 2 when counted by 7s. The answer is 23. A harder one is Qin Jiushao's rice problem of 1247: 3 equal baskets of rice were emptied with measures of 19, 17 and 12 ge, leaving 1, 14 and 1 ge. Each basket held 3,193 ge.

**Where do 70, 21 and 15 come from in Sunzi's problem?**

Each is a multiple of the other 2 divisors that leaves 1 with its own divisor. 70 is a multiple of 5 and 7 and leaves 1 when divided by 3. 21 is a multiple of 3 and 7 and leaves 1 when divided by 5. 15 is a multiple of 3 and 5 and leaves 1 when divided by 7. The Sunzi Suanjing gives the numbers without saying how they were found.

**When was the Sunzi Suanjing written?**

The date is uncertain. Modern references give the 3rd to 5th century CE. The arguments rest on details inside the book, such as its mention of Buddhist scriptures and of the distance from Chang'an to Luoyang, and on its listing in the bibliography of the Sui dynasty history.

**Does the Chinese remainder theorem work when the divisors share a factor?**

A solution exists only when the remainders agree on the shared factor, and the answer is then fixed up to the least common multiple. Sunzi's recipe does not cover this case. Qin Jiushao's dayan method of 1247 first replaces the divisors with ones that share no factor.
