# [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 $\displaystyle m,n$ is $\displaystyle \beta : \mathbb{Z}_m \to \mathbb{Z}_n$ by $\displaystyle \beta ([a]_m) = [a]_n$ well defined?

Solution:

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

Proof:

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

($\displaystyle \Rightarrow$): For the converse, we use the contrapositive. Assume $\displaystyle n \nmid m$. Then by the Division Algorithm, $\displaystyle n = qm + r$, $\displaystyle 0 < r < m$, for unique $\displaystyle q,r \in \mathbb{Z}$. So $\displaystyle m = \frac {n - r}q$ (which is an integer by hypothesis). Thus, $\displaystyle a \equiv b~(\mbox {mod }m) \Longleftrightarrow b - a = mk$, for some $\displaystyle k \in \mathbb{Z}$, which implies $\displaystyle b - a = \left( \frac {n - r}q \right)k = \left( \frac nq \right)k - \left( \frac rq \right)k \ne nl$ for any $\displaystyle l \in \mathbb{Z}$. Thus, $\displaystyle n \nmid (b - a)$, which means $\displaystyle 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 $\displaystyle m,n$ is $\displaystyle \beta : \mathbb{Z}_m \to \mathbb{Z}_n$ by $\displaystyle \beta ([a]_m) = [a]_n$ well defined?

You need to prove that if $\displaystyle n|m$ then the homomorphism is well-defined, i.e. if $\displaystyle a\equiv b(\bmod m)\implies a\equiv b(\bmod n)$ (for all $\displaystyle a,b$). And conversely, i.e. if $\displaystyle a\equiv b(\bmod m)\implies a\equiv b(\bmod n)$ (for all $\displaystyle a,b$) then $\displaystyle n|m$. You proved the first part correctly. We can do it easier. If $\displaystyle a\equiv b(\bmod m)$ then $\displaystyle m|(a-b)$ since $\displaystyle n|m$ it means $\displaystyle n|(a-b)\implies a\equiv b(\bmod n)$ (divisibility is transitive). For the second part you overkilled it. Assume that $\displaystyle a\equiv b(\bmod m)\implies a\equiv b(\bmod n)$ (for all $\displaystyle a,b$), choose $\displaystyle a=m,b=0$ then $\displaystyle a\equiv b(\bmod m)$ and so $\displaystyle 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 $\displaystyle n|m$. And then you should that if $\displaystyle 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 $\displaystyle a\equiv b(\bmod m)\implies a\equiv b(\bmod n)$ (for all $\displaystyle a,b$), choose $\displaystyle a=m,b=0$ then $\displaystyle a\equiv b(\bmod m)$ and so $\displaystyle 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 $\displaystyle n|m$ given that it works for all $\displaystyle 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 $\displaystyle n|m$ given that it works for all $\displaystyle a,b$. So simply pick the conveintent ones.

okie dokie!