Primitive roots and quadratic nonresidues modulo a prime of form $2^n+1$ Let $p$ be a prime number. We call a unit $a$ in $\Bbb Z/p\Bbb Z$ a primitive root, if $\text{ord}_p(a)=p-1$.
Any unit in $\Bbb Z/p\Bbb Z$ can be written as some power as some power of $a$. if $p$ is of the form $2^n +1$, prove that the primitive roots in $\Bbb Z/p\Bbb Z$ are precisely the quadratic non-residues modulo $p$, if $n > 1$ , prove $3$ is always a primitive root.  
I tried but can't figure out.
 A: We look at the case where $p$ is a prime of the form $2^n+1$. The arguments will assume a certain number of background theorems.
Recall that a primitive root of the odd prime $p$ is always a quadratic non-residue of $p$.
Recall also that an odd prime $p$ always has $\varphi(\varphi(p))$ primitive roots, where $\varphi$ is the Euler $\varphi$-function.
In the case $p=2^n+1$, we have $\varphi(\varphi(p))=\varphi(2^n)=2^{n-1}$.
But $p$ has $\frac{p-1}{2}$, that is, $2^{n-1}$ quadratic non-residues.
Since every primitive root is a quadratic non-residue, and the number of non-residues and primitive roots is in this case the same, the two sets must be identical.
For the question about $3$, we first observe that if $n\gt 1$, and $2^n+1$ is prime, then $n$ is even. That is because if $n$ is odd then $2^n+1$ is divisible by $3$. (Parenthetically, $n$ must in fact be a power of $2$, these are the Fermat primes.) 
Note that if $n$ is even, then $2^n+1\equiv 2\pmod{3}$. Note also that $2^n+1\equiv 1\pmod{4}$. So by Quadratic Reciprocity, $3$ is a non-residue of $p$, and hence a primitive root.
Remark: The first question is substantially more elementary. If $a$ has order $p-1$ modulo $p$, then the powers $a,a^2,a^3,\cdots, a^{p-1}$ must be distinct modulo $p$. For if $a^i\equiv a^j\pmod{p}$, with $1\le i\lt j\le p-1$, then $a^{j-i}\equiv 1\pmod{p}$, contradicting the fact that $a$ has order $p-1$.
