Prove co-prime exist

Question

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

Answer 1

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

Answer 2

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?