If gcd(m, n) = 1, Then (a ≡ b mod mn) If And Only If (a ≡ b mod m) And (a ≡ b mod n)

If \((a ≡ b \bmod m)\) and \((a ≡ b \bmod n)\):

Since \(\gcd(m, n) = 1\), we can use this lemma here:

This means \((a ≡ b \bmod mn)\).

Conversely, if \([a ≡ b \bmod mn]\), then \(mn|b-a\), but if \(mn|b-a\), then \(m|b-a\). Therefore, \([a ≡ b \bmod m]\). A similar argument can be made to show that \([a ≡ b \bmod n]\).