Thread: Subgroup, generators, order

you should be posting these questions in the advanced algebra section.

Z₁₂ is cyclic. All of its subgroups will also be cyclic. Also, any subgroup of order m will be unique.

in fact <k> will have order 12/gcd(k,12).

this tells us that <1>, <5>, <7>, <11> are all of order 12, that is are Z₁₂ itself.

<2> = <10>, the same subgroup of order 6, {0,2,4,6,8,10}

<3> = <9>, the same subgroup of order 4, {0,3,6,9}

<4> = <8>, the same subgroup of order 3, {0,4,8}

<6>, a subgroup of order 2, {0,6}

<0>, the trivial subgroup {0}.

U(11) (the group of units mod 11, which consists of all the non-zero elements of Z11, under multiplication mod 11), is a group of order 10. as it turns out, this group is also cyclic, although that is not obvious.

let's see if 2 is a generator:

2² = 4
2³ = 8
2⁴ = 16 = 5 (mod 11)
2⁵ = (5)(2) = 10 (mod 11)
2⁶ = (10)(2) = 20 = 9 (mod 11)
2⁷ = (9)(2) = 18 = 7 (mod 11)
2⁸ = (7)(2) = 14 = 3 (mod 11)
2⁹ = (3)(2) = 6 (mod 11)
2¹⁰ = (6)(2) = 12 = 1 (mod 11), and 1 is the identity of U(11), so we see the order of 2 is 10, so 2 is indeed a generator.

now...why does this tell us that 4 and 10 are NOT generators?

you go ahead and check 3, and then 5.

you can do Z₂₀ the same way i did Z₁₂. to find a subgroup of order 4, you'll want to pick some integer k with gcd(k,20) = 5. why?

Originally Posted by Deveno

you can do Z₂₀ the same way i did Z₁₂. to find a subgroup of order 4, you'll want to pick some integer k with gcd(k,20) = 5. why?

because 20 / 4 = 5 and <5> = {0, 5, 10, 15} ...... 4 elements

Originally Posted by Deveno

U(11) (the group of units mod 11, which consists of all the non-zero elements of Z11, under multiplication mod 11), is a group of order 10. as it turns out, this group is also cyclic, although that is not obvious.

let's see if 2 is a generator:

2² = 4
2³ = 8
2⁴ = 16 = 5 (mod 11)
2⁵ = (5)(2) = 10 (mod 11)
2⁶ = (10)(2) = 20 = 9 (mod 11)
2⁷ = (9)(2) = 18 = 7 (mod 11)
2⁸ = (7)(2) = 14 = 3 (mod 11)
2⁹ = (3)(2) = 6 (mod 11)
2¹⁰ = (6)(2) = 12 = 1 (mod 11), and 1 is the identity of U(11), so we see the order of 2 is 10, so 2 is indeed a generator.

now...why does this tell us that 4 and 10 are NOT generators?

you go ahead and check 3, and then 5.

i don't have idea why
i've checked 3 and 5, they are not generators
but there must be some trick, shortcut
what if i have Z_50?? i can't check every element

p.s. how can i find left and right cosets of subgroup <2> ={0,2,4,6,8,10} of Z_12 ???

to your first question- no, because 20/5 = 4 (not the other way around).

to your 2nd question- 4 cannot be a generator (an element of order 10), because 4 = 2², and 2 divides 10, so

1 = 2¹⁰ = (2²)⁵ = 4⁵ (mod 11), so 4 has order at most 5.

see if you can figure out why 10 cannot have order 10.

indeed, it is true that 3 and 5 are NOT generators of U(11), they both have order 5. so far, we've eliminated:

1,3,4,5 and 10 as generators, and we have that 2 is a generator. that leaves 6,7,8 and 9 to check.

is there a short-cut? well, yes, if we find ONE generator (which we have). let's list the powers of 2, in order (starting with 2⁰ = 1):

1, 2, 4, 8, 5, 10, 9, 7, 3, 6

0, 1, 2, 3, 4, 5, 6, 7, 8, 9

below them, i have listed the elements of Z¹⁰, which is also another cyclic group of order 10.

now, which elements of Z₁₀ generate Z₁₀? the k with 10/gcd(k,10) = 10, which means that gcd(k,10) = 1.

which elements are these? 1,3,7, and 9. so the generators of U(11) ought to correspond to these generators of Z₁₀.

2<-->1, we already found this one.
8<-->3 look! a new generator!
7<-->7 another generator!
6<-->9 this should be all of them.

so, our generators are {2,6,7,8}. note that 9 corresponds to 6, which is an element of order 5 in Z₁₀:

5(6) = 30 = 3(10) = 3(0) = 0 (mod 10).

therefore, we should expect 9⁵ = 1 (mod 11).

9⁵ = (9²)²(9) = (81)²(9)

but 81 = 4 mod 11, so 9⁵ = (4)²(9) = (16)(9) = (5)(9) (mod 11) (since 16 = 5 + 11)

= 45 (mod 11) = 1 (mod 11) (since 45 = 1 + 44 = 1 + 4(11)).

so 9⁵ = 1 (mod 11), as we should have known.

note that we had to find the generator 2 first, to know "which" powers of 2 would be the generators (the generators being 2^k, where k is a generator of Z₁₀).

in general, it is hard to say in advance which elements of U(p) will be generators. but on average, around 40% will be generators (the exact number depends on "how factorable" p-1 is), so you usually find one in 2 or 3 tries. once you have found a generator, you can use knowing the generators of Z_p-1, to find the other generators of U(p).

thanks a lot

[Solved]