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

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