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
.