Let n and m be relatively prime [ (n,m) = 1]. Prove that a ≡ b (mod m) and a ≡ b(mod n) if and only if a ≡ b

Let n and m be relatively prime [ (n,m) = 1]. Prove that a ≡ b (mod m) and a ≡ b(mod n) if and only if
a ≡ b (mod m*n) .

One of the directions is much easier than the other. If a = b mod mn, this means by definition that a - b is a multiple of mn, ie, that there is an integer k with a - b = kmn. But then clearly a - b is a multiple of n (it is km*n) and a - b is a multiple of m (it is kn*m) and so by definition a = b mod n and a = b mod m. We never used the hypothesis that (m,n) = 1 here because it is not necessary. This direction holds for any pair of positive integers m and n.

For the converse we have to work a little and actually use the hypothesis.

It helps to have the general fact that if gcd(x,y) = 1 and x divides a product yz then x must divide z. This is usually proved by appealing to a theorem that asserts because gcd(x,y) = 1 there are integers P and Q with Px + Qy = 1. Multiplying both sides of this by z one finds that Pxz + Qyz = z. Because x divides yz there is an integer w with yz = wx and we therefore see that Pxz + Qwx = z or that z = x(Pz + Qw) and since Pz + Qw is an integer it follows that x divides z.

With that in mind, a = b mod m there is an integer k with a - b = km. Since a = b mod n there is an integer q with a - b = qn. So qn = km and hence n divides the product mk. Since gcd(n,m) = 1 we conclude that n divides k (we are applying the statement just proved with x = n, y = m, and z = k). So there is an integer p with k = pn. But then a - b = km = (pn)m = p*mn is a multiple of mn so that a = b mod mn by definition.