Multiplicative group of a prime field is generated by all primes less than square root plus one
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.
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 .