Exercise 4.7

Proof. The first examples of such couples $(q,p)$ are $(5,11),(29,59),(41,83),(53,107),(89,179)$.

$p=2q+1=8t+3$ and $p,q$ are prime numbers.

From Fermat’s little theorem, $2^{p-1}\equiv 1(\mathit{mod}p)$, so $2^{2q}\equiv 1(\mathit{mod}p)$.

The order of $2$ modulo $p$ divides $2q$ : to prove that the order of $2$ is $2q=p-1$, it is sufficient to prove that

If $2^2\equiv 1(\mathit{mod}p)$, then $p\mid 3$, $p=3$ and $q=1$ : $q$ is not a prime, so $2^2\not\equiv 1(\mathit{mod}p)$.

If $2^q=2^{(p-1)∕2}\equiv 1(\mathit{mod}p)$, then $2$ is a square modulo $p$ (prop. 4.2.1), there exists $a\in \mathbb{Z}$ such that $2\equiv a^2(\mathit{mod}p)$.

From the complementary case of the law of quadratic reciprocity (see next chapter, prop. 5.1.3), $2$ is a square modulo $p$ iff

Yet $p\equiv 3(\mathit{mod}8)$, so $p^2\equiv 9(\mathit{mod}16)$, $\left(\frac{2}{p}\right)={(-1)}^{(p^2-1)∕8}=-1$, so $2$ is not a square modulo $p$. This is a contradiction, so $2^q\not\equiv 1(\mathit{mod}p)$ : $2$ is a primitive root modulo $p$. □