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.
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 (孫子算經), 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). This post is part of my series Ancient algorithms, implemented.
The problem
Call the unknown number N. The 3 counts say:
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 (舊本久佚). 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.
今有物,不知其數。三三數之,賸二;五五數之,賸三;七七數之,賸二。問:物幾何?答曰:二十三。
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.
The recipe.
術曰:三三數之,賸二,置一百四十;五五數之,賸三,置六十三;七七數之,賸二,置三十。并之,得二百三十三,以二百一十減之,即得。
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é.
The general rule.
凡三三數之,賸一,則置七十;五五數之,賸一,則置二十一;七七數之,賸一,則置十五。一百六以上,以一百五減之,即得。
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é.
Word by word
| Chinese | Pinyin | Meaning |
|---|---|---|
| 今有 | jīn yǒu | "now there are", the usual opening of a problem |
| 物 | wù | things |
| 不知其數 | bù zhī qí shù | (we) do not know their number |
| 三三數之 | sān sān shǔ zhī | count them 3 by 3. Here 數 is the verb shǔ, to count |
| 賸 | shèng | to be left over. A variant of 剩, which some editions print |
| 幾何 | jǐ hé | how many |
| 答曰 | dá yuē | the answer says |
| 術曰 | shù yuē | the method says |
| 置 | zhì | set down, as counting rods on the board |
| 并 | bìng | put together, add |
| 減 | jiǎn | take away |
| 即得 | jí dé | then you have it |
| 凡 | fán | in general, whenever |
| 一百六以上 | 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 數之 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:
- Where 70, 21 and 15 come from. The text states them and moves on.
- What to do with other divisors. The general rule covers 3, 5 and 7 only.
- 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.
- 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.
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
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 of 499 CE and Qin Jiushao's qiuyi of 1247. Today we use the extended Euclidean algorithm.
Why it works
Write the answer as
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.
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 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_multipliersrebuilds 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
crtand the kuttaka'sremainder_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:
>>> 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.1
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 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 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.
- 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. The next post in the series covers Qin Jiushao's dayan method.
Sources
- Sunzi Suanjing (孫子算經), Siku Quanshu copy, 3 juan. E-text: Chinese Wikisource. 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, 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.
Footnotes
-
PKCS #1 (RFC 8017) stores the constant in the private key as
qInv, the inverse ofqmodulop, and recombines with Garner's formulam = 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.