Proof that checking if $g^k\bmod p\ne1$ finds a generator of a cyclic group

Question

In this post the top answer says that for $\mathbb Z_p^*$, $k$, the order of an element $g$, divides p-1. Then it was concluded that this entails we can check if $g$ is a generator by checking if $g^k\bmod p\ne1$, with $k=(p-1)/q$ for $q$ each of the distinct prime factors of $p-1$.

Why does the first claim being true entail the conclusion that the test is valid?

Answer 1

The quoted post states that for prime $p$, the order $k$ of any element $g$ of $\mathbb Z_p^*$ divides $p-1$. That is because $\mathbb Z_p^*$, or equivalently $\{1,\ldots,p-1\}$, is a group of $p-1$ elements under multiplication modulo $p$, and then a consequence of (one of) Lagrange's theorem.

If an element $g$ has order $k$ that divides $p-1$, then by definition of divides there is some (uniquely defined) integer $u\ge1$ such that $p-1=k\,u$. The element $g$ is of order $p-1$ if and only if that $u$ is $1$.

If $u$ is not $1$, then there is some prime $q$ dividing $u$ (thus $q$ dividing also $p-1)$, and some integer $v\ge1$ with $u=q\,v$, thus with $p-1=k\,q\,v$; and since $g$ has order $k$, it holds $g^k\bmod p=1$, therefore $\left(g^k\right)^v\bmod p=1$, therefore $g^{k\,v}\bmod p=1$, therefore $g^{(p-1)/q}\bmod p=1$.

Hence if $g$ is not of order $p-1$, then there is some prime $q$ dividing $p-1$ such that $g^{(p-1)/q}\bmod p=1$.

By contraposition, if for every prime $q$ dividing $p-1$ it holds $g^{(p-1)/q}\bmod p\ne1$, then $g$ is of order $p-1$.

Note: sometime, $p$ is chosen as a safe prime, meaning $p$ and $(p-1)/2$ are prime. A test that $g$ is a generator (that is, has the maximal order $p-1$) then boils down to $g^2\bmod p\ne1$ (equivalently, $g\bmod p\ne1$ and $g\bmod p\ne p-1$ ) and $g^{(p-1)/2}\bmod p\ne1$. For a test that $g$ has (prime) order $(p-1)/2$, replace that last test with $g^{(p-1)/2}\bmod p=1$.

Answer 2

Because if $g^k \neq 1 \mod p$ for all the possible choices of $k$, then that implies that the order of $g$ is strictly greater than all the values of $k$. i.e. the order of $g$ is $p-1$

To see this, suppose that the test concludes with $g^k \neq 1 \mod p$ for all $k$, but that there exists an integer $m < p-1$ such that $g^m = 1 \mod p$. That is, $g$ is not a generator of the group. As an exercise, try these steps:

1. Show that $m$ must divide one of the values of $k$.
2. Hence show that $g^k = 1 \mod p$ (for the $k$ above).

(2) is a contradiction.