The Chinese Remainder Theorem (Ta-Yen)

It was not until 1247 that Qin Jiushao (c 1202-1261) published a general method for solving systems of linear congruence's in his book called 'Shushu jiuzhang (Mathematical Treatise in Nine Sections)' (Katz, 1992, p188). A book clearly influenced by the old chiu chang suan shu, as were a majority of Chinese mathematical works. Before this time only specific problems had been solved, by people such as Shu Zi (late third century). This method became known as the Ta-Yen. The basic format of problems it was to solve was ; N = a(mod b) = c(mod d) = ... This meant find N such that when divided by b gives a remainder of a and when divided by d gives a remainder of c.

Throughout this page we will use the example
N = 10(mod 12) = 0(mod 11) = 0(mod 10) = 4(mod 9) = 6(mod 8) = 0(mod 7) = 4(mod 6)

In simple terms the method goes like this :

1. Find the least common multiple of the moduli.
In our example the moduli are 12,11,10,9,8,7 and 6.

How was this done? Reduce all moduli to a multiplication of prime numbers or their powers, unless they are already prime or a power of a prime alone.

12 = 2x2 x 3, 11 = 11 (already a prime), 10 = 2 x 5, 9 = 3x3, 8 = 2x2x2, 7 = 7 (already a prime) and
6 = 2 x 3

Leave any moduli which is a prime or only the power of a prime as it is. In all the other moduli cancel out any of these occurrences. If no numbers are left assign it a 1. 'The new relatively prime moduli, are called the dingshu' (Katz, 1992, p188) and are represented by mi for each i.

m1 = 1, m2 = 11, m3 = 5, m4 = 9, m5 = 8, m6 = 7 and m7 = 1

The least common multiple (yenmu O) is the product of the dingshu.

In our specific case yenmu O = 11x5x9x8x7 = 27720.

2.Divide the yenmu by each of the dingshu in turn to get yenshu.
Represent these as Mi for each i. Mi = yenmu O/mi.

In our specific case Mi = 27720/mi

M1 = 27720/1 = 27720, M2 = 27720/11 = 2520, M3 = 27720/5 = 5544, M4 = 3080, M5 = 3465, M6 = 3960 and M7 = 27720

3.Subtract from each of the yenshu as many copies of the corresponding dingshu as possible, and take the remainder.
Represent these as Ni for each i.

N1 = 27720 - 27720x1 = 0, N2 + 2520 - 229x11 = 1, N3 = 5544 - 1108x5 = 4, N4 = 2, N5 = 1, N6 = 5 and N7 = 0

4.Solve for xi using Nixi = 1(mod mi).
These solutions are called the chenglu. When Ni = 0, xi = 0.

x1 = x7 = 0 (as Ni = 0 where i = 1,7)
1x2 = 1(mod 11), x2 = 1
4x3 = 1(mod 5), x3 = 4
2x4 = 1(mod 9), x4 = 5
1x5 = 1(mod 8), x5 = 1
5x6 = 1(mod 7), x6 = 3

5.Multiply each xi by the corresponding Mi and ri.
Where ri is the original remainder. These solutions are called the tsungshu.

In our specific case, these values are nonzero only for i = 4 and i = 5.
rMx4 = 4 x 3080 x 5 = 61600
rMx5 = 6 x 3465 x 1 = 20790

6.Sum these values.

61600 + 20790 = 82390

7.Reduce the sum by twice the yenmu to get N.

82390 - 2x27720 = 26950

***Therefore the solution is N = 26,950.***

All of these calculations are summarised in the table below.

NOTE: This method was taken from Katz (1992) but written in my own words which I believe to be easier to understand.

select here to
return to the Chinese home page