We have seen, at least in outline, and in examples, why Zp* is a cyclic group if p is prime: you can count the elements of Zp* with order less than p-1, and not all elements are accounted for. Therefore there must be some of order p-1. That makes Zp* cyclic, because those elements are generators. The proof is indirect, in the sense that it does not identify which elements are generators, it only proves that they exist. In fact, no one has a good way to figure out in advance which elements the generators will be.
But not all Zn* are cyclic groups. You can easily check that Z15* is NOT cyclic, just by checking all possible generators, and verifying that none of them actually IS a generator. First of all, Z15* ={1,2,4,7,8,11,13,14}, just the elements relatively prime to 15. Now look at what each of them generates, starting with 2:
powers of 2: 2, 4, 8, 1 (mod 15)
powers of 4: 4, 1 (mod 15)
powers of 7: 7, 4, 13, 1 (mod 15)
powers of 8: 8, 4, 2, 1 (mod 15)
powers of 11: 11, 1 (mod 15)
powers of 13: 13, 4, 7, 1 (mod 15)
powers of 14: 14, 1 (mod 15)
There is nothing of order 8.
The best way to understand multiplication mod 15 is to realize that there is a homomorphism
and also a homomorphism
just given by reduction mod 5 in the first case and reduction mod 3 in the second case. [In class we recalled what this means and did some examples: 4*13 = 52 = 7 (mod 15). If you reduce mod 5 you get 4*3=12=2 mod 5. And sure enough, 7 (mod 15) reduces to 2 (mod 5). This is the homomorphism property: you can multiply in Z15* and reduce, or reduce, then multiply in Z5*. It comes out the same either way. Similarly if you reduce 4*13 mod 3, it is 1*1=1 (mod 3). And this is also what you get when you reduce 7 (mod 15) to 1 (mod 3). We checked that if you try reducing to other groups, like Z7*, with no particular relation to Z15*, the reduction is NOT a homomorphism: reducing mod 7 gives 4*6=3 (mod 7), and this is not what you get if you take 7 (mod 15) and reduce to 0 (mod7). Alyssa W. raised the very interesting question of reducing mod 10 or mod 12, numbers which share factors with 15. You can easily try it: reducing 4*13 mod 10 gives 4*3=2 (mod 10) not the same as 7 (mod 15) which reduces to 7 (mod 10). But note that we can still reduce mod 5 after reducing mod 10! That property has not been lost, although we cannot any longer reduce mod 3: 2 (mod 10) reduces to 2 (mod 3), not 1 (mod 3). Similarly, reducing mod 12, 4*13=4*1=4 (mod 12) which is not 7 (mod 12), although we can still reduce mod 3: they are both 1 (mod 3). The agreement mod 5 has been destroyed, though, by the reduction mod 12.]
Here is how the elements of Z15* reduce: we will say a-->(b,c) if a in Z15* is b mod 5 and c mod 3:
1 --> (1,1)
2 --> (2,2)
4 --> (4,1)
7 --> (2,1)
8 --> (3,2)
11 --> (1,2)
13 --> (3,1)
14 --> (4,2)
As you can see, from the reduction mod 5 and 3 together, you can uniquely figure out what the element originally was. For example, 3 mod 5 and 1 mod 3 (which we are calling (3,1)) must be 13 in Z15*. This also gives a way to multiply in Z15* in which you multiply mod 5 in the first place and mod 3 in the second place: 13*11 = (3,1)*(1,2)=(3*1,1*2)=(3,2)=8 (mod 15). You just multiply separately in Z5* and Z3*, because of the homomorphism!
Since 2 is a generator of Z5*, the element of Z15* which reduces to (2,1) (it happens to be 7) is a bit like a generator in Z15* (of course it only generates 4 elements, not all 8). And since 2 is a generator of Z3*, the element of Z15* which reduces to (1,2) (it happens to be 11) is also a bit like a generator in Z15* (where it generates two elements). 7 generates a copy of Z5* in Z15* and 11 generates a copy of Z3* in Z15*. Together they generate everything in Z15*. That is, if we form (7^j)*(11^k) with different exponents j=0,1,2,3 and k=0,1, we get all of Z15*, as the table shows. The rows are labeled by the exponent j, and the columns by the exponent k:
| k=0 | k=1 | |
| j=0 | 1 | 11 |
| j=1 | 7 | 2 |
| j=2 | 4 | 14 |
| j=3 | 13 | 8 |
You can see in this table why phi(15)=phi(5)*phi(3)! The number of rows is just phi(5)=4, because the first column is a copy of Z5*, and the number of columns is just phi(3)=2 because the first row is just a copy of Z3*. Together they make a rectangle with phi(15)=8 entries.
This gives a different way to represent elements of Z15*, namely by their exponents (7^j)*(11^k)-->(j,k). [This pair of exponents (j,k) should not be confused with the (b,c) above! It is a different notation, another way of representing elements in Z15*.] In this way of looking at it, multiplication mod 15 is just addition of exponents (mod 4 in the j-place and mod 2 in the k-place). So to multiply 11*13 we could look at the table and say it is (0,1)+(3,0)=(3,1), the exponents for 8 (find the entry with j=3, k=1), i.e., 11*13=8 (mod 15).
Analyze Z21* in this way, using the homomorphisms onto Z7* and Z3* (namely reduction mod 7 and reduction mod 3). In particular, find an element which reduces to a generator of Z7* and reduces to 1 in Z3* (this will be an element of Z21* which plays the role which 7 played in the example above: I will call it a for the moment, but you should find what number it is). Also find an element which goes onto a generator of Z3* and onto 1 in Z7* (in analogy to 11 in the example above: I will call it b for the moment, but you should find it). Show that every element in Z21* is of the form (a^j)*(b^k), using your a and your b and appropriate exponents j and k as in the table just above. Make a table like that one, showing what element you get for each pair of exponents. Check that your table has phi(7) rows, and phi(3) columns!
This result is sometimes stated symbolically as Z21* = Z7* x Z3*. The group Z21* is a product group: it is "built" out of smaller groups.