# Proving the generator criterion for group $Zp$

I am trying to understand how to find a generator of Zp. How to find generator $g$ in a cyclic group?.
I have heard that we can pick random a Zp and for each primitive d| p-1 check wether:
a^[(p-1)/d] != 1 .If it holds it is a generator, otherwise it is not.

Why does this hold? If a is of order q | p-1 then all I can see is that from Fermat's theorem:
a^(p-1) = a^(q* p-1/q) = 1 mod p

• You are actually trying to find a generator of the multiplicative subgroup $\mathbb Z_p^*$ of $\mathbb Z_p$ aka $\mathbb Z/p\mathbb Z$. The $*$ denotes exclusion of element(s) without multiplicative inverse, and the use of multiplication as the group law.
– fgrieu
Jan 30, 2023 at 11:00

• Here is my new effort: If $ord(a)=d \implies a^d=1 \mod p$ then since $(a^{(p-1)/d})^d=1$ the order of $b=a^{p-1/d}$ must divide d . Assume $p-1/d = k \in N$ then $a^k$ must belong in the subgroup of a.. how can I go on? Feb 2, 2023 at 18:27
• Let $D$ be the set of divisors of p-1 except for 1. Consider the set $C= \{(p-1)/d \mid d \in D\}$. Why does this set $C$ contain all divisors of p-1 except p-1? Feb 4, 2023 at 4:33