## Class 16: Zp* is cyclic, if p is prime

The problem due today points out how much simpler multiplication in Z13* looks when you represent each element as a generator to some exponent: multiplication (mod 13) turns into addition (mod 12) of the exponents. Specifically, one could see that the elements of Z13*, in terms of the generator 2, were just 2^j where the exponents j can be read from the following table:

 exponent 1 2 3 4 5 6 7 8 9 10 11 12 element of Z13* 2 4 8 3 6 12 11 9 5 10 7 1 ORDER 12 6 4 3 12 2 12 3 4 6 12 1

The third row of the table gives the order of each element in Z13* -- note that the order of an element always divides 12, the total number of elements in Z13*. The representation by exponents makes it easy to see what the order will be. The element 8 = 2^3, for example, has order 4, because (2^3)(2^3)(2^3)(2^3)=2^12=1. The element 9 = 2^8 has order 3 because (2^8)(2^8)(2^8)=2^24=(2^12)(2^12)=1*1=1. In general, if an element has exponent j, then the order will be 12/gcd(12,j).

That Z13* is cyclic is just another way of saying that there is an element of order 12: any such element is represented by an exponent j such that gcd(12,j)=1, i.e., the exponent j is relatively prime to 12. Of course this is a little bit of circular reasoning! The only reason we can represent elements with exponents is that we already have noticed that 2 is a generator. But at least we are able to spot the other generators this way: 6, 11, and 7, the other elements with order 12. If we know one generator, we can easily find the other ones. But in general we don't know if a multiplicative group Zp* is cyclic, i.e., we don't know if a generator even exists.

A curious proof that Zp* is cyclic if p is prime starts with Fermat's Little Theorem (FLT), and "turns it around." Recall that FLT says that if p is prime and a is an element of Zp*, then We can regard this as a polynomial equation for which we already know all the roots! That is, in the case of Z13*, we can say that the polynomial x^12 - 1 takes the value zero (mod 13) for every x in Z13*, i.e., x=1,2,3,4,...,12. This polynomial of degree 12 has 12 roots which we happen to know already. Since 12 is already a fairly large degree, let us see how it works for a smaller prime, say p=3: Then x^2-1 should have the elements of Z3* as roots. These elements are, of course {1,2}. And this is true:

x^2-1=(x-1)(x+1),

a neat factorization of polynomials you may remember from high school. If you put in x=1, then the first factor is zero, and if you put in x=2, the second factor is zero (mod 3).

Try it for p=5. The elements of Z5* are all roots of

x^4-1 = (x^2-1)(x^2+1) = (x-1)(x+1)(x^2+1)

(mod 5). If you try it, you find x=1 and x=4 are roots (mod 5) of the factors (x-1) and (x+1). The other elements, x=2 and x=3, are roots of x^2+1, i.e., they are square roots of -1 (mod 5). They must therefore have order 4, which makes them generators of Z5*, and proves Z5* is cyclic in a kind of indirect way. This idea generalizes to show that Zp* is cyclic for any prime p.

Let us see how it works in case p=13, the case we started with. Every element of Z13* is a root of x^12-1, by FLT, as we have noted already. But some of those elements have order less than 12. For example, elements with order 1 are roots of x-1=0, an equation with exactly one solution, x=1. Elements of order 2 are roots of x^2-1=0=(x-1)(x+1). There are two roots, but one of them is x=1, the one we found first, with order 1, so the only new root is x=-1=12 (mod 13). This element actually does have order 2. Elements with order 3 are roots of x^3-1=0=(x-1)(x^2+x+1). One solution is x=1, the one we found first, but the roots of x^2+x+1=0 are two new elements, which actually do have order 3. (It is not necessary for the argument actually to find them, but it is easy to see that they are x=3 and x=9. What is crucial to the argument is that the quadratic polynomial x^2+x+1 have exactly two roots, a fact familiar in ordinary high school algebra, but rather subtle here in Z13 -- although still true.) Elements with order 4 are roots of x^4-1=(x-1)(x+1)(x^2+1)=0. Two solutions are x=1 and x=-1, elements which have order 1 and 2 respectively, but the roots of x^2+1=0 in Z13 are two new elements which actually do have order 4. (They happen to be 5 and 8, although it is unnecessary to find them.) Finally, elements with order 6 are roots of x^6-1=0=(x^3-1)(x^3+1)=(x^3-1)(x+1)(x^2-x+1). Four of the solutions have already been noted, but the roots of x^2-x+1=0 are new, and have order 6. (They happen to be 10 and 4.) We have now counted all the elements of Z13* with order 6 or less, and there are exactly 8 of them. That leaves 4 elements unaccounted for, and these must therefore have order 12. Therefore Z13* has a generator (an element of order 12) and is cyclic.

### Assignment

Try this kind of argument on Z7*. Since phi(7)=6, and the order of every element must divide 6, the possible orders are 1, 2, 3, and 6. Find all the elements with order 3 or less by solving the polynomial equations x-1=0, x^2-1=0, and x^3-1=0 in Z7. Factor the polynomials to show how the same element may appear as a solution to more than one equation. Find the solutions explicitly, and note that each equation of degree d has exactly d distinct solutions (here d =1, 2, and 3). Finally point out that the elements which appear as solutions are not all the elements of Z7*, and hence that there must be elements of order 6. Each such element is a generator, proving (indirectly!) that Z7* is cyclic.