# $p=2^n+1$. Prove that every quadratic nonresidue modulo $p$ is a primitive root modulo $p$

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?

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.

If you know the basics of cyclic groups and their subgroups, then the following approach suggests itself.

The group $\Bbb{Z}_p^*$ is cyclic of order $p-1=2^n$. If $a$ is an element of order $2^n$, then it is primitive. OTOH if the order of $a$ is a factor of $2^{n-1}$, then it is a square, because the squares form the unique subgroup of order $2^{n-1}$. By the same argument a squre cannot be primitive.

• Wow, this is really neat! +1 – Alex Wertheim Nov 19 '13 at 7:33
• A very similar argument works, when $p=2q+1$, with both $p,q$ prime (Sophie Germain prime). An element is $a\in\Bbb{Z}_p^*$ is then a primitive root, iff its order is neither $2$ nor $q$. In the former case $a\equiv-1$, and in the latter case $a$ is a quadratic residue. Both of these possibilities can often be easily excluded. – Jyrki Lahtonen Nov 19 '13 at 7:37

A bit differently: With $r$ a primitive root, we can write $a\equiv r^m$ for some $m$. If $a$ is a quadratic nonresidue, clearly $m$ must be odd. Then $\gcd(m,2^n)=1$ and there exist $u,v\in\mathbb Z$ with $um+v2^n=1$. Thius implies $a^u=r^{um+v2^n}\equiv r$ and hence that $a$ is primitive.

Another approach using Euler’s criterion.

We know, by Euler’s criterion, that if $a$ is a quadratic non-residue, $$a^{(p-1)/2}\equiv -1\pmod p$$ But that would mean $$a^{2^{n-1}}\equiv -1\pmod p\tag 1$$ Since $p=2^n+1$, we have $\phi p=2^n$. So if the order of $p$ is $d$, then $d=2^k$ for some $k\le n$. But $k>n-1$ by (1), so $k=n$, i.e. $a$ is primitive.