Results 1 to 5 of 5

Thread: [SOLVED] Abstract Algebra: Homomorphisms

  1. #1
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3

    [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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by Jhevon View Post
    (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$.

    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by ThePerfectHacker View Post
    ... 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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by Jhevon View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by ThePerfectHacker View Post
    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!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Abstract Algebra Problem
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Nov 23rd 2008, 10:56 AM
  2. [SOLVED] Abstract algebra semigroup question
    Posted in the Advanced Algebra Forum
    Replies: 8
    Last Post: Jul 9th 2008, 09:33 PM
  3. [SOLVED] Abstract Algebra: Integers Modulo n
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: Feb 16th 2008, 05:16 PM
  4. [SOLVED] Abstract Algebra: Integers Modulo n 2
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: Feb 16th 2008, 02:48 PM
  5. Replies: 2
    Last Post: Feb 16th 2008, 02:30 PM

Search Tags


/mathhelpforum @mathhelpforum