Let m1, m2, , mn be pairwise relatively prime positive

Chapter 5, Problem 40

(choose chapter or problem)

Let m1, m2, , mn be pairwise relatively prime positive integers (that is, gcd(mi , mk) = 1 for 1 i, k n, i k), let m = m1m2cmn, and let a1, a2, c, an be any integers. Then there is an integer x such that x a1 (mod m1) x a2 (mod m2) ( x an (mod mn) and any other integer y that satisfies these relations is congruent to x modulo m. This result is known as the Chinese remainder theorem (based on work done by the Chinese mathematician Sun-Tsu in the first century ad). The following steps will prove the Chinese remainder theorem. a. Let s and t be positive integers with gcd (s, t) = 1. Prove that there exists an integer w such that sw 1 (mod t). b. For each i, 1 i n, let Mi = mmi. Prove that gcd(Mi , mi ) = 1. c. Prove that there is an integer xi such that Mi xi 1 (mod mi ) and ai Mi xi ai (mod mi ). d. Prove that akMk xk 0 (mod mi ) for all k i. e. Let x = a1M1x1 + a2M2x2 + c+ anMn xn. Prove that for 1 i n, x ai (mod mi ). f. Let y be such that y ai (mod mi ), 1 i n. Prove that x y (mod m). (Hint: Use the fundamental theorem of arithmetic and write m as a product of distinct primes, m = pk1 1 pk2 2 pkt t ).