# Why it is sufficient to look at prime divisor of $p-1$ when finding generators of $\mathbb{Z}_p^*$?

Let's say that I want to find the generators of $$\mathbb{Z}_p^*$$, where $$p$$ is a prime number. I found the following necessary and sufficient condition:

An element $$x \in \mathbb{Z}_p^*$$ is a generator of $$\mathbb{Z}_p^*$$ if and only if $$x^{\frac{p-1}{t}} \neq 1, \text{ for every prime divisor t} \text{ of } p-1.$$

Why is this true? I mean, why it is enough to check for prime divisor of $$p-1$$ instead of for every $$r$$ such that $$1 \leq r < p-1$$ (that is, the definition of generator).

I have also found another necessary and sufficient condition regarding primitive $$n$$-th roots of unity in $$\mathbb{Z}_p^*$$ with the same problematic:

Let $$n$$ be an integer such that $$1 \leq n \leq p-1$$. An element $$x > \in \mathbb{Z}_p^*$$ is a primite $$n$$-th root of unity in $$\mathbb{Z}_p^*$$ if and only if $$x^{\frac{n}{t}} \neq 1, \text{ for every prime divisor t} \text{ of } n.$$

I suppose that answering the previous problematic would also solve this one.

• Argue that: If $x$ has order $\frac {p-1}d$ for some proper divisor $d$ of $p-1$, then let $q$ be any prime divisor of $d$. Then $x^{(p-1)/q}\equiv 1 \pmod p$.
– lulu
Aug 2, 2021 at 16:46
• By Fermat's Little Theorem, $a^{p-1}\equiv 1\pmod{p}$ (if $\gcd(a,p)=1$). So we know the order is a divisor of $p-1$, by Lagrange's Theorem. So it suffices to show it is not a proper divisor of $p-1$. Aug 2, 2021 at 19:19
• @ArturoMagidin Do you mean that it suffices to show it is a proper divisor of $p-1$? Aug 2, 2021 at 19:24
• You are trying to show that the order is exactly $p-1$ (for it to be a primitive root/generator) so you want to show that the order is not a proper divisor of $p-1$. Aug 2, 2021 at 19:27