Historical development of the Chinese remainder theorem

1 Historical development of the Chinese remainder theorem SHEN KANGSHENG Communicated by C. TRUESDELL 1. Source of the Problem Congruences of first degree were necessary to calculate calendars in ancient China as early as the 2 na century Subsequently, in making the Jingchu [a] calendar (237, ), the astronomers defined shangyuan [b] 1 as the starting point of the calendar. If the Winter Solstice of a certain year occurred rl days after shangyuan and r2 days after the new moon, then that year was N years after shangyuan; hence arose the system of congruences aN ~ rl (mod 60) ~ r2 (mod b), . ~ ' where a is the number of days in a tropical year and b the number of days in a lunar month. 2. Sun Zi suanjing [c] (Master Sun's Mathematical Manual) Sun Zi suanjing (Problem 26' Volume 3) reads: "There are certain things whose number is unknown. A number is repeatedly divided by 3, the remainder is 2; divided by 5, the remainder is 3; and by 7, the remainder is 2. What will the num- ber be ?

2 " The problem can be expressed as x --= 2 (mod 3) ~ 3 (mod 5) ~- 2 (rood 7). SUN ZI solved the problem as we do, giving x ~ 140 + 63 -k 30 ~=- 233 ~ 23 (rood 105). 1 Shangyuan is a supposed moment that occurred simultaneously with the midnight of jiazi [v] (the first day of the 60 day cycle), the Winter Solstice and the new moon. 286 SHEN KANGSHENG In speaking of the algorithm yielding these addends in the solution he continued: "In general, for G1 ~ 0(mod 5) ~ 0 (mod 7) = 1 (rood 3), take G1 = 70, G2 ~ 0(rood 3) ~ 0(mod 7) ~ 1 (mod 5), take G2 = 21, G3 ~ 0 (mod 3) ~ 0 (mod 5) ~ (1 rood 7), take G3 = 15. Thus, in the present problem, if t p G l~0(mod5)~0(mod7)-~2(mod3), so G1=70 2-- 140, G2~0(mod3)~0(mod7)~3(modS), so G2=21 3= 63, Ga~0(mod3)~0(modS)~2(mod7), and G~= 15 2=30, then the required x ~ G' 1 + G~ + G'3 (rood 105)." SUN'S example is a special numerical one, which can be transformed to solve the general case: x ~ ri (mod mi) (i = 1, 2 .. , n) (1) where mi, mj are relative primes, 1 ~ i ~ j ~ n.

3 If G1 ~ 0 (mod m2) ~ 0(modma).. ~ 0 (mod ran) ~ 1 (mod m0, G2 ~ 0 (mod rn~) ~ 0 (mod m3) .. ~ 0 (mod rnn) ~ l (mod m2), (2') G~ ~- 0 (mod rnl) ~0 (mod m2) .. ~ 0 (mod rn~_l) ~ 1 (mod m~), then x ~. G'i =~ Gir i mod m i . i=1 i~l In the same way, if we get F i from r/ congruences and let MiFi : Gi ~ 1 (mod mi), then where x~ ~ G'i=--- 2 Giri =~ 2 MiFiri (mod M), i=1 i=l i=l (3') (2) (3) M = H ml, M, = M/rn i. i--I This statement is called the SuN Z~ theorem , or the Chinese remainder Theo- rem. Indeed, in imitation of the theorem , YANa HuI [d] in Xu gu zhai qi suanfa [el (Continuation of ancient mathematics for elucidating the strange, 1275) had four similar problems, three of which concerned n = 3 and the fourth n = 4, x ~ 1 (mod 2) ~ 2 (mod 5) -=-- 3 (mod 7) ~ 4 (mod 9). The Chinese remainder theorem By applying formula (2), he estimated G~ = 315, Gz = 126, Gs = 540, G,~ = 280. Substituting these in formula (3) he got the final answer: x~315 1+ 126 2 t-540 3+280 4~3307~ 157 (mod 630).)]

4 287 3. Kuttaka of India The solution of the equation ax + c = by (4) for x, y in positive integers (where a, b, c are given integers, a > b, and a, b are relatively prime) is called Kuttaka by Indian mathematicians. Literally, Kuttaka means a pulverizer, a name given on account of the process of continued division that was adopted for the solution. Legend has it that it was up to ARYABHATA (C. 476 ) to determine the integer N which when divided by a leaves the re- mainder rl, and when divided by b, leaves the remainder r2; thus N= ax + rl = by + r 2, by -- ax : c, where c : r I -- r 2 . Thus ARYABHATA discoverd a rule for the solution, which he expressed in two obscure stanzas of his Aryabhatiya. 2 In modern symbolism by B. DATTA 3, the solution can be expressed as follows. Through continued division (Euclidean algorithm) a series of quotients and corresponding remainders are as follows: qJ, qz .. , qm, rl, r2 .. rm; the relations among them are a - bql + rl, b = rlq2 + r2, r 1 = r2q 3 -~- r 3, rn_ 2 ~-- r.

5 ,_lq . + r., 2 ARYABHATA, Aryabhatiya, SHUKLA'S English Translation, 1979, Delhi, pp. 74-84. a B. DATTA & A. N. SINGH, History df Hindu Mathematics, 1938, Lahole, Vol. 2, pp. 95-99. 288 , ~ SHEN KANGSHENG, from which there is a series of reduction formulas : Y~ qlX-Jr Yl, where by~ ~ rlx + e, x ~q2Y~ + x~., where rlx~ -~ r2y~ -- e, Yl = qaxl Y2, where rzy 2 = r3x 2 -~- e, xa ~ q4Y2 ~- x2, where rax2 -- r4yz -- e, Ym--1 ~ q2m--lXm--1 -~ Ym, where r2m_2Y m z r2m_lXm_ 1 -~- c, Xm--1 ~- qzmYm -~ Xm, where r2m_lX m z r2mY m -- c. : There are two cases to consider: Case l, n,= 2m--1 .. Ym-1 ~ q2m-lXm-i -~- Ym, r2m-2Ym = r2m-aXm-I ~- e. Let Xm. 1 -k t, SO that Ym =~- (r2m-it -~- c)/r2m--2 is the integer q, and then from bottom totop by reduction formulas we Obtain the requffed x and y. Case 2, n = 2m, Xm_ 1 z q2mYm -~.Xm, r2m 1Xm ~- r2mYm -- C. r ' is the integer q'. We then obtain Let Ym ~ it, SO that x m = ( 2m t -- c)/r 2m-I X and y by using these reduction formulas from bottom to top.

6 We may note that Chapter IV of MAHAVIRA'S Ganita Sara Sangraha presents new points of view4: ' 1. Omit ql. and when x is solved, y may be determined by substituting x in equation (4). ' ' " .. 2. Continued division is carried up to rn~ 1. ' MAHAVmA'S idea is fascinating. Let us apply his suggestion to the equation ax -- 1 = by (5) and the series of quotients will be. q2m--l? q2m-2, "'', q3, q2" When r2m-1 = rn = 1, in Case 1 of Kuttaka, let X,n--1 ---- t = 1, SO that Ym ---- 0, and let ko ~ Ym ~- O, kl ~- xm-1 z 1. With the reduction formula of Kuttaka, we have k2 = Ym-1 ~ q2m-lXm-I ~ Ym q2m-lkl -k ko, k3 = Xm-- 2 = q2m-2Ym 1 -~- Xm-1 ~- q2m-2k2 -~- kl .. , 4 SRIHIVASIENGAR, The History of Ancient lndian Mathematics, 1967, Calcutta, pp. 101-102. The Chinese remainder theorem 289 and in general, thus ki = q2m+l-iki-1 @ ki-2 ~ qn+2_iki_l @ ki_2; .. x = k, = q2kn-1 4- kn-2. (6) Moreover, Indian mathematicians did much work on Kuttaka and left us many problems, such as the following.

7 Example 1. Find the number that if divided by 8 is known to leave 5, that if divided by 9 leaves a remainder 4, and that if divided by 7 leaves a remainder 1 (Aryabhatiya, annotated by BHASKARA I. the 6 th century). Example 2. Suppose at a certain time since the Kalpa, the sun, the moon etc., have travelled for the following number of days after completing their full revo- lutions: Sun Moon Mars Mercury Jupiter Saturn 1000 41 315 1000 1000 1000 Given that the sun completes 3 revolutions in 1096 days, the moon, 5 revolutions in 137 days, Mars, 1 revolution in 185 days, Mercury, 13 revolutions in 1096 days, Jupiter, 3 revolutions in 10960 days, Saturn, 1 revolution in 10960 days, find the number of days since the Kalpa (Brahmagupta, XVIII, sl 7-8, 6281) Example3. The dividends are sixteen numbers beginning with 35 and increasing successively by 3; the divisors are 32 and others increasing successively by 2; the remainders are 1 and others increasing successively by 3, What is the unknown multiplier?

8 (MAHAVlRA, Ganita Sara Sargraha, IV, 138 1/3, c. 850.) In general, in solving systems of equations x = alxl 4- rt = azx2 4- r2 = = a,x, + rn, Indian mathematicians started with the first two conditions, x =- a~x~ 4- r, ~ a2x2 4- r2. By Kuttaka one can find the minimum value of X~, say o~; then the minimum value of x will be ~ 4- r1 and hence the general solution: will be x ~- al.(azt + o ) 4- r t -~ alazt 4- a~.~ 4- rl where t is an integer. If we supply the third condition, then x ~ ala2t 4- alo~ 4- rl ~ a3x 3 ~- ra, which c~m be solved in the sam e way. Proceeding in this way successively we will have a value satisfying all the conditions. 3. ~ . 290 SnEN KANGSnENG 4. The General Dayan qiuyi [fl Rule Shu shufiu zhang [g], written by QIN JIUSHAQ [h] in 1247, was the most important mathematical work in the Song [i] dynasty. At its very beginning there is the Gener- al Dayan qiuyi Rule, discussing extensively congruences of first degree in order to solve the nine problems in Chapter I and the third problem of Chapter II.]

9 These problems are set against various natural or social backgrounds, yet all of them are expressed by systems of congruences as far as mathematics is concerned 5. Their moduli are of different types. Example 1. Solve x ~ 1 (rood 19) ~ 14 (mod 17) 1 (rood 12) (Ssjz 6, I, 9) Example 2. Solve x (mod ) (rood ) (mod ) (Ssjz, I, 5) Example 3. Solve x 0 (rood 365 4108/16900) 11 7540/16900 (mod 60) 10 7264/16900 (mod 29 8967/16900) (Ssjz, II, 3) Example 4. Solve x ~ 0 (rood 54) ~ 0 (mod 57) 51( mod 75) ~-~ 18 (rood 72) ( , I, 3) Example 5. Solve x --60 (rood t30)~ --30 (mod 110) -- --10 (mod 120) ~ --10 (mod 60) ~ 10 (mod 25) 10 (mod 100) ~ 10 (mod 30) ~ 10 (mod 20) (Ssjz, I, 8) The General Dayan qiuyi Rule is composed of four parts, as follows: , The classification of moduli Yuanshu [j]--A set of natural numbers without a gcf (greatest common factor) 7. Shoushu [k]--A set of decimals. Tongshu [1]--A set of fractions. Fushu [m]--A set of natural numbers having a gcf.

10 To convert moduli into dingshu [n]. To convert shoushu and tongshu into yuanshu QIN believed that x~ a rood a , 5 U. LIBBRECHT, Chinese Mathematics in the Thirteenth Century, 1973, MIT Press, pp. 384412. 6 We abbreviate Shu shu jiu zhang (Mathematical Treatise in Nine Chapters) as Ssjz, 7 The greatest common faetor~ of a~ b, .. C, we-denote by (a, b, .. c). The Chinese remainder theorem 291 where a, b, c are natural numbers, was the same as the congruence ax ~- b (mod c). Therefore the system of congruences in Example 2 may be converted into 100x ~ 32 (mod 83) ~ 70 (rood 110) ~ 30 (mod 135), and that in Example 3 into 6172608x ~ 193440 (mod 1014000) 163771 (rood 499067). To convert yuanshu into dingshu, QIN must have had an intimate knowledge of the Chinese remainder theorem and also the condition for solubility of the system of congruences. The moduli of nine problems in Ssjz are not relatively prime. If we solve them by the theorem directly, there would be a contradiction.