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
Please explain
thanks
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?
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).