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

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$.
