Results 1 to 4 of 4

Math Help - Generators of Cyclic Groups

  1. #1
    Newbie
    Joined
    Oct 2012
    From
    District of Columbia
    Posts
    16

    Generators of Cyclic Groups

    Let a have order n, and prove <a> has phi(n) different generators.

    I am not sure how to relate phi(n) and a as a generated group?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    146

    Re: Generators of Cyclic Groups

    Suppose ord(a) = 6. Then <a> = \{1, a, a^2, a^3, a^4, a^5 \}.

    What are the generators of <a>? 1 obviously isn't (<1> = {1}). a obviously is. What about a^2 \ ?

    <a^2> = \{ (a^2)^0 = 1, (a^2)^1 = a^2, (a^2)^2 = a^4, (a^2)^3 = a^6 = 1 \} = \{1, a^2, a^4 \}.

    Thus <a^2> \ \ne \ <a>, \text{ and so } a^2 \text{ doesn't generate } <a>.

    Do the same examination for  a^3, a^4, \text{ and } a^5, and hopefully you'll see/understand the relationship

    between relative primeness of s and n for a^s, and whether a^s is a fellow generator of <a>.
    Last edited by johnsomeone; October 16th 2012 at 06:46 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member jakncoke's Avatar
    Joined
    May 2010
    Posts
    387
    Thanks
    80

    Re: Generators of Cyclic Groups

    I've written the proof below, but if you want a hint, use the fact that if gcd(a, b) = d, then d = na + mb , for integers n, m
    Spoiler:

    If n = 1, then it is easy to see that  \phi(1) = 1 your group has 1 generator. Now take  n > 1 Take A = { x | 0 < x <  n, gcd(x, n) = 1 and x is an integer } so basically  |A| = \phi(n) . Now take  x \in A , if we pulled x = 1, then we can easily see  a^x = a^1 is a generattor, now take  x \in A, x \not = 1 , so, since gcd(m, n) can be written in the form gcd(m, n) = pm + qn , where p, q are integers, we see that  gcd(x, n) = 1 so  1 = xp + nq where p and q are integers, and so  a^1 = a^{xp + nq} = a^{xp} \dot a^{nq} which equals  a^1 = a^{xp}  \dot  e , now since we assumed  1 < x < n, we can say  a^x \not = a^1 so since  (a^{x})^p = a^{xp}  = a  a^x is also a generator of the group (if you take any element in <a> and by raising it to powers, get a as a result after some power, that initial element is a generator of the whole group), thus  a^x where  x \in A are unique elements of the group  <a> , and since a raised to a power from A gives us a unique generator, so  |A|  = \phi(n) is the number of generators for <a>
    Last edited by jakncoke; October 16th 2012 at 11:10 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,392
    Thanks
    759

    Re: Generators of Cyclic Groups

    first of all, this is actually a statement about cyclic groups (<a> is cyclic, with generator a).

    so one might ask: for a given k, what is |ak|?

    if |a| = n, i claim it is: n/(gcd(k,n)).

    let's look at a "nice case" first: suppose k|n, so n = kt, for some positive integer t.

    i claim in this case, the order of ak is t.

    clearly (ak)t = akt = an = e, since |a| = n.

    now suppose (ak)s = e, for some 0 < s < t.

    thus aks = e, where 0 < ks < kt = n, contradicting that |a| = n.

    note this still adheres to our formula above, because when n = kt, gcd(k,n) = gcd(k,kt) = k(gcd(1,t)) = k(1) = k,

    so n/(gcd(k,n)) = n/k = kt/k = t.

    another "nice case": suppose k = 0, then a0 = e, and n/(gcd(0,n)) = n/n = 1 (and indeed the identity always has order 1).

    so now, suppose gcd(k,n) = d, where d < n. thus k = du, and n = dv for some positive integers u and v, with gcd(u,v) = 1.

    so n/(gcd(k,n)) = dv/d = v.

    now (ak)v = (adu)v = aduv = advu = (adv)u = (an)u = eu = e.

    so |ak| divides v (= n/(gcd(k,n)), at the very least.

    suppose (ak)r = e, with 0 < r < v.

    this mean akr = e, so n divides kr. we can write this as: kr = nw (for some integer w).

    so dur = dvw, thus: ur = vw.

    now u divides ur, and gcd(u,v) = 1, so u|w. so w = ux, for some positive integer x (i DO apologize for using so many letters).

    so now from kr = nw, we have:

    dur = dvux, that is:

    r = vx, which can't be possible, since 0 < r < v (vx ≥ v since x is positive).

    so no such r exists, so |ak| = v = n/(gcd(k,n)).

    now, ak is a generator for <a> if ak has order n, so that n/(gcd(k,n)) = n, in which case gcd(k,n) must be 1.

    by definition, φ(n) = {k in Z: 0 < k < n and gcd(k,n) = 1}, so we see we have φ(n) generators for <a> (a0 = an = e is never a generator unless n = 1).

    phew!

    now, all this might seem a bit abstract, so it helps to look at a concrete example:

    let |a| = 12. so <a> = {e,a,a2,....a11}.

    clearly |a1| = |a| = 12, and |a0| = |e| = 1 (and 12/(gcd(0,12)) = 12/12 = 1).

    how about the order of a2? well it's pretty obvious |a2| = 6 (because 2 goes evenly into 12).

    ok, what about a10. let's do this two ways:

    first we compute powers of a10 until we get the identity:

    (a10)2 = a20 = (a12)(a8) = ea8 = a8
    (a10)3 = a30 = (a24)(a6) = (a12)2(a6) = e2a6 = a6
    (a10)4 = a40 = (a36)(a4) = a4 (i hope you understand the short-cut i took here)
    (a10)5 = a50 = (a48)(a2) = a2
    (a10)6 = a60 = (a12)5 = e5 = e

    so |a10| = 6.

    using our formula:

    gcd(10,12) = 2, so |a10| = 12/2 = 6. that's...easier to do, right?

    it should hopefully be clear by now that the generators of <a> are:

    a,a5,a7,a11, so we have 4 of them, and:

    φ(12) = φ(4)φ(3) = φ(22)φ(3) = (2-1)21(3-1)30 = (1)(2)(2)(1) = 4, what do you know!
    Last edited by Deveno; October 16th 2012 at 08:44 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Generators of Groups
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: October 9th 2010, 02:47 AM
  2. Cyclic Group Generators
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: November 21st 2009, 08:59 AM
  3. Cyclic group Generators
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: November 15th 2009, 11:33 AM
  4. Cyclic groups, generators
    Posted in the Algebra Forum
    Replies: 0
    Last Post: November 1st 2009, 06:25 AM
  5. Homomorphism of Groups and their generators
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: December 1st 2008, 01:15 PM

Search Tags


/mathhelpforum @mathhelpforum