Safe prime has plus or minus two as a primitive root

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 .

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 , 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.