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.