# Generators of Finite Cyclic Groups

Given a cyclic multiplicative group such as $\mathbb{Z}^*_p$ where $p$ is prime, how do you determine an element in that group that generates the entire group?

-
Those generators are called primitive roots. –  Tomas Aug 2 '13 at 22:57
$\mathbb Z_p$ is not a multiplicative group. –  Ittay Weiss Aug 2 '13 at 22:58

If you mean the additive group $\mathbb{Z}_n$, then you are looking for an element with order $n$. Try different values of $n$ and see what elements generate $\mathbb{Z}_n$. See if you can show that an element $a\in\mathbb{Z}_n$ has order $n$ if and only if $(a,n)=1$.

In general, you can show that an element $a$ has order $\frac{n}{(a,n)}$.

Now, if you mean the multiplicative group $\mathbb{Z}_n^{\times}$, then this is only cyclic when $n=2,4,p^k,$ or $2p^k$ where $p$ is an odd prime. In that case, classifying the generators is an open problem. You can read about it here.

-
If course, once you've found a generator for $\mathbb Z_p^\times$ you can easily find a generator for $\mathbb Z_{p^k}^\times$. The key problem is generators for $\mathbb Z_p^\times$ –  Thomas Andrews Aug 2 '13 at 23:40

Aside from obvious exclusions, such as perfect squares, it is hard to say much about how to find primitive roots in $\mathbb Z_p^\times$. They are distinctly badly behaved. Trial and error is about as good as you can get.

The first paragraph in this paper gives a rough outline. The next paragraph indicates a result known if the extended Riemann Hypothesis is true, which indicates the kind of complexity we are dealing with. (Note: In that paper, $\textrm{GF}(p)\cong\mathbb Z_p$.)

-