Results 1 to 5 of 5

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

  2. #2
    Global Moderator

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

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

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    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 n|m given that it works for all 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 n|m given that it works for all 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: November 23rd 2008, 10:56 AM
  2. [SOLVED] Abstract algebra semigroup question
    Posted in the Advanced Algebra Forum
    Replies: 8
    Last Post: July 9th 2008, 09:33 PM
  3. [SOLVED] Abstract Algebra: Integers Modulo n
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: February 16th 2008, 05:16 PM
  4. [SOLVED] Abstract Algebra: Integers Modulo n 2
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: February 16th 2008, 02:48 PM
  5. Replies: 2
    Last Post: February 16th 2008, 02:30 PM

Search Tags


/mathhelpforum @mathhelpforum