Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
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. –  highphi Apr 28 '12 at 14:45
1  
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? –  highphi Apr 28 '12 at 15:07
1  
That’s exactly right. –  Brian M. Scott Apr 28 '12 at 15:10

1 Answer 1

up vote 5 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.