Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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