If $x^d \equiv 1 \pmod{p}$ has full number of roots, $d\mid p-1$?

Question

Let $p$ be a prime. What I know is that $d\mid p-1$ then $x^d \equiv 1 \pmod{p}$ has the maximum possible number of roots, that is, $d$. I am wondering if the converse holds. I have searched for $d\not\mid p-1$ that still has $d$ many roots in the equation, but I could not find one up to $p=23$ (unless my calculation was not complete). Is there a counter-example to the converse?

Answer 1

Yes, the converse holds.

We have $x^m \equiv 1 \bmod{p}$ iff $x^d \equiv 1 \bmod{p}$, where $d=\gcd(m,p-1)$.

Moreover, $x^d \equiv 1 \bmod{p}$ has exactly $d$ roots because $\mathbb F_p^\times$ is cyclic.

Therefore, $x^d \equiv 1 \bmod{p}$ has $d$ roots iff $d$ divides $p-1$.

Answer 2

Use Discrete Logarithm

$$x^d\equiv1\pmod p\implies$$

$d\cdot $ind$_gx\equiv0\pmod{p-1}$ for an primitive root $g\pmod p$

What if ind$_gx\equiv1\pmod{p-1}$

Alternatively, let $G=(d,p-1)$ and $\dfrac dD=\dfrac{p-1}Q=G\implies(D,Q)=1$

$D\cdot $ind$_gx\equiv0\pmod Q\implies Q$ must divide ind$_gx$

For maximum root $Q$ must be $=1$