Suppose gcd(n,m) = 1. Prove that for any integers a,b in Z, there exists x in Z
ID: 1892988 • Letter: S
Question
Suppose gcd(n,m) = 1. Prove that for any integers a,b in Z, there existsx in Z such that x = a mod m and x = b mod n. (This result is known
as the Chinese Remainder Theorem.)
Hints: Using properties of the gcd, express a as a linear combination of n
and m, and do the same for b. Then let x be the sum of two of the terms
you get, one from the a expression and one from the b expression.
Explanation / Answer
gcd(n,m) = 1 -> there exists integers u and v in Z such that: un + vm = 1 -> vm (mod n) = 1 So we have: Consider t = (b-a)v. Note that x = a + tm satisfies (x = a mod m and x = b mod n): x mod m = a + t*0 = a (mod m) x mod n = a + (b-a)vm (mod n) = (a + b-a) (mod n) = b (mod n)