0
$\begingroup$

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.

$\endgroup$
4
  • 3
    $\begingroup$ 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$. $\endgroup$
    – lulu
    Aug 2, 2021 at 16:46
  • 3
    $\begingroup$ 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$. $\endgroup$
    – Arturo Magidin
    Aug 2, 2021 at 19:19
  • $\begingroup$ @ArturoMagidin Do you mean that it suffices to show it is a proper divisor of $p-1$? $\endgroup$
    – Bean Guy
    Aug 2, 2021 at 19:24
  • 3
    $\begingroup$ 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$. $\endgroup$
    – Arturo Magidin
    Aug 2, 2021 at 19:27

0

Reset to default

You must log in to answer this question.