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.

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?

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

2 Answers 2

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.

share|improve this answer
    
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$.)

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.