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.

Possible Duplicate:
Finding a primitive root of a prime number

Given a field $F_p = \mathbb{Z}/p\mathbb{Z}$ I want to find all $x$ such that $\{x^n|n\in \mathbb{N}\} = F_p \setminus \{0\}$. Note that $x=2$ seems to work for a lot of primes, but only $3$ and $5$ work for $7$. I don't see a pattern, not until one such $x$ is found, that is. Is there a way to find such elements without brute force?

share|improve this question
    
This is a similar question: math.stackexchange.com/questions/124408/… –  Makoto Kato Aug 12 '12 at 9:17
    
Thanks, I didn't know they were called primitive roots. I'm not sure, whether I should close, delete the question or ask you to write your comment as an answer to accept? –  Karolis Juodelė Aug 12 '12 at 9:32
    
Note that $/\ne\setminus$. –  Did Aug 12 '12 at 10:13
add comment

marked as duplicate by Karolis Juodelė, Alex B., Did, Gerry Myerson, t.b. Aug 12 '12 at 13:42

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1 Answer

up vote 2 down vote accepted

Finding a primitive root is a difficult problem. There is a vast mathematical literature on the problem, which others more expert than me could point you to. Let me focus first on the issue of whether $2$ can be a primitive root to illustrate some points. It is known that $2$ is a quadratic residue (mod $p$) if $p \equiv \pm 1$ (mod 8). This means that for such primes $p,$ $2$ has multiplicative order at most $\frac{p-1}{2}$ in $\mathbb{Z}/p\mathbb{Z}$, and consequently has no chance to be a primitive root (mod $p$). In general, quadratic reciprocity can be used to exclude many possibilities for primitive roots (mod $p$). Given an integer $m$ with $1 \leq m \leq p-1$, it is in principle routine to determine whether $m$ is a quadratic residue (mod $p$). If it is a residue, it can't be a primitive root. However, if $m$ is a quadratic non-residue, that is no guarantee that $m$ is a primitive root (mod $p$). The only case where that is guaranteed is when $p$ is a Fermat prime, for then the order of $m$ must be a power of $2,$ and if $m$ is not the square of something else, it must generate the multiplicative group of $\mathbb{Z}/p\mathbb{Z}.$ This is only the beginning of the story, but it does explain why $2$ is not a primitive root (mod $7$), and for example, you can quickly see that $3$ and $5$ are quadratic non-residues (mod $17$), so they are both primitive roots (mod $17$). In fact, if $p$ is any Fermat prime greater than $5$, we see that $$\left( \begin{array}{cc} \underline{3}\\{p} \end{array} \right) = \left( \begin{array}{cc} \underline{p}\\{3} \end{array} \right) = \left( \begin{array}{cc} \underline{2}\\{3} \end{array} \right)= -1,$$ and $$\left( \begin{array}{cc} \underline{5}\\{p} \end{array} \right) = \left( \begin{array}{cc} \underline{p}\\{5} \end{array} \right) = \left( \begin{array}{cc} \underline{2}\\{5} \end{array} \right)= -1,$$ so that both $3$ and $5$ are primitive roots (mod $p$), However, life is rarely this easy when searching for primitive roots!

share|improve this answer
    
What is $\left( \begin{array}{cc} \underline{a}\\{b} \end{array} \right)$? –  Karolis Juodelė Aug 12 '12 at 12:03
    
@KarolisJuodelė, that is called Legendre's symbol. In fact I think that you shouldn't be dealing with that right now as it seems to be you're beginning with this stuff and that symbol is used in a little more advanced things, but if you want to can google it. –  DonAntonio Aug 12 '12 at 12:35
    
@Karolis: You can google "quadratic reciprocity" if you haven't seen it before. It will explain the Legendre symbol (also sometimes known as the Jacobi symbol). –  Geoff Robinson Aug 12 '12 at 12:40
add comment

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