Results 1 to 5 of 5

Math Help - Cyclic Groups

  1. #1
    Senior Member slevvio's Avatar
    Joined
    Oct 2007
    Posts
    347

    Cyclic Groups

    Hey everyone I was wondering if anybody could help me with this problem.

    Let G = <x> where x has order n and let r denote a positive integer. Prove that  x^r generates G if and only if gcd(r,n) = 1, i.e. r and n are coprime.

    I guess I am trying to prove the statement  |x^r | = n \iff gcd (r,n) = 1 .

    When I try to do this however I just get a strange result... I would appreciate any guidance with this to see where I have gone wrong or what I can do to solve it.

    Proof (<=)

     gcd (r,n)=1 \implies \exists a,b \in \mathbb{Z} such that  ar + bn = 1 \implies ar = 1 - bn

    So  x = x ^{ar+bn} \implies x^r = x^{rar +rbn} = x^{rar}x^{rbn}=x^{rar}(x^n)^{rb} = x^{rar}1^{rb} = x^{rar} since |x| = n.

    Also  x^{ar} = x^{1-bn} = x x^{-bn} = x (x^n)^{-b} = x 1 ^{-b} = x since |x| = n.

    Hence  x^r = x^{rar} = x^r x^{ar} = x ^{ra} x^r =x^r x = x x^r giving  x = 1 which of course means  |x^r| = |x| = n = 1 .

    Is this right, have I done something wrong?? Any help would be appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by slevvio View Post
    Hey everyone I was wondering if anybody could help me with this problem.

    Let G = <x> where x has order n and let r denote a positive integer. Prove that  x^r generates G if and only if gcd(r,n) = 1, i.e. r and n are coprime.

    I guess I am trying to prove the statement  |x^r | = n \iff gcd (r,n) = 1 .

    When I try to do this however I just get a strange result... I would appreciate any guidance with this to see where I have gone wrong or what I can do to solve it.

    Proof (<=)

     gcd (r,n)=1 \implies \exists a,b \in \mathbb{Z} such that  ar + bn = 1 \implies ar = 1 - bn

    So  x = x ^{ar+bn} \implies x^r = x^{rar +rbn} = x^{rar}x^{rbn}=x^{rar}(x^n)^{rb} = x^{rar}1^{rb} = x^{rar} since |x| = n.

    Also  x^{ar} = x^{1-bn} = x x^{-bn} = x (x^n)^{-b} = x 1 ^{-b} = x since |x| = n.

    Hence  x^r = x^{rar} = x^r x^{ar} = x ^{ra} x^r =x^r x = x x^r giving  x = 1 which of course means  |x^r| = |x| = n = 1 .

    Is this right, have I done something wrong?? Any help would be appreciated.

    I think you were on the right path but somewhere you decided to do life harder to yourself: let  b = x^m be any element in G, so:

    b = x^m=x^{m\cdot 1}=x^{mar+mbn}=(x^r)^{ma}\,(x^n)^{mb}=(x^r)^{ma}\c  dot 1\in<x^r>

    And thus any element in G is a power of x^r.

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member slevvio's Avatar
    Joined
    Oct 2007
    Posts
    347
    Thanks very much. Do you have any suggestions for proof in the other direction? I'm not even sure where to begin
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by slevvio View Post
    Thanks very much. Do you have any suggestions for proof in the other direction? I'm not even sure where to begin

    We know that (r,n)=1\Longleftrightarrow rk+ny = 1\,,\,\;k\,,\,y\in \mathbb{Z}. So, if <x^r> = x, then ord(x^r)= n; OTOH:

    \exists k\in \mathbb{Z}\,\,s.t. (x^r)^k=x\Longrightarrow x^{rk-1}=1\Longrightarrow n\mid rk-1\Longrightarrow\,...

    Tonio
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member slevvio's Avatar
    Joined
    Oct 2007
    Posts
    347

    proof

    Let  d = gcd ( r, n )

    Then  d | n and  d | r

    So  (x^r)^{\frac{n}{d}} = (x^n)^{\frac{r}{d} } = 1

    So  |x^r| \le \frac{n}{d}

    But we know  |x^r| = |G|= n by assumption.

    Hence  n \le \frac{n}{d} \implies d \le 1

    But  d \ge 1 by definition of greatest common divisor, hence  d = 1 .

    Ta-dah!

    Thanks for the help everyone !
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Automorphism groups of cyclic groups
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: August 15th 2011, 10:46 AM
  2. cyclic groups
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: February 25th 2010, 08:29 PM
  3. Cyclic groups.
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: May 2nd 2009, 05:33 PM
  4. cyclic groups
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 17th 2008, 05:24 AM
  5. Cyclic Groups
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: March 1st 2008, 08:47 PM

Search Tags


/mathhelpforum @mathhelpforum