# Primitive roots and quadratic nonresidues modulo a prime of form $2^n+1$ [duplicate]

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.

## marked as duplicate by Daniel Fischer, Semiclassical, apnorton, William, Brian FitzpatrickAug 10 '14 at 6:32

• Pick a quadratic residue $a$, say $a = x^{2}$. What is the order of $a$ in terms of the order of $x$? Do you remember any theorems from group theory that may be relevant here? – A. Barron Jul 29 '14 at 4:49
• math.stackexchange.com/questions/572916/… – lab bhattacharjee Jul 29 '14 at 5:14
• This is essentially a duplicate of the question linked to by @lab (well done finding that!). The extra part about $3$ does need the law of quadratic reciprocity (see André's answer). – Jyrki Lahtonen Jul 29 '14 at 6:36

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$.