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

From Number

## Statement

Suppose is a safe prime, i.e., is an odd prime such that is also prime (this is equivalent to saying that is a Sophie Germain prime).

Then:

- If , is a primitive root modulo .
- If , then , and is a primitive root modulo .
- If , then , and is a primitive root modulo .

## Facts used

- Quadratic nonresidue that is not minus one is primitive root for safe prime
- Congruence condition for minus one to be a quadratic residue
- Congruence condition for two to be a quadratic residue: For an odd prime , is a quadratic residue modulo iff , and a nonresidue iff .

## Proof

**Given**: A safe prime .

**To prove**: If or , then is a primitive root modulo . If , then is a primitive root modulo .

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

The cases and are settled by fact (3).

In the case , . By facts (2) and (3), is a quadratic residue modulo and is a quadratic nonresidue modulo . Thus, is a quadratic nonresidue modulo , completing the proof.