Generators of
Since they all have a gcd of 1.
all have gcd of 2
all have gcd of 3
have a gcd of 6
Problem: Find all subgroups of , draw the subgroup diagram.
Corollary:
If is a generator of a finite cyclic group of order , then the other generators G are the elements of the form , where r is relatively prime to n.
I'm following this problem in the book. It says that by corollary 6.16 (what I wrote above), the elements 1, 5, 7, 11, and 17 are all generators of .
These elements (1, 5, 7 ...) are from using the generator <1>, correct? And therefore (1, 5, 7...) will not only be subgroups of but will actually equal , correct?
Then the example starts with <2>, which is the next generator after <1>, which forms the subgroup {0, 2, 4, 6, 8, 10, 12, 14, 16}. It then goes on to say that <2> "generates elements of the form , where is relatively prime to 9, namely, h=1,2,4,7,8 so h2=2,4,8,10,14,16. What exact is the purpose of that bolded statement? Is it just used to save time, since we can now say by that corollary, is a generator because 4 is relatively prime to n=9?
It continues, saying that the element 6 of <2> generates {0, 6, 12}, and 12 is also a generator of this group. Why exactly are we looking at <2>? Are we methodically going through each generator and looking at all of it's elements that we haven't used as generators yet, to use as generators?
Continuing, it says we have found all the subgroups generated by 0,1,2,4,5,6,7,8,10,11,12,13,14,16,17. This just leaves 3, 9 and 15 to consider.
.
Now I'm assuming since we've already seen 0, 6 and 12, we are only concerned with 3, 9, and 15. It says that 15 can also generate this group, which is easy to see. So we ignore it in just the diagram? Or just ignore it altogether?
9 is the last generator left unexplored, so <9>={0,9}.
The subgroup then looks like this:
<1> to <2>, <3>
<2> to <1>, <6>
<3> to <6>, <9>, <1>
<6> to <2>, <3>, <0>
<9> to <3>, <6>, <0>
<0> to <6>, <9>
What exactly are these nodes? Are they the generators that we didn't ignore in the process of finding all of the subgroups? Why aren't we using any of the generators (besides 1) found in the first part of the problem? What exactly was the point of finding those generators in the first part of the problem?
Any help is appreciated.
the subgroups of Zn in general are in one-to-one correspondence with the divisors of n.
in fact, if (k,n) = d, a^k has order d. Zn has exactly one subgroup of order d, for each divsior d.
if you haven't covered lagrange's theorem yet, you won't be able to prove this (at least, not easily).
so let's look at Z18 in particular. the divisors of Z18 are 1,2,3,6,9 and 18.
clearly, <1> = Z18. does Z18 have any other generators? by the corollary from your book, these generators should be:
{1,5,7,11,13 and 17}. let's verify this to our satisfaction. first of all, it should be the case that <x> = <18-x>.
clearly if x is of order m, then m(18-x) = m18 - mx (mod 18) = 0 - 0 = 0 (mod 18).
now suppose d(18-x) = 0 (mod 18) for some 0 ≤ d < m. this means -dx = 0 (mod 18), so dx = -0 = 0 (mod 18).
since the order of x is m, m is the smalleset positive integer such that mx = 0 (mod 18), so we must have d = 0, which
shows that 18-x has the same order as x. this cuts our work in half, we know immediately that <17> = <1>.
let's look explicitly at <5>:
{5,10,15,2,7,12,17,4,9,14,1,6,11,16,3,8,13,0} are the "powers" m5, as you can see we have 18, so <5> = <1>.
by our argument above, <5> = <13> (if you actually listed <13>, you would get: {13,8,3,16,11,6,1,14,9,4,17,12,7,2,15,10,5,0},
note that except for 0, this is <5> listed in reverse order).
again, we can list <7> explicitly: <7> = {7,14,3,10,17,6,13,2,9,16,5,12,1,8,15,4,11,0}, which has 18 elements, so is all of Z18.
again, we know that <7> = <11>.
so now, we look at the smallest number that isn't a generator, which is 2.
<2> ={2,4,6,8,10,12,14,16,0} which has 18/2 = 9 elements.
it is obvious that <2> =<16> (count down by 2's instead of counting up).
what isn't obvious is that <2> = <8>. but, seeing is believing:
<8> = {8,16,6,14,4,12,2,10,0} these are the same 9 elements of <2>.
so the formula for the order of <k> must be more complicated than 18/k, in fact it is 18/(k,18).
the gcd of (8,18) is 2, so the order of <8> = 18/2 = 9. again, we know that <8> = <10>.
note that <2> is a cyclic group of order 9. applying the corrollary to it, we should have that the generators of <2> are:
{2,4,8,10,14,16}. it is instructive to see for yourself that this is true (in this case, all that is left to verify is <4>).
the next step is to investigate 3. we suspect that the order of <3> should be 18/3 = 6, since (3,18) = 3.
<3> = {3,6,9,12,15,0}, which indeed has 6 elements. convince yourself that only 15 is also a generator of <3>.
so...where are we? we've found <1>,<2>,<3>,<4>,<5>,<7>,<8>,<10>,<11>,<13>,<14>,<1 5>,<16>,<17>.
what does that leave? 6, 9, 12 and 0. of course <0> = {0}, it's not very interesting (but important!).
clearly, <6> = <12>, and <6> = {6,12,0}, which has 18/(6,18) = 18/6 = 3 elements.
finally, <9> = {9,0}, which has 18/(9,18) = 18/9 = 2 elements.
the point of this (somewhat tedious) exercise is to burn forever upon your brain the notion that there is a deep connection between
"divisiblity" and "subgroup of cyclic group". when you DO study lagrange's theorem, you have a motivating example (lagrange's theorem
generalizes this to arbitrary finite groups as much as possible. since arbitrary groups are not cyclic, we lose a bit of information,
we cannot necessarily produce a generator for a subgroup, and we cannot always say how many subgroups of a given order a group has.
nevertheless the order of a subgroup, and the order of the parent group are still connected...by divisibility).
note that for each divisor d of 18, we were only able to produce a single subgroup of order 18/d:
Z18, order 18, generated by 1,5,7,11,13,or 17 <-- all of these numbers have (k,18) = 1
<2>, order 9, generated by 2,4,8,10,14,or 16 <-- all of these number have (k,18) = 2
<3>, order 6, generated by 3 or 15 <-- all of these numbers have (k,18) = 3
<6>, order 3, generated by 6 or 12 <-- all of these numbers have (k,18) = 6
<9>, order 2, generated by 9 <-- (9,18) = 9
<0>, order 1, generated by 0 <-- (0,18) = 18.
dwsmith - Thanks for editing your post, it is now much more clear!
Denevo - That is a beautiful reply! Words cannot express my gratitude for your detailed and clear response - I now have a much improved understanding of the question and the answer.