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

From Number

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

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