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.