Exercise 2.8.21 (When is $-g$ a primitive root?)

Proof. Let $p$ be an odd prime, and $g$ a primitive root of $p$. We prove that $-g$ is a primitive root if and only if $p\equiv 1(\mathit{mod}4)$.

• If $p\equiv 3(\mathit{mod}4)$, then $p=4k+3,k\in \mathbb{N}$. Since $g^{(p-1)∕2}\equiv -1(\mathit{mod}p)$ (see Problem 15),

  $${(-g)}^{(p-1)∕2}={(-1)}^{2k+1}{g}^{(p-1)∕2}\equiv 1(\mathit{mod}p),$$

  thus $-g$ is not a primitive root.

• If $p\equiv 1(\mathit{mod}4)$, then $p=4k+1,k\in \mathbb{N}$. Let $d$ be a positive integer such that $d\mid p-1,d\ne p-1$, so that $p-1=\mathit{ld},l\ge 2$. To prove that $-g$ is a primitive root modulo $p$, it suffices to show that ${(-g)}^d\not\equiv 1(\mathit{mod}p)$.

  Assume for contradiction that ${(-g)}^d={(-1)}^d{g}^d\equiv 1(\mathit{mod}p)$. Then, either ${(-1)}^d=1$ and $g^d=1$, or ${(-1)}^d=-1$ and $g^d=-1$.

  In the former case, $g^d=1$. This is impossible since $g$ has order $p-1$ and $1\le d<p-1$.

  In the later case, $d$ is odd, and $g^d=-1$. Then $g^{2d}=1$, where $1<2d\le \mathit{ld}=p-1$. Since the order of $g$ is $p-1$, $2d=p-1$, thus $(p-1)∕2=d$ is odd, in contradiction with $(p-1)∕2=2k$.

  This proves that ${(-g)}^d\not\equiv 1$ for every divisor $d$ of $p-1$ ( $d\ne 1,d\ne p-1$). Therefore $-g$ has order $p-1$ modulo $p$, so $-g$ is a primitive root.

  So $-g$ is a primitive root, or not, according as $p\equiv 1(\mathit{mod}4)$ or $p\equiv 3(\mathit{mod}4)$.