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

Statement

Suppose $p$ is a safe prime, i.e., $p$ is an odd prime such that $(p-1)/2$ is also prime (in other words $(p-1)/2$ is a Sophie Germain prime). Then, if $a$ is a quadratic nonresidue modulo $p$ that is not congruent to $-1$ modulo $p$, then $a$ is a primitive root modulo $p$.

Related facts

Applications

• Safe prime has plus or minus two as a primitive root

Facts used

1. Euler's criterion

Proof

Given: A safe prime $p$, a quadratic nonresidue $a$ modulo $p$ other than $-1$.

To prove: $a$ is a primitive root modulo $p$.

Proof: By Fermat's little theorem, the order of $a$ modulo $p$ is a factor of $p-1$. The only factors of $p-1$ are $1,2,(p-1)/2,p-1$. (If $p=5$, two of these factors become equal).

• The order of $a$ cannot be $1$ or $(p-1)/2$ since $a^{(p-1)/2}\equiv -1{\pmod {p}}$ by fact (1).
• The order of $a$ cannot be $2$ since the only element of order two is $-1$, and $a$ is not $-1$ modulo $p$ by assumption.

This forces the order to be $p-1$, so $a$ is a primitive root.