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.
Z_{12} 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_{12} 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^{2} = 4
2^{3} = 8
2^{4} = 16 = 5 (mod 11)
2^{5} = (5)(2) = 10 (mod 11)
2^{6} = (10)(2) = 20 = 9 (mod 11)
2^{7} = (9)(2) = 18 = 7 (mod 11)
2^{8} = (7)(2) = 14 = 3 (mod 11)
2^{9} = (3)(2) = 6 (mod 11)
2^{10} = (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_{20} the same way i did Z_{12}. 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 = 2^{2}, and 2 divides 10, so
1 = 2^{10} = (2^{2})^{5} = 4^{5} (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^{0} = 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^{10}, which is also another cyclic group of order 10.
now, which elements of Z_{10} generate Z_{10}? 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_{10}.
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_{10}:
5(6) = 30 = 3(10) = 3(0) = 0 (mod 10).
therefore, we should expect 9^{5} = 1 (mod 11).
9^{5} = (9^{2})^{2}(9) = (81)^{2}(9)
but 81 = 4 mod 11, so 9^{5} = (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 9^{5} = 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_{10}).
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).