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

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.
