Prove co-prime exist Firstly:
$[a]_m$ means $a \pmod m$


*

*$m$ is co-prime with $n$, $\gcd(m,n)=1$

*$[a_1]_{m}$ is coprime with $m$, $\gcd(a_1,m)=1$

*$[a_2]_{n}$ is coprime with $n$, $\gcd(a_2,n)=1$


I find $x$ so that $[x]_m = a_1$ and $[x]_n = a_2$ (I used chinese remainder algo) 
But my problem is the following, I need to prove that also
$[x]_{mn}$ is coprime with $m \cdot n$.
 A: You know that $x\equiv a_1\pmod{m}$ and $x\equiv a_2\pmod{n}$; thus
$$
x=um+a_1,\qquad x=vn+a_2
$$
Suppose $p$ is a prime divisor of $x$ and $mn$. Then either $p$ divides $m$ or $p$ divides $n$. Suppose $p$ divides $m$: you have $x=px'$ and $m=pm'$, so
$$
a_1=p(x'-um')
$$
Can you finish?
A: Since $m$ is coprime with $n$ then there is some $N$ such that $$[m]_n[N]_n=[1]_n$$
Likewise, there is $M$ such that $$[n]_m[M]_m=[1]_m$$
Therefore $$x=a_1nM+a_2mN$$ satisfies $[x]_m=[a_1nM+a_2mN]_m=[a_1]_m[n]_m[M]_m=[a_1]_m$ and $[x]_n=[a_1nM+a_2mN]_n=[a_2]_n[m]_n[N]_n=[a_2]_n$.
Now we can look at the coprimarity with $nm$.
Any prime dividing $n$ divides $a_1nM$. Therefore, for it to divide $x$ it would need to divide $a_2mN$. But $a_2$ is coprime with $n$, therefore $p$ doesn't divide $a_2$. It doesn't divide $m$ because $m$ and $n$ are also coprime. Finally, $n$ and $N$ are coprime because $[m]_n[N]_n=[1]_m$. Otherwise $p$ would divide $1$.
A similar argument shows that a prime that divides $m$ can't divide $x$.
