Safe prime has plus or minus two as a primitive root

Statement

Suppose $p$ is a safe prime, i.e., $p$ is an odd prime such that $(p-1)/2$ is also prime (this is equivalent to saying that $(p-1)/2$ is a Sophie Germain prime).

Then:

• If $p=5$, $2$ is a primitive root modulo $p$.
• If $(p-1)/2\equiv 1{\pmod {4}}$, then $p\equiv 3{\pmod {8}}$, and $2$ is a primitive root modulo $p$.
• If $(p-1)/2\equiv 3{\pmod {4}}$, then $p\equiv 7{\pmod {8}}$, and $-2$ is a primitive root modulo $p$.

Related facts

• Quadratic nonresidue equals primitive root for Fermat prime
• Quadratic nonresidue that is not minus one is primitive root for safe prime

Facts used

1. Quadratic nonresidue that is not minus one is primitive root for safe prime
2. Congruence condition for minus one to be a quadratic residue
3. Congruence condition for two to be a quadratic residue: For an odd prime $p$, $2$ is a quadratic residue modulo $p$ iff $p\equiv \pm 1{\pmod {8}}$, and a nonresidue iff $p\equiv \pm 3{\pmod {8}}$.

Proof

Given: A safe prime $p$.

To prove: If $p=5$ or $(p-1)/2\equiv 1{\pmod {4}}$, then $2$ is a primitive root modulo $p$. If $(p-1)/2\equiv 3{\pmod {4}}$, then $-2$ is a primitive root modulo $p$.

Proof: Since $p>3$, neither $2$ nor $-2$ is congruent to $-1$ modulo $p$. Thus, by fact (1), it suffices to show in either case that $2$ (or $-2$) is a quadratic nonresidue modulo $p$.

The cases $p=5$ and $(p-1)/2\equiv 1{\pmod {4}}$ are settled by fact (3).

In the case $(p-1)/2\equiv 3{\pmod {4}}$, $p\equiv -1{\pmod {8}}$. By facts (2) and (3), $2$ is a quadratic residue modulo $p$ and $-1$ is a quadratic nonresidue modulo $p$. Thus, $-2$ is a quadratic nonresidue modulo $p$, completing the proof.