# Multiplicative group of a prime field is generated by all primes less than square root plus one

## Statement

Suppose is an odd prime. The multiplicative group modulo is generated by the congruence classes of all primes less than .

## Related facts and conjectures

• Smallest quadratic nonresidue is less than square root plus one
• Extended Riemann hypothesis: A stronger form of the Riemann hypothesis that is equivalent to the statement that the smallest quadratic nonresidue modulo , for any odd prime , is less than , where here is the natural logarithm.
• Artin's conjecture on primitive roots: This is a closely related conjecture that states that every integer that is not or a perfect square occurs as a primitive root for infinitely many primes.

## Proof

Given: An odd prime , is the subgroup of the multiplicative group modulo generated by all primes less than .

To prove: is the whole multiplicative group modulo .

Proof: Note first that any positive integer less than is a product of primes less than . Hence, its congruence class is in .

Let be the smallest positive integer whose congruence class is not in . Then, .

Let be the smallest positive integer such that , and . Since is prime, , so . Further, we have: .

Since is not in , either or . However, since , , while . Thus, we have found a positive integer smaller than that is also not in , contradicting minimality of .