Let an odd prime $p = 2^n+1$. If $a$ is a quadratic non-residue modulo $p$ then by Euler's criterion $ a^{2^{n-1}} = -1 \pmod{2^n+1} $. How does this imply that that the order of $a$ is $2^n$?
I've seen a result that says $a$ is a primitive root modulo $m$ iff $a^{\phi(m)/p} \not \equiv 1 \pmod{m}$ for every prime divisor of $p$ of $\phi(m)$. That would straight away give us the result as $2$ is the only prime divisor of $\phi(2^n+1) = 2^n$, right?