Quadratic nonresidue that is not minus one is primitive root for safe prime
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 .
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.