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$?

  • $\begingroup$ 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)$. $\endgroup$ – Erick Wong Jul 14 '12 at 7:09

The relevant phrase to look up here is primitive root. There is still a bit of mystery surrounding primitive roots. It is neither 'easy' to find all primitive roots for a given prime nor easy to say for what set of numbers a particular number might be a primitive root.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.