Results 1 to 11 of 11

Math Help - Finding a Generator of a Cyclic Group

  1. #1
    Junior Member
    Joined
    Nov 2009
    Posts
    29

    Finding a Generator of a Cyclic Group

    There's something I'm a bit confused about.

    There's a theorem that states that if the order of a group is n, then every k > 1 that satisifes gcd(k,n) = 1 will be a generator of the group.

    So if we take U(9) = {1,2,4,5,7,8}, and the order n = 6 and the generators in this case are supposed to be 5 and 7, since gcd(5,6) = gcd(7,6) = 1.

    <5> = {5,7,8,4,2,1} is okay, but
    <7> = {7,4,1}
    and instead <2> = {2,4,8,7,5,1}, even though gcd(2,6) = 2.

    What's the problem here?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by Koaske View Post
    There's something I'm a bit confused about.

    There's a theorem that states that if the order of a group is n, then every k > 1 that satisifes gcd(k,n) = 1 will be a generator of the group.


    No, what that theorem says is that if g is a generator of that cyclic group of order n, then any other

    generator is of the form g^k\,,\,\,(k,n)=1 , and the other direction is true, too.

    Tonio


    So if we take U(9) = {1,2,4,5,7,8}, and the order n = 6 and the generators in this case are supposed to be 5 and 7, since gcd(5,6) = gcd(7,6) = 1.

    <5> = {5,7,8,4,2,1} is okay, but
    <7> = {7,4,1}
    and instead <2> = {2,4,8,7,5,1}, even though gcd(2,6) = 2.

    What's the problem here?
    .
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2009
    Posts
    29
    Ah, I see. So here it's <2^k> , and k = 1 makes it <2>, and k = 5 makes it <5>.

    This leads me to another problem though... To prove that a very big group is cyclic, U(101) = {1,2,...,99,100}, to be exact, I would first have to find this element g to find all other generators. If this was a smaller group, I would just go through the elements one by one, but here it would require too much work. I suppose there has to be an easier solution, but I don't know what it is...
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Nov 2010
    Posts
    193
    Finding a specific generator in such a large group can be tough.

    But U(\mathbb{Z}_{101}) IS cyclic, as 101 is prime. In fact, it is true that if p is an odd prime, then U(\mathbb{Z}_{p^n}) is cyclic, for any n\geq 1.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Nov 2009
    Posts
    29
    What if we knew that <a> = G for some a? Would there be any easier way to prove that a really generates the whole group, other than going through all a^k ?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Nov 2010
    Posts
    193
    Quote Originally Posted by Koaske View Post
    What if we knew that <a> = G for some a? Would there be any easier way to prove that a really generates the whole group, other than going through all a^k ?
    This question doesn't make any sense.

    "If we knew that a generates G, could we prove that a generates G?"

    Maybe you mean something else?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Nov 2009
    Posts
    29
    What I meant is that if we ASSUME that some element a generates the group. We would still have to prove that assumption though. For example, let's say that we have a hunch that 5 would generate U(9), but we don't want to go through all 5^k to prove it. Would there be another way?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Nov 2010
    Posts
    193
    Well...

    You could do it a little more simply than that, but it would still require some computation.

    The order of the group U(\mathbb{Z}_9) is \varphi (9)=3\cdot 2=6. Thus any element of this group has order 1, 2, 3, or 6.

    If you could show that an element doesn't have order 1, 2, or 3, then it would necessarily have order 6, from which it would follow that it generates the group.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Nov 2009
    Posts
    29
    So in case of U(101), which has 100 = 2 * 5 elements, I would have to find an element that has order of at least 51?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member
    Joined
    Nov 2010
    Posts
    193
    I guess. But you just need an element whose order is none of the proper divisors of 100.

    So you don't need to check every power. Given an element, raise it to the powers 1, 2, 4, 5, 10, 20, 25, 50 (yea, there's work to do there). If none of these give 1, the element must generate the group.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by Koaske View Post
    So in case of U(101), which has 100 = 2 * 5 elements, I would have to find an element that has order of at least 51?


    As 101=1\!\!\pmod 4\,\,and\,\,\phi(101)=100 , an element g\in U(101) is a generator iff

    g^{50}=-1\!\!\pmod{101}\,\,and\,\,g^{25}\neq 1\!\!\pmod{101} , and something similar is

    true for any prime 1 mod 4 (can you give the general claim and its proof?)

    If p=3\!\!\pmod 4 then it is easier: g\in U(p) is a generator iff g^{\frac{p-1}{2}}=-1\!\!\pmod p.

    The general problem of finding a primitive root modulo p (which is what's called a generator

    of U(p)) has no general acceptable easy algorithm to do it.

    Tonio
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Definition of a generator of a cyclic group?
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: October 10th 2011, 08:18 PM
  2. Finding an inifnite group that is not cyclic
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: October 3rd 2011, 08:05 PM
  3. Cyclic Group having only one generator
    Posted in the Advanced Algebra Forum
    Replies: 14
    Last Post: August 11th 2011, 08:33 AM
  4. Finding a generator of a cyclic group
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 16th 2011, 08:08 PM
  5. [SOLVED] Cyclic groups of order greater then 2 have more then one generator
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: November 12th 2010, 08:12 PM

Search Tags


/mathhelpforum @mathhelpforum