# Difference between revisions of "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 .

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