[PDF] Historical development of the Chinese remainder theorem

View - Download Historical development of the Chinese remainder theorem

Previous PDF

Next PDF

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 B.C. Subsequently, in making the Jingchu [a] calendar (237,A.D.), 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 ?" 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. 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, i.e. 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). 287 3. Kuttaka of India 3.1. 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 A.D.) 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 i.e. 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.,_lq . + r., 2 ARYABHATA, Aryabhatiya, K.S. 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.

3.2. 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 C.N. 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)

3.3. Moreover, Indian mathematicians did much work on

Kuttaka and left

us many problems, such as the following. 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? (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 al.o~ 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. 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 0.32 (mod 0.83)

0.70 (rood 1.10)

0.30 (mod 1.35)

(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)

(Ss.iz, 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:

4.1, 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.

4.2. To convert moduli into

dingshu [n].

4.2.1. 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). 4.2.2. To convert yuanshu into dingshu, QIN must have had an intimate knowledge

quotesdbs_dbs21.pdfusesText_27

[PDF] chinese remainder theorem tutorialspoint

[PDF] chinese remainder theorem word problems

[PDF] chinese remainder theorem word problems pdf

[PDF] chinese students abroad

[PDF] chinese students in canada statistics 2018

[PDF] chinese students in france

[PDF] chinese will be the next world language

[PDF] chino jail inmate search

[PDF] chiropractic school

[PDF] chiropractor average salary uk

[PDF] chiropractor cost

[PDF] chiropractor definition

[PDF] chiropractor hmsa

[PDF] chiropractor houston

[PDF] chiropractor jobs uk