Use Lagrange's Theorem to prove g=5 is a generator of the multiplicative group G of integers modulo p that are coprime to p of prime order p=647.

Question

Prove g=5 is a generator of the multiplicative group G of integers modulo p that are coprime to p prime order p=647.

I have approached this using Lagrange's Theorem to show that all non-identity elements of G are generators, hence g=5 is a generator.

Is there another way to use Lagrange's Theorem to prove the statement and if so how?

If not then would the way I have proved it be sufficient?

Answer 1

The order of $G$ is $p-1=646=2 \cdot 17 \cdot 19$. It is enough to prove that the order of $5$ is not any proper divisor of $646$, which are $\{1, 2, 17, 19, 34, 38, 323\}$. Actually, it is enough to prove that $5^k \not\equiv 1 \bmod 647$ for $k \in \{ 646/2, 646/17, 646/19 \} = \{34, 38, 323\}$.