# $p$ an prime number of the form $p=2^m+1$. Prove: if $(\frac{a}{p})=-1$ so $a$ is a primitive root modulo $p$

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.

-
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

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

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

i.e.

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

i.e.

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

-

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

-

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

-
Is the OP allowed to assume the existence of a primitive root? – fretty Jun 8 '12 at 11:43