Exercise 4.6

Proof.

Solution 1 (with quadratic reciprocity).

Write $p=2^k+1$, with $k=2^n$.

We suppose that $n>0$, so $k\ge 2,p\ge 5$. As $p$ is prime, $3^{p-1}\equiv 1(\mathit{mod}p)$.

In other words, $3^{2^k}\equiv 1(\mathit{mod}p)$: the order of $3$ is a divisor of $2^k$, a power of $2$.

$3$ has order $2^k$ modulo $p$ iff $3^{2^{k-1}}\not\equiv 1(\mathit{mod}p)$. As ${\left(3^{2^{k-1}}\right)}^2\equiv 1(\mathit{mod}p)$, where $p$ is prime, this is equivalent to $3^{2^{k-1}}\equiv -1(\mathit{mod}p)$, which remains to prove.

$3^{2^{k-1}}=3^{(p-1)∕2}\equiv \left(\frac{3}{p}\right)(\mathit{mod}p)$.

Since $n\ge 1$, $k\ge 2$, thus $2^{k-1}$ is even. By the law of quadratic reciprocity,

Therefore $\left(\frac{3}{p}\right)=\left(\frac{p}{3}\right)$, and

so $\left(\frac{3}{p}\right)=\left(\frac{p}{3}\right)=-1$, that is to say

The order of $3$ modulo $p=2^{2^n}+1$ is $p-1=2^{2^n}$, i.e. $3$ is a primitive root modulo $p$.

(On the other hand, if the order of $3$ modulo $p$ is $p-1$, then $p$ is prime, so

Solution 2 (without quadratic reciprocity, with the hint of chapter 4).

As above, if we suppose that $3$ is not a primitive root modulo $p$, then

where $k=2^n\ge 2$, and $p=2^k+1$.

Therefore ${(-3)}^{(p-1)∕2}=3^{2^{k-1}}\equiv 1(\mathit{mod}p)$, thus $-3$ is a square modulo $p$. So there is some $a\in \mathbb{Z}$ such that $-3\equiv a^2(\mathit{mod}p)$.

As $2\wedge p=1$, $2$ has an inverse modulo $p$, so there exists $u\in \mathbb{Z}$ such that $2u\equiv -1+a(\mathit{mod}p)$ ( $\bar{u}$ is similar to $\omega =\frac{-1+i\sqrt{3}}{2}\in ℂ$). Then

As $p\wedge 2=p\wedge 8=1,u^3\equiv 1(\mathit{mod}p)$. Moreover, if $u\equiv 1(\mathit{mod}3)$, then $a\equiv 3(\mathit{mod}p)$, $-3\equiv 9(\mathit{mod}p),p\mid 12$, so $p=2$ or $p=3$, in contradiction with $p\ge 5$. So the order of $u$ modulo $p$ is $3$ : ${(\mathbb{Z}∕\mathit{p\mathbb{Z}})}^{\text{∗}}$ contains an element $\bar{u}$ of order $3$. So $3\mid p-1$, $p\equiv 1(\mathit{mod}3)$, but $p\equiv {(-1)}^{2^n}+1\equiv 2\equiv -1(\mathit{mod}3)$ : this is a contradiction, so $3$ is a primitive root modulo $p=2^{2^n}+1$. □