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

From Number
Jump to: navigation, search

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

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 .