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

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.
