[SOLVED] Abstract Algebra: Homomorphisms

Printable View

March 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
March 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.
March 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?
March 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.
March 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!