Exercise 3.2.16* (If $F_n = 2^{2^n}+1$ is prime, $3,5,7$ are primitive roots modulo $F_n$ ($n1$))

Question

Show that if $p = 2^{2^n}+ 1$ is prime then $3$ is a primitive root $\pmod p$ and that $5$ and $7$ are primitive roots provided that $n>1$.

Richard Ganaye · Accepted Answer

ewcommand{\legendre}[2]{\genfrac{(}{)}{}{}{#1}{#2}}

\begin{proof} Assume that $p = 2^{2^n}+ 1$ is prime, where $n$ is a positive integer ($3$ is not a primitive root of $F_3 = 3$). Since $p = 2^{2\cdot 2^{n-1}} +1 = 4^{2^{n-1}} + 1 = 4^N + 1$, where $N = 2^{n-1} \geq 1$, we may repeat the arguments of Problem 15 (see Problem 15 for more details):

$$\legendre{3}{p} = \legendre{p}{3} =  \legendre{4^N + 1}{3} = \legendre{2}{3} = -1,$$
therefore $3^{(p-1)/2} \equiv -1\pmod p$, so $3^{p-1} \equiv 1 \pmod p.$ This gives
$$3^{2^{2^{n} - 1}} \equiv -1 \pmod p, \qquad 3^{2^{2^n}} \equiv 1 \pmod p.$$
If $d$ is the order of $3$ modulo $p$, then $d \mid 2^{2^n}$, but $d 
mid 2^{2^n-1}$. Hence $d = 2^{2^n} = p-1$. This shows that $3$ is a primitive element modulo $p = 2^{2^n}+1$.

(Alternatively, we have proved by another way in Problem 3.1.21 that any quadratic nonresidue modulo a Fermat number  is a primitive root.)

\bigskip
Suppose now that $n>1$. Using $p \equiv 1 \pmod 4$, the law of quadratic reciprocity shows that
\begin{align*}
\legendre{5}{p} &= \legendre{p}{5} \
&=\legendre{2^{2^n} + 1}{5}\
&=\legendre{(2^4)^{2^{n-2}} + 1}{5}\
&=\legendre{2}{5} & (	ext{since } 2^4 \equiv 1 \pmod 5)\
&= -1.
\end{align*}
Similarly,
\begin{align*}
\legendre{7}{p} &= \legendre{p}{7} \
\end{align*}
Moreover, for every exponent $k \geq 2$
\begin{align*}
2^{2^k}  &= 2^{2^2\cdot 2^{k-2}} \
&= 16^{2^{k-2}}\
&\equiv 2^{2^{k-2}} \pmod 7.
\end{align*}
By an obvious induction, we obain $2^{2^n} \equiv 2^{2^{n-2j}}\pmod 7$ for all $j$ such that $n-2j\geq 0$. Hence
\begin{align*}
2^{2^n} \equiv 2^{2^0} \pmod 7& 	ext{ if } n 	ext{ is even,}\
2^{2^n} \equiv 2^{2^1} \pmod 7& 	ext{ if } n 	ext{ is odd.}
\end{align*}
Therefore $p \equiv 3 \pmod 7$ or $p \equiv 5 \pmod 7$. Since the quadratic residues modul $7$ are $1,2,4$, this shows that $p$ is a quadratic non residue modulo $7$. Hence
\begin{align*}
\legendre{7}{p} &= \legendre{p}{7} = -1. \
\end{align*}
Since any quadratic nonresidue modulo a Fermat number  is a primitive root, (Problem 3.1.21), $3$, $5$ and $7$ are primitive roots modulo $p$.
\end{proof}

Verification with Sage that $F_n \equiv 3,5 \pmod 7$:
\begin{verbatim}
sage: def F(n):
....:     return 2^(2^n) + 1
....: 
sage: [F(n) % 7 for n in range(2,15)]
[3, 5, 3, 5, 3, 5, 3, 5, 3, 5, 3, 5, 3]

sage: [F(n) % 5 for n in range(2,15)]
[2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]

sage: [F(n) % 3 for n in range(2,15)]
[2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]\end{verbatim}

Exercise 3.2.16* (If $F_n = 2^{2^n}+1$ is prime, $3,5,7$ are primitive roots modulo $F_n$ ($n>1$))

Answers

Comments

Exercise 3.2.16* (If $F_n = 2^{2^n}+1$ is prime, $3,5,7$ are primitive roots modulo $F_n$ ($n>1$))

Answers

Comments

Add answer