Results 1 to 3 of 3

Math Help - Abstract Algebra: Cyclic Groups and GCD 2

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

    Abstract Algebra: Cyclic Groups and GCD 2

    Hi all,

    My brain is fried by now, I'm not sure where to go with this homework problem.


    Problem:

    Prove that <[a]> = <[b]> in \mathbb{Z}_n iff gcd(a,n) = gcd(b,n). (See problem 15.26).



    Things that might come in handy:


    Here is problem 15.26:

    Prove that if gcd(a,n) = d, then <[a]> = <[d]> in \mathbb{Z}_n


    For notation, see here


    There's a theorem, I don't know how useful it would be in this case.

    Theorem: Let T_1 and T_2 be subsets of a group G. Then

    <T_1> = <T_2> iff T_1 \subseteq <T_2> and T_2 \subseteq <T_1>


    I will supply any other useful information upon request.


    What I tried:

    Like i said, my brain is fried.

    I'm not sure how to apply the <[a]> = <[b]> part, but i know that, given that that's true, i want to show that ak + nl = bp + nr, for k,l,p,r \in \mathbb{Z}

    Also lost for the converse.


    Thanks guys and gals
    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

    Prove that <[a]> = <[b]> in \mathbb{Z}_n iff gcd(a,n) = gcd(b,n). (See problem 15.26).
    Given positive integer a:
    \left< [a] \right> = \left< [d] \right> where d=\gcd(a,n).
    Now since \gcd(b,n) = d it means \left< [b] \right> = \left< [d] \right>.
    Thus, \left< [a] \right> = \left< [b] \right>.

    So that means we need to prove \left< [a] \right> = \left< [d] \right> when \gcd(a,n) = d. Note [a]\in \left< [d] \right> because d|a, this means \left< [a] \right> \subseteq \left< [d] \right>. Note there exist x,y\in \mathbb{Z} so that ax+ny=d. Thus, [d] = [ax+ny] = [ax], so [d] \in \left< [a] \right> which means \left< [d] \right> = \left< [a] \right>.
    Last edited by ThePerfectHacker; March 5th 2008 at 07:29 AM.
    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
    Given positive integer a:
    \left< [a] \right> = \left< [d] \right> where d=\gcd(a,n).
    Now since \gcd(b,n) = d it means \left< [b] \right> = \left< [d] \right>.
    Thus, \left< [a] \right> = \left< [b] \right>.

    So that means we need to prove \left< [a] \right> = \left< [d] \right> when \gcd(a,n) = d. Note [a]\in \left< [d] \right> because d|a, this means \left< [a] \right> \subseteq \left< [d] \right>. Note there exist x,y\in \mathbb{Z} so that ax+ny=d. Thus, [d] = [ax+ny] = [ax], so [d] \in \left< [a] \right> which means \left< [d] \right> = \left< [a] \right>.
    Using problem 26, it was actually easy proving this direction. it was really the other direction i was interested in.

    i want to show that <[a]> = <[b]> \implies gcd(a,n) = gcd(b,n)

    okay, so if i assume <[a]> = <[b]>, then [a] = [kb] for some k \in \mathbb{Z}. So, a \equiv kb ~(\mbox{mod }n) \Longleftrightarrow a - kb = ln for some l \in \mathbb{Z}. Thus, a = kb + ln

    Similarly, I can get b = ma + rn for m,r \in \mathbb{Z}.

    What now?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. abstract algebra: cyclic!
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: September 22nd 2008, 05:53 PM
  2. Abstract Algebra: Cyclic Groups and GCD
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: March 5th 2008, 05:46 PM
  3. Abstract Algebra: Groups
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: March 5th 2008, 04:13 AM
  4. Abstract Algebra: cyclic groups
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: February 11th 2008, 08:06 PM
  5. Abstract Algebra: Groups
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: February 11th 2008, 10:39 AM

Search Tags


/mathhelpforum @mathhelpforum