Exercise 4.4

Proof. Solution 1.

Suppose that $a$ is a primitive root modulo $p$. As $p-1$ is even, ${(-a)}^{p-1}=a^{p-1}\equiv 1(\mathit{mod}p)$.

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

Therefore $a^{2n}\equiv 1(\mathit{mod}p)$. As $a$ is a primitive root modulo $p$, $p-1\mid 2n$, $2t\mid n$, thus $n$ is even.

Since $(-1)n=1$, $a^n\equiv 1(\mathit{mod}p)$, and $p-1\mid n$. So the least $n\in {\mathbb{N}}^{\text{∗}}$ such that ${(-a)}^n\equiv 1(\mathit{mod}p)$ is $p-1$: the order of $-a$ modulo $p$ is $p-1$, $-a$ is a primitive root modulo $p$.

Conversely, if $-a$ is a primitive root modulo $p$, we apply the previous result at $-a$ to to obtain that $-(-a)=a$ is a primitive root.

Solution 2.

Let $p-1=2^{a_0}{p}_1^{a_1}\cdots p_k^{a_k}$ the decomposition of $p-1$ in prime factors.

As $p_i$ is odd for $i=1,2,\cdots k$, $(p-1)∕p_i$ is even, and $a$ is primitive, so

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