1. ## Subgroup, generators, order

hi
can someone help me with this i'm really confused

1. Find all subgroup of (Z_12,+)
2. Find all generators of (Z_11\{0},*)
3. Find all generators of (Z_20,+) and subgroup of order 4 and 10

thanks

2. ## Re: Subgroup, generators, order

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

Z12 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 Z12 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:

22 = 4
23 = 8
24 = 16 = 5 (mod 11)
25 = (5)(2) = 10 (mod 11)
26 = (10)(2) = 20 = 9 (mod 11)
27 = (9)(2) = 18 = 7 (mod 11)
28 = (7)(2) = 14 = 3 (mod 11)
29 = (3)(2) = 6 (mod 11)
210 = (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 Z20 the same way i did Z12. to find a subgroup of order 4, you'll want to pick some integer k with gcd(k,20) = 5. why?

3. ## Re: Subgroup, generators, order

Originally Posted by Deveno
you can do Z20 the same way i did Z12. 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

4. ## Re: Subgroup, generators, order

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:

22 = 4
23 = 8
24 = 16 = 5 (mod 11)
25 = (5)(2) = 10 (mod 11)
26 = (10)(2) = 20 = 9 (mod 11)
27 = (9)(2) = 18 = 7 (mod 11)
28 = (7)(2) = 14 = 3 (mod 11)
29 = (3)(2) = 6 (mod 11)
210 = (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

5. ## Re: Subgroup, generators, order

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

6. ## Re: Subgroup, generators, order

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 = 22, and 2 divides 10, so

1 = 210 = (22)5 = 45 (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 20 = 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 Z10, which is also another cyclic group of order 10.

now, which elements of Z10 generate Z10? 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 Z10.

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 Z10:

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

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

95 = (92)2(9) = (81)2(9)

but 81 = 4 mod 11, so 95 = (4)2(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 95 = 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 2k, where k is a generator of Z10).

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 Zp-1, to find the other generators of U(p).

thanks a lot

[Solved]

,
,

,

,

,

# how to find generators for z in algebra

Click on a term to search for related topics.