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