# Proving $\alpha : \mathbb{Z}_{mn} \rightarrow \mathbb{Z}_m \times \mathbb{Z}_n$ is injective.

Let $m$ and $n$ be relatively prime positive integers. Define $\alpha : \mathbb{Z}_{mn} \rightarrow \mathbb{Z}_m \times \mathbb{Z}_n$ by $\alpha([a]_{mn}) = ([a]_m,[a]_n)$.

Prove that $\alpha$ is injective.

My attempt:

To prove $\alpha$ is injective, $(\forall a_1, a_2 \in \mathbb{Z})(\alpha([a_1]_{mn})=\alpha([a_2]_{mn}) \rightarrow [a_1]_{mn} = [a_2]_{mn})$ needs to be shown.

Therefore, $\alpha([a_1]_{mn})=\alpha([a_2]_{mn}) \implies ([a_1]_m, [a_1]_n) = ([a_2]_m, [a_2]_n)$, so $[a_1]_m = [a_2]_m$ and $[a_1]_n = [a_2]_n$. So, $a_1 = a_2 + c_1m$ and $a_1 = a_2 + c_2n$.

However, I don't know how to show that $a_1 = a_2 + c_3mn \implies [a_1]_{mn} = [a_2]_{mn}$.

Am I taking the correct approach at this? What am I overlooking?

-
I think that you mean that you don’t know how to get from $a_1=a_2+c_1m$ and $a_1=a_2+c_2n$ to $a_1=a_2+c_3mn$. The first says that $m\mid a_1-a_2$, the second says that $n\mid a_1-a_2$, and the desired conclusion is that $mn\mid a_1-a_2$; what do you know about relatively prime integers that would help here? – Brian M. Scott Apr 28 '12 at 14:28
Thanks for the quick response! Because $m$ and $n$ are coprime, then they have no common factors, so $a_1-a_2 = m \cdot n \cdot c_3$ must be true. I don't know how to express getting to that point mathematically, though. – Brandon Amos Apr 28 '12 at 14:45
It depends on what you’ve already proved. If you have the unique factorization theorem, you can always fall back on that. An easier way it to use the result that if $a\mid bc$, and $\gcd(a,b)=1$, then $a\mid c$, assuming that it’s available to you. You have $a_1-a_2=c_1m$ for some integer $c_1$, and you have $n\mid a_1-a_2$, so you have $n\mid c_1m$. – Brian M. Scott Apr 28 '12 at 14:51
Yes, I see now. From there, $n|c_1 \implies c_1=c_3n$ and thus $a_1-a_2=c_3mn \implies a_1=a_2+c_3mn$, correct? – Brandon Amos Apr 28 '12 at 15:07
That’s exactly right. – Brian M. Scott Apr 28 '12 at 15:10

Alternate approach:

Look at the kernel of the map $\alpha$.

If $\alpha([a])=([0],[0])$, then $[a]$ must necessarily be a multiple of both $m$ and $n$ (since $[a]_m = [a]_n = 0$).

Since $m$ and $n$ are coprime, their LCM is $mn$, thus $[a]_{mn}=[0]$.

Therefore, the kernel of $\alpha$ is $\{[0]\}$, hence $\alpha$ is injective.

(if $\alpha([a_1]) = \alpha([a_2])$, then $\alpha([a_1]-[a_2]) = ([0],[0])$ and by our argument above, $[a_1] - [a_2]$ must be $[0]_{mn}$; so $[a_1]=[a_2]$.)

-