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

From Number
Jump to: navigation, search

Statement

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

Related facts

Applications

Facts used

  1. Euler's criterion

Proof

Given: A safe prime , a quadratic nonresidue modulo other than .

To prove: is a primitive root modulo .

Proof: By Fermat's little theorem, the order of modulo is a factor of . The only factors of are . (If , two of these factors become equal).

  • The order of cannot be or since by fact (1).
  • The order of cannot be since the only element of order two is , and is not modulo by assumption.

This forces the order to be , so is a primitive root.