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.

  • $\begingroup$ 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$.) $\endgroup$ – quid Jul 15 '17 at 10:33

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$....


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.