# Generator of multiplicative group of $\mathbb{Z}/p\mathbb{Z}$ [duplicate]

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?

-

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

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

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!

-
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