# 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 .

## 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 .