Proof involving modulus and CRT Let m,n be natural numbers where gcd(m,n) = 1. Suppose x is an integer which satisfies
x ≡ m (mod n)
x ≡ n (mod m)
Prove that x ≡ m+n (mod mn).
I know that since gcd(m,n)=1 means they are relatively prime so then given x, gcd(x,n)=m and gcd(x,m)=n. I have trouble getting to the next steps in proving x ≡ m+n (mod mn). Which is gcd(x, mn)=m+n
 A: From the Chinese Remainder Theorem (uniqueness part) you know that, since $m$ and $n$ are relatively prime, the system of congruences has a unique solution modulo $mn$. 
So we only need to check that $m+n$ works. For that, we only need to verify that $m+n\equiv n\pmod{m}$, and that $m+n\equiv m\pmod{n}$.  That is very easy! 
A: You have to prove that $m n$ divides $x - (m + n)$. Since $\gcd(m,n) = 1$, the lcm of $m$ and $n$ is $mn$, so you have to prove that $m$ and $n$ divide $x - (m + n)$.
Let's do it for $n$. You have $x -(m+n) = (x -m) - n$, and by assumption you have that $n$ divides $x - m$.
A: Since $\rm\:x\:$ and $\rm\:x' = m+n\:$ are both solutions, it follows from CRT uniqueness that $\rm\:x \equiv x'\ (mod\ mn)\:$ since $\rm\:gcd(m,n)=1\:\Rightarrow\:\color{#C00}{lcm(m,n)} = mn.\:$ CRT uniqueness has a very simple proof, namely
$$\rm\:\begin{array}{l} x\equiv a\equiv x'\ \ (mod\ m)\\\rm x\equiv b\equiv x'\ \ (mod\ n)\end{array}\ \Rightarrow\ m,n\mid x- x'\ \Rightarrow\ lcm(m,n)\mid x-x'\ \Rightarrow\ x\equiv x'\ \ (mod\ \color{#C00}{lcm(m,n)})$$
Remark $\ $ Generally, $ $ uniqueness theorems $ $ provide very powerful tools for deducing equalities. See these prior posts for many further examples.
