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

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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

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