# Functions on Congruence Classes

Given the function $f: \frac{\mathbb Z}{mn\mathbb Z} \rightarrow \frac{\mathbb Z}{m\mathbb Z} \times \frac{\mathbb Z}{n\mathbb Z}$ defined by $f([a]_{mn}) = ([a]_m, [a]_n)$.

I must:

Show that $f$ is well-defined.

Show that if $m=6$ and $n=10$ that $f$ is neither injective nor surjective.

Show in general that if $m,n$ have a common divisor $d>1$, then $f$ is neither injective nor surjective.

-
Good. What have you done to work towards that goal? –  Alex Youcis Apr 13 '12 at 5:27
Sorry, I am a bit confused by the initial ordered pair notation given in the function. I am not sure how to proceed given that. –  Dominick Gerard Apr 13 '12 at 5:29
The codomain of $f$ is the Cartesian product of two sets. The elements of a Cartesian product are ordered pairs, the first component coming from the first set in the product, the second from the second. So $([a]_m,[a]_n)$ just means the ordered pair where the first entry is the class of the integer $a$ in ${\bf Z}/m{\bf Z}$ and the second entry is the class of $a$ in ${\bf Z}/n{\bf Z}$. Does that explain the ordered pair notation? –  Gerry Myerson Apr 13 '12 at 5:34
yes, thank you very much –  Dominick Gerard Apr 13 '12 at 5:43
this is famous exercise in abstract algebra –  Babak Miraftab Apr 13 '12 at 6:58

If $[a]_{mn}=[b]_{mn}$ then $mn\ |\ b-a$ so in particular $m | b-a$ and $n|b-a$. Thus the map $f$ is well-defined. Now, if $m=6$ and $n=10$ then $f(30)=0$ but $30\not\equiv 0(mod 60)$ hence $f$ is not injective. On the other hand, since both groups have the same size a function is injective if and only if is surjective. Therefore, $f$ is not surjective too. Using the same idea we can handle the general case.