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

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

The number of generators of $\Bbb Z_p^\times$ is $\phi(p-1)=\phi(2^n)=2^{n-1}$. Since half the elements of $\Bbb Z_p^\times$ are residues (and not generators), all the quadratic non-residues are generators.

If $\langle g\rangle\cong\Bbb Z_p^\times$ then $\langle g^i\rangle\cong\Bbb Z_p^\times\iff\gcd(p-1,i)=1$. Moreover, the number of generators of $\Bbb Z_p^\times$ is $\phi(p-1)$.

Proof: Let $g$ be a generator of $\Bbb Z_p^\times$ and consider the homomorphism $$\phi:\Bbb Z_p^\times\rightarrow\Bbb Z_p^\times\\g\mapsto g^i$$ Suppose that $\phi(g^m)=g^{mi}=1$.

• If $\gcd(p-1,i)=1$ then $p-1\mid m$ so that $g^m=1$ and $\ker(\phi)=\langle 1\rangle$.
• If $\gcd(p-1,i)=d\neq 1$ then $\langle 1\rangle\subset\langle g^{\frac{m}{d}}\rangle\subset\ker(\phi)$.

Let $S=\{x^2\mid x\in\Bbb Z_p\}$, that is, the set of quadratic residues in $\Bbb Z_p^\times$. Then $$|S|=\frac{1}{2}|\Bbb Z_p^\times|$$

Proof: Consider the homomorphism $$\phi:\Bbb Z_p^\times\rightarrow S\\x\mapsto x^2$$ $\ker(\phi)=\langle -1\rangle$, so $\Bbb Z_p^\times/\ker(\phi)\cong S$.