Results 1 to 3 of 3

Thread: 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 $\displaystyle <[a]> = <[b]>$ in $\displaystyle \mathbb{Z}_n$ iff $\displaystyle gcd(a,n) = gcd(b,n).$ (See problem 15.26).



    Things that might come in handy:


    Here is problem 15.26:

    Prove that if $\displaystyle gcd(a,n) = d$, then $\displaystyle <[a]> = <[d]>$ in $\displaystyle \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 $\displaystyle T_1$ and $\displaystyle T_2$ be subsets of a group $\displaystyle G$. Then

    $\displaystyle <T_1> = <T_2>$ iff $\displaystyle T_1 \subseteq <T_2>$ and $\displaystyle 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 $\displaystyle <[a]> = <[b]>$ part, but i know that, given that that's true, i want to show that $\displaystyle ak + nl = bp + nr$, for $\displaystyle 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 $\displaystyle <[a]> = <[b]>$ in $\displaystyle \mathbb{Z}_n$ iff $\displaystyle gcd(a,n) = gcd(b,n).$ (See problem 15.26).
    Given positive integer $\displaystyle a$:
    $\displaystyle \left< [a] \right> = \left< [d] \right> $ where $\displaystyle d=\gcd(a,n)$.
    Now since $\displaystyle \gcd(b,n) = d$ it means $\displaystyle \left< [b] \right> = \left< [d] \right>$.
    Thus, $\displaystyle \left< [a] \right> = \left< [b] \right>$.

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

    So that means we need to prove $\displaystyle \left< [a] \right> = \left< [d] \right>$ when $\displaystyle \gcd(a,n) = d$. Note $\displaystyle [a]\in \left< [d] \right> $ because $\displaystyle d|a$, this means $\displaystyle \left< [a] \right> \subseteq \left< [d] \right>$. Note there exist $\displaystyle x,y\in \mathbb{Z}$ so that $\displaystyle ax+ny=d$. Thus, $\displaystyle [d] = [ax+ny] = [ax]$, so $\displaystyle [d] \in \left< [a] \right>$ which means $\displaystyle \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 $\displaystyle <[a]> = <[b]> \implies gcd(a,n) = gcd(b,n)$

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

    Similarly, I can get $\displaystyle b = ma + rn$ for $\displaystyle 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: Sep 22nd 2008, 04:53 PM
  2. Abstract Algebra: Cyclic Groups and GCD
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: Mar 5th 2008, 04:46 PM
  3. Abstract Algebra: Groups
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Mar 5th 2008, 03:13 AM
  4. Abstract Algebra: cyclic groups
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: Feb 11th 2008, 07:06 PM
  5. Abstract Algebra: Groups
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: Feb 11th 2008, 09:39 AM

Search Tags


/mathhelpforum @mathhelpforum