Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $p$ be an odd prime number of the form $p=2^m+1$.

I'd like your help proving that if $a$ is an integer such that $(\frac{a}{p})=-1$, then $a$ is a primitive root modulo $p$.

If $a$ is not primitive root modulo $p$ so $Ord_{p}(a)=t$, where $t<p-1=2^m$ and $t|2^m$ since $Ord_{p}(a)|p-1$ . I also know that there are no solutions to the congruence $x^2=a(p)$, How can I use it in order to reach a contradiction?

Thanks a lot.

share|cite|improve this question
Are you allowed to assume the existence of a primitive root to begin with? My solution does not use this but the other one does. – fretty Jun 8 '12 at 11:45
up vote 6 down vote accepted

Ok well we know by Fermat's little theorem that:

$a^{p-1} \equiv 1$ mod $p$


$a^{2^m} \equiv 1$ mod $p$

Now $a$ must have order $2^i$ for some $0\leq i\leq m$ by Lagrange's theorem.

But the fact that the Legendre symbol is $-1$ coupled with Euler's criterion tells us that:

$a^{\frac{p-1}{2}} \equiv \left(\frac{a}{p}\right)$ mod $p$


$a^{2^{m-1}} \equiv -1$ mod $p$

So that $a$ cannot have order $2^i$ for $0\leq i < m$ (otherwise this congruence would be false).

Thus $a$ has order $2^m$, and so is a primitive root.

share|cite|improve this answer

Here is an easy counting argument.

The number of primitive roots of any prime $p$ is $\varphi(\varphi(p))$. Since $\varphi(p)=2^m$, and $\varphi(\varphi(p))=2^{m-1}$, there are $2^{m-1}$ primitive roots of $p$.

There are only $2^{m-1}$ quadratic non-residues of $p$. The primitive roots are a subset of the quadratic non-residues.

So every quadratic non-residue of $p$ is a primitive root of $p$.

share|cite|improve this answer

Let $x$ be any primitive root and write $a \equiv x^k \pmod p$. Since $a$ is not a quadratic residuo modulo $p$, $k$ must be odd. The order of $a$ divides $p-1 = 2^m$, so $\operatorname{ord}(a) = 2^l$ for some $l \leq m$. We have $1 \equiv a^{2^l} \equiv x^{k2^l}$. The order of $x$ is $2^m$, so $2^m |k2^l$. But $k$ is odd, so $2^m | 2^l \pmod p$, hence $m=k$. From $\operatorname{ord}(a) = 2^m$ follows that $a$ is a primitive root modulo $p$.

share|cite|improve this answer
Is the OP allowed to assume the existence of a primitive root? – fretty Jun 8 '12 at 11:43

Your Answer


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.