# generators of $\mathbb{Z}_p^*$ are all the elements in $\mathbb{Z}_p^*$?

I know that a finite group with a prime number of elements is cyclic and every element in the group is a generator for the group.

Thinking about $(\mathbb{Z}_p^*, \cdot)$ I thought that the order of $(\mathbb{Z}_p^*, \cdot)$ was $p$, so that every element in the group had to be a generator, but then I pondered the fact that I had to remove the 0 and so $(\mathbb{Z}_p^*, \cdot)$ had to have cardinality $p-1$, and so the theorem shouldn't be applied anymore.

This also explained to me the presence in $(\mathbb{Z}_p^*, \cdot)$ groups (lets say $(\mathbb{Z}_{19}^*,\cdot)$) of particular elements which generate the entire group named "primitive roots" (the group generators if I understood well), and that not every element of the group is a primitive root.

Is all that I wrote correct? Did I make the correct reasoning?

• You are right, $\mathbb{Z}_p^\ast$ has $p-1$ elements, so almost always we cannot deduce immediately that the group is cyclic. Indeed it is cyclic, but this requires proof, and the proof takes more than a little work. Because of this, I find the "this explained" part puzzling, since the existence of primitive roots is not obvious. – André Nicolas Jun 26 '16 at 22:43
• I maybe explained myself bad: I read from another book (written tofether with an intuitive explanation rather then a formal proof) that in $(\mathbb{Z}_p^*, \cdot)$ there were primitive roots that generated the group – Alessio Martorana Jun 26 '16 at 22:54
• It is true that there are primitive roots modulo $p$ for every prime $p$, and also for $p^n$ and $2p^n$ when $p$ is an odd prime. – André Nicolas Jun 26 '16 at 22:58
• Yes, the same sentence of the book =) – Alessio Martorana Jun 26 '16 at 23:00

You are correct. The order of $\mathbb{Z}_p^*$ is $p-1$, so it is not a priori cyclic. However, it turns out to be a nontrivial fact that it is cyclic; and not every element is a generator, because (for instance) 2 divides $p-1$ and so there is an element of order $2$.
Actually finding a generator is very difficult in full generality. As far as I know, it's still open whether $2$ is a generator mod $p$ for infinitely many $p$.
• Finding the generator is easy: most things are generators. Just try things until you find one; either in order or randomly chosen, and you're nearly guaranteed to pick one after a handful of tries. The only time things get difficult is when $p-1$ is difficult to factor, because you need to know the factorization to fully prove if something generates (but not if you just want to be almost completely sure). – user14972 Jun 26 '16 at 22:50
• @AlessioMartorana: Sort of related. But in the discrete logarithm problem, you already know a generator $g$, and given $a$ you want to find $k$ such that $g^k=a$ (in the group). – André Nicolas Jun 26 '16 at 23:01