Is there a necessary and sufficient condition to determine the generators of $\mathbb{Z}_p^\times$?

This is something I was wondering about.

I know that the generators of the cyclic groups $(\mathbb{Z}_n,+)$ are precisely those integers coprime to $n$, and there are $\phi(n)$ of them. Now the multiplicative group of a finite field $\mathbb{Z}_p$ is cyclic of order $p-1$, and thus isomorphic to $(\mathbb{Z}_{p-1},+)$.

Is there a similar condition about which elements are generators as in the additive case? Being coprime doesn't work, since $1$ is never a generator. What I usually do is find at least one generator of $\mathbb{Z}_p^\times$, and consider this the image of $1$ under some induced isomorphism from $(\mathbb{Z}_{p-1},+)\to(\mathbb{Z}_p^\times,\cdot)$, and then the images of generators in $(\mathbb{Z}_{p-1},+)$ are the generators in $(\mathbb{Z}_p^\times,\cdot)$.

Is there a more efficient method that doesn't require first finding a generator in $\mathbb{Z}_p^\times$?

• The simplest description would just be "those elements whose multiplicative order is $p-1$". Perhaps more satisfying would be they are the roots of the cyclotomic polynomial $\Phi_{p-1}(x)$. – Erick Wong Jul 14 '12 at 7:09