On the Chinese Remainder Theorem and Its Applications

Tapia, C.1; Tello, D.2 Faculty Mentors: Kutzko, Phil and Madison, Gene. Professors at the University of Iowa. Summer Research Opportunity Program 2000 July 28, 2000. Iowa City, Iowa

Introduction
In a book similar to that of the Arithmetic in Nine Sections, (1257 AD) written by the Chinese mathematician, Sun-tz, we encounter the first Chinese problem in indeterminate analysis. The problem says: There are things of an unknown number which when divided by 3 leaves 2, by 5 leave 3, and by 7 leave 2. What is the (smallest) number? This problem is considered to be the beginnings of the famous Chinese Remainder Theorem of Elementary Number Theory. In our process of extending the Chinese Remainder Theorem to polynomials, we found that in the particular case when the divisors are different prime polynomials of degree 1, the algorithm for finding the desired polynomial is the LaGrange Interpolation Formula found in Numerical Analysis.

The Chinese Remainder Theorem

Theorem 1. Let m and n be integers with gcd(m, n) = 1, M = mn and let b and c be any integers. Then the simultaneous congruences
x b (mod m ) and x c (mod n )

have exactly one solution with 0 x M. Proof 3: We begin by solving the congruence x b (mod m). The solution consists of all numbers of the form x = my + b . We substitute this into the second congruence, which yields my c b (mod n ).

Carmelo Tapia. Senior, University of Illinois at Chicago. 4700 S. Lawndale, Chicago, IL 60632. ctapia1@uic.edu 2 David Tello. Senior, University of Illinois at Chicago. 809 S. Damen, Chicago, IL 60612. dtello1@uic.edu 3 See [9].

We are given that gcd(m, n) = 1, so the Linear Congruence Theorem tells us that there is exactly one solution y1 with 0 y1 < n. Then the solution to the original is given by x1 = my1 + b ; and this will be the only solution x1 with 0 x < M , since there is only one y1 between 0 and n , and we multiplied y1 by m to get x1 . This completes the proof. Examples: 1. Suppose we want to solve x 8 (mod 11) and x 3 (mod 19). As stated in the proof, we write the solutions of the first congruence in the form of x = 11y + 8 and substitute it into the second congruence, which yields 11y -5 (mod 19) which is equal to 11y 14 (mod 19) and equal to 11y 33 (mod 19). Then we divide both sides of the congruence by 11 and we get y 3 (mod 19), now we can find the solution to the first congruence, x = 11y + 8 = 11 (3) + 8 = 41. Finally we want to check whether our answer is accurate, so substitute 41 for x and see that 41 8 (mod 11) = 33 0 (mod 11) and 41 3 (mod 19) = 38 0 (mod 19). 2. Now, suppose we want to solve three simultaneous congruences: x 2 (mod 3), x 1 (mod 5) and x 3 (mod 7) We write the solutions to the first congruence as x = 3y + 2 and substitute it into the second and get 3y -1 (mod 5) which is equivalent to 3y 4 (mod 5) and equal to 3y 9 (mod 5). If we divide by 3 we get that y 3 (mod 5) which can be rewritten as y = 5z + 3. Now if we substitute the solutions to the first congruence into the third, we get 3y 1 (mod 7), which is equivalent to 3 (5z + 3) 1 (mod 7) when substituting y. Evaluating, we get that 15z -8 (mod 7) which is equal to 15z 6 (mod 7). When we divide by 15 we get z 6 (mod 7). When substituting we get that x = 3y + 2 = 3 [5(6) +3] +2 = 101. Finally to check our solution of x, we noted that 101 2 (mod 3) = 99 0 (mod 3); 101 1 = 100 0 (mod 5); and 101 3 = 98 0 (mod 7). An alternative way to solve these congruences is the following:

Using the theorem, we get that M = (3)(5)(7) = 105. Let m1 = 3, m2 = 5 , and m3 = 7 ; now let b1 = 2, b2 = 1 and b3 = 3 . The integers y1 , y 2 and y3 are found by the congruence M yi 1 (mod mi ), mi thus we have 35 y1 1 (mod 3), 21y 2 1 (mod 5), and 15 y3 1 (mod 7). So y1 = -1, y2 = 1, and y3 = 1 are possible values and x = (35)(-1)(2) + (21)(1)(1) + (15)(1)(3) = -4 (mod 105) = 101. Thus, this leads us to define x as M x = yi bi (mod M). i =1 mi Remarks: Notice that in the congruences inverse of M modulus mi . mi M yi 1 (mod mi), yi is the multiplicative mi

Extension of the Theorem to Polynomials

When trying to extend the definition of the Chinese Remainder Theorem to polynomials we are presented a problem of the following kind: Example 1. Assume you have a polynomial that when it is divided by (x-1) you get remainder 3, when it is divided by (x-2) you get remainder 2 and when it is divided by (x-3), you get reminder 1. Find such a polynomial? Using the theorem, we get g ( x) = ( x 1)( x 2)( x 3). Notice that P(x) can be a polynomial of degree at most 3. Let m1 = x 1 , m2 = x 2 , and m3 = x 3 . Now let b1 = 3, b2 = 2, and b3 = -1. The polynomials y1 , y 2 , and y3 (degree 0 in this particular case) are found by the congruence M yi 1 (mod mi ), mi

we now have ( x 2 5 x + 6) y1 1 [mod (x-1)], ( x 2 4 x + 3) y 2 1 [mod (x-2)], and 1 1 ( x 2 3 x + 2) y 3 1 [mod (x-3)]. So y1 = , y 2 = 1 , and y3 = are possible values and 2 2 1 1 P = ( x 2)( x 3) (3) + ( x 1)( x 3)(1)(2) + ( x 1)( x 2) (1) = x 2 + 2 x + 2. 2 2 Thus notice the theorem could be extended to polynomials as long as the moduli mi are relatively prime to each other. Theorem 2. Let m1 ( x ), m2 ( x ),! , mr ( x) denote r prime polynomials of degree p ( p 1) that are relatively prime in pairs, and let b1 , b2 ,!, br denote any r prime polynomials of degree at most p 1 . Then the system of congruences x bi (mod mi ( x ) ), i = 1,2,!, r has a unique solution modulo g(x), where g ( x ) = mi ( x) .
i =1 r

Proof: A sketch of the proof can be found following the ideas of [3] or [5]. Assume we set mi ( x ) to be a monic and degree one, then theorem 2 becomes the following; Theorem 3.4 Let m1 ( x ), m2 ( x ),! , mr ( x) denote r prime monic polynomials of degree one that are relatively prime in pairs, and let b1 , b2 ,!, br denote any r prime polynomials of degree zero. Then the system of congruences x bi ( mod mi ( x ) ), i = 1,2,!, r has a unique solution modulo g(x), where g ( x ) = mi ( x) .
i =1 r

Proof: Let g (x) denoted the polynomial obtained by multiplying together all the mi ( x ) , since mi ( x ) is a monic polynomial of degree one we can write it as ( x ai ) , where ai is one of the x coordinates of our points. For each point (ai , bi ) , we can write the bi 1 g ( x) g ( x) M expression , for which is just and is algorithm for ( x ai ) g (ai ) ( x ai ) mi g (ai ) M We now have our familiar x = yi bi (mod M ) in the form of i =1 mi b g ( x) A note of remarkable P( x) = i ( mod g ( x) ) for polynomials. i =1 ( x ai ) g ( ai ) importance is the fact that the algorithm for P(x) is the familiar Lagrange Interpolation Formula found in Numerical Analysis. finding yi .

Connection was acquired from seminar lectures given by Phil Kutzko, Professor at the University of Iowa in the summer of 2000.

A Historical Remark
The Chinese Remainder Theorem was first presented as problem 26 of the last volume of Master Suns Mathematical Manual, which divides into three volumes, sometime before 1213 (?). Joseph Lagrange presented his interpolation formula, which is described by him as a short version of Isaac Newtons (1642-1727) interpolation formula in his Lectures at the Ecole Normale in 1795. According to [2], many of the Chinese findings n mathematics ultimately made their way to Europe via India and Arabia. The Chinese Remainder Theorem became known in Europe through article, Jottings on the science of Chinese arithmetic, by Alexander Wylie in 1853 [1]. Furthermore, [1]says that J.L. Lagrange worked on problems on Indeterminate Analysis around 1767-68. Whether there was any direct transmission of mathematical knowledge from China to the West remains a matter of conjecture. However, the possibility should not be dismissed out of hand, as many historians of mathematics are inclined to do either because they find the idea unpalatable or because there is insufficient documentary evidence. The fact remains that, as early as the third century B.C. Chinese silk and fine ironware were to be found in the markets of Imperial Rome. And a few centuries later a whole range of technological innovations found their way slowly to Europe. It is not unreasonable to argue that some of Chinas intellectual products, including mathematical knowledge, were also carried westwards to Europe, there perhaps to remain dormant during Europes intellectual Dark Ages, but coming to life once more with the cultural awakening of the Renaissance [3]. No implications can be made (at this point) on whether Lagrange was able to recognize the connection between The Chinese Remainder Theorem for polynomials and his proof on the Interpolation Formula. Moreover, it is still unknown to us if anybody has contemplated this idea before the late 1960s and early 1970s when it occurred to Phil Kutzko, who at the time was a graduate student at the University of Wisconsin.

Acknowledgements
David would like to thank Professors Phil Kutzko, Gene Madison, Daniel Anderson, Norman Johnson, and Raul Curto for their encouraging words, valuable experiences, mathematical knowledge, and support towards my future mathematical quest in graduate school as well as the entire SROP/Graduate College Staff, especially Diana J. Bryant, for their support and patience. Furthermore, he would like to thank Sharon Clarke, Leonardo Morales, and Simon Cisneros; graduate students in mathematics for treating him as one of them and taking time off from their studies to share some valuable experiences. Finally, his most deeply thank you goes to future Sharon Lima, Ph.D. for those talks and coffee time and Cindy for just being herself. Carmelo would like to thank Professor Phil Kutzko for his enthusiasm and teaching method in mathematics, it has re-kindled my interest, Professor Gene Madison for

sharing his life experiences, it has taught me greater lesson not learned in books, and Professor Daniel Anderson who has shown me that we need to put forth all our efforts to be at the top. I would like to thank the SROP/Graduate College for this wonderful opportunity and especially Diana J. Bryant and Joseph Henry for making me feel welcomed. I would like to thank David Tello for his patience and understanding of my situation and Glorimar Ramos who has inspired me to reach for greater things.

References
1. Dickson, Leonard. History of the Theory of Numbers, Volume II. Chelsea Publishing Company, 1992. pg. 57-64. 2. Eves, Howard. An Introduction to the History of Mathematics. Saunders College Publishing, 1992. pg. 212-9. 3. Gheverghese, George. The Crest of the Peacock, Non-European Roots of Mathematics. Penguin Books, 1992. pg. 204-214. 4. Goldstinen, Herman H. A History of Numerical Analysis From the 16th through the 19th Century. Springer-Verlag, 1977. pg. 68-71, 171. 5. Hungerford, Thomas.W. Algebra. Springer-Verlag, 1974. pg. 131-2. 6. Lagrange, Joseph Louis. From the French by Thomas J. McCormack. Elementary Mathematics. Chicago, 1901. pg. 146-9. 7. Lang, Serge. Algebra. Addison-Wesley, 1967. pg 63-4. 8. Niven, Ivan; Zuckerman, H.S. An Introduction to the Theory of Numbers. John Wiley & Sons, 1980. pg. 44-5. 9. Silverman, Joseph H. A Friendly Introduction to Number Theory. Prentice Hall, 1997. pg. 67-8. 10. Yan, Li, Shiran Du. Translated by John N. Crossley and Anthony W. C. Lun. Chinese Mathematics, A Concise History. Clarendon Press, 1987. pg. 93, 161-6.