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

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?

• Do you mean the order of the group $\mathbb{Z}_p^*$ or do you mean the order of each element in the group? Suggest an edit here.
– Lev
Oct 19, 2022 at 0:05
• @Lev made the edit Oct 19, 2022 at 0:13
• slightly tweaked it, hope thats okay. Hope my answer below helps.
– Lev
Oct 19, 2022 at 0:17

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

• why is it important that the order of g is p-1? Oct 20, 2022 at 1:30
• @John Rawls: in some applications, we want $x\mapsto g^x\bmod p$ to be a bijection of the set $\{1,\ldots,p-1\}$; that's equivalent to $g$ having order $p-1$. In some others (including textbook Diffie-Hellman), that's customary, even though it would be as good to have $g$ of prime order $(p-1)/2$. Oct 20, 2022 at 5:50

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

• dont we want to have $g^k \ne1 \bmod p$? I thought g is a generator iff $g^{(p-1)/q} \ne 1 \bmod p$ Oct 19, 2022 at 0:31
• Exactly. (2) leads to a contradiction in the assumption that $m$ was not equal to $p-1$.
• Well, that should follow from the fact that $m$ is not $p-1$, or any of the $k$s and that $m$ divides $p-1$.
• Well we want a generator of the group. If you keep taking powers of a generator, you get every element in the group. A generator is an element which has the same order as the group. This is useful in a manner of ways. We can even write the group as $\langle g \rangle$. That is, the group generated by g (with the group operation given).