This is another one of the number theory problems I've been struggling with as of late (hopefully I'm not posting too many questions at once!).
Let $n$ be a positive integer and let $p=2^n+1$ be a prime number.
Prove that every quadratic nonresidue modulo $p$ is a primitive root
modulo $p$.
Suppose $a$ is a quadratic nonresidue and $r$ a primitive root muodulo $p$. Then there exists no $x$ such that $x^2 \equiv a \mod p$. We must determine the order of $a$. We know that $a$ must be congruent to some power of $r$, say $m$, since $\{r^1,r^2,\ldots,r^{2^n}\}$ is a reduced residue system modulo $p$. Suppose that $\mathrm{ord}_p a=b$. Then $a^b \equiv r^{mb} \equiv 1 \mod p$. We must show that $b=2^n$ since $\phi(p)=2n$. But $r$ is a primitive root and so $mb \equiv 0 \mod{2^n}$ (or $\equiv 2^n \mod{2^n}$). Hence $mb = 2^n k$. How can I finish it?
Best Answer
We will use standard results that you may be familiar with. There are $2^{n-1}$ quadratic non-residues of $p$.
There are $\varphi(\varphi(p))$ primitive roots of $p$. Thus there are $2^{n-1}$ primitive roots of $p$.
It follows that every quadratic non-residue is a primitive root.