# Application of Lagrange's theorem for the number of roots of a polynonial modulo a prime

The question is: Let p be prime and d be a positive factor of p-1. Use Lagrange's theorem for the number of roots of a polynomial modulo a prime to prove that,

$$x^{\frac{p-1}{d}}$$ takes exactly d distinct values modulo p as x ranges over 1,2,...,p-1.

My attempt: I think a way of approaching this question is by raising $x^{\frac{p-1}{d}}$ to the power d and then applying the before mentioned theorem. So my solution follows,

$$(x^{\frac{p-1}{d}})^{d} \equiv 1 \mod p$$ $$\Rightarrow (x^{\frac{p-1}{d}}) \equiv \pm1 \mod p$$

Let g be a primitive root mod p so we obtain {$1, g, g^2,..., g^{(p-2)}$}={$1,2,...,p-1$}.

I'm really unsure if this method is correct and whether I've even used the theorem so any advice would be appreciated.

P.S. I apologise for the formatting as this is my first question.

• What does the result you are supposed to use tell? (Your method cannot possibly be correct. You say it is $\pm 1$ if this were true, there'd be two values namely $\pm 1$ not $d$.) – quid Jul 15 '17 at 10:33

## 1 Answer

This is the sort of result one proves before deducing the existence of primitive roots, so it's a good idea to avoid using them.

It doesn't follow that $y^d\equiv 1$ implies $y\equiv \pm1$ for $y=x^{(p-1)/d}$.

Each value $y=x^{(p-1)/d}$ solve $y^d\equiv1\pmod p$ (use Fermat's Little Theorem). By Lagrange, there are $\le d$ solutions of this modulo $p$.

If there were fewer than $d$ distinct values of $x^{(p-1)/d}$ modulo $p$, then one of them would come from more that $(p-1)/d$ values of $x$, that is there's some $a$ with $x^{(p-1)/d}\equiv a\pmod p$ having more than $(p-1)/d$ solutions modulo $p$....