# [SOLVED] Abstract Algebra: Homomorphisms

• Mar 16th 2008, 08:00 AM
Jhevon
[SOLVED] Abstract Algebra: Homomorphisms
Hello all,

I'd like you to check my work. I have this nagging feeling that I am missing something, or worst yet, that my proof has some error I can't see.

Problem:

(b) For which pairs $m,n$ is $\beta : \mathbb{Z}_m \to \mathbb{Z}_n$ by $\beta ([a]_m) = [a]_n$ well defined?

Solution:

We claim that this is true for pairs $m,n$ iff $n \mid m$. Thus we need to show $(a \equiv b~(\mbox{mod }m) \implies a \equiv b~(\mbox{mod }n)) \Longleftrightarrow n \mid m$.

Proof:

( $\Leftarrow$): Assume $n \mid m$. Then $m = tn$ for some $t \in \mathbb{Z}$. So, $a \equiv b~(\mbox{mod }m) \Longleftrightarrow b - a = mk \implies b - a = n(tk) \Longleftrightarrow a \equiv b~(\mbox{mod }n)$ for some $k \in \mathbb{Z}$.

( $\Rightarrow$): For the converse, we use the contrapositive. Assume $n \nmid m$. Then by the Division Algorithm, $n = qm + r$, $0 < r < m$, for unique $q,r \in \mathbb{Z}$. So $m = \frac {n - r}q$ (which is an integer by hypothesis). Thus, $a \equiv b~(\mbox {mod }m) \Longleftrightarrow b - a = mk$, for some $k \in \mathbb{Z}$, which implies $b - a = \left( \frac {n - r}q \right)k = \left( \frac nq \right)k - \left( \frac rq \right)k \ne nl$ for any $l \in \mathbb{Z}$. Thus, $n \nmid (b - a)$, which means $a \not \equiv b~(\mbox{mod }n)$.

QED

I don't like the second part of the proof too much, the part where i said not equal to nl mostly. Plus, this is just an observation of mine that I saw and proved, how do I know these are the only m and n for which this works?

Thanks all
• Mar 16th 2008, 08:33 AM
ThePerfectHacker
Quote:

Originally Posted by Jhevon
(b) For which pairs $m,n$ is $\beta : \mathbb{Z}_m \to \mathbb{Z}_n$ by $\beta ([a]_m) = [a]_n$ well defined?

You need to prove that if $n|m$ then the homomorphism is well-defined, i.e. if $a\equiv b(\bmod m)\implies a\equiv b(\bmod n)$ (for all $a,b$). And conversely, i.e. if $a\equiv b(\bmod m)\implies a\equiv b(\bmod n)$ (for all $a,b$) then $n|m$. You proved the first part correctly. We can do it easier. If $a\equiv b(\bmod m)$ then $m|(a-b)$ since $n|m$ it means $n|(a-b)\implies a\equiv b(\bmod n)$ (divisibility is transitive). For the second part you overkilled it. Assume that $a\equiv b(\bmod m)\implies a\equiv b(\bmod n)$ (for all $a,b$), choose $a=m,b=0$ then $a\equiv b(\bmod m)$ and so $a\equiv b(\bmod n)\implies m\equiv 0(\bmod n)\implies n|m$.

Quote:

how do I know these are the only m and n for which this works?
Because you proved it both ways. You said if it is well-defined then it can only be when $n|m$. And then you should that if $n|m$ then it is well-defined. Thus, you found precisely the numbers for which is works.
• Mar 16th 2008, 08:40 AM
Jhevon
Quote:

Originally Posted by ThePerfectHacker
... Assume that $a\equiv b(\bmod m)\implies a\equiv b(\bmod n)$ (for all $a,b$), choose $a=m,b=0$ then $a\equiv b(\bmod m)$ and so $a\equiv b(\bmod n)\implies m\equiv 0(\bmod n)\implies n|m$.

so it does not matter that we choose particular a and b though we want to show it for all a and b?
• Mar 16th 2008, 08:56 AM
ThePerfectHacker
Quote:

Originally Posted by Jhevon
so it does not matter that we choose particular a and b though we want to show it for all a and b?

All you want to show $n|m$ given that it works for all $a,b$. So simply pick the conveintent ones.
• Mar 16th 2008, 08:57 AM
Jhevon
Quote:

Originally Posted by ThePerfectHacker
All you want to show $n|m$ given that it works for all $a,b$. So simply pick the conveintent ones.

okie dokie!