Safe prime has plus or minus two as a primitive root

From Number
Jump to: navigation, search

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:

Related facts

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.