Exercise 4.5

Proof. Let $a$ a primitive root modulo $p$.

Then $a^{p-1}\equiv 1(\mathit{mod}p)$, $p\mid (a^{(p-1)∕2}-1)(a^{(p-1)∕2}+1)$, thus $p\mid a^{(p-1)∕2}-1$ or $p\mid a^{(p-1)∕2}+1$. Since $a$ is a primitive root modulo $p$, $a^{(p-1)∕2}\not\equiv 1(\mathit{mod}p)$, thus

Hence ${(-a)}^{(p-1)∕2}={(-1)}^{2t+1}{a}^{(p-1)∕2}\equiv (-1)\times (-1)=1(\mathit{mod}p)$.

Suppose that ${(-a)}^n\equiv 1(\mathit{mod}p)$, with $n\in \mathbb{N}$.

Then $a^{2n}={(-a)}^{2n}\equiv 1(\mathit{mod}p)$, so $p-1\mid 2n,\frac{p-1}{2}\mid n$.

This proves that $-a$ has order $(p-1)∕2$ modulo $p$.

Conversely, suppose that $-a$ has order $(p-1)∕2=2t+1$ modulo $p$. Let $2,p_1,\dots p_k$ the prime factors of $p-1$, where the primes $p_i$ are odd.

$a^{(p-1)∕2}=a^{2t+1}=-{(-a)}^{2t+1}=-{(-a)}^{(p-1)∕2}\equiv -1$, so $a^{(p-1)∕2}\not\equiv 1(\mathit{mod}2)$.

As $p-1$ is even, $(p-1)∕p_i$ is even, thus

$a^{(p-1)∕p_i}={(-a)}^{(p-1)∕p_i}\not\equiv 1(\mathit{mod}p)$ (since $-a$ has order $p-1)$.

So the order of $a$ is $p-1$ (see Ex. 4.8) : $a$ is a primitive root modulo $p$. □