Can you please show the proof of

"The solutions to $x^m \equiv 1 \bmod p$ will all be solutions to $x^{mn} \equiv 1 \bmod p$ for any $n$."

  • 2
    $\begingroup$ If $x^m\equiv 1$ mod $p$, then $x^{mn} \equiv 1^n \equiv 1$ mod $p$. $\endgroup$ – TonyK Jul 6 '15 at 9:36
  • $\begingroup$ $$x^{mn}=(x^m)^n$$ See math.stackexchange.com/questions/188657/… $\endgroup$ – lab bhattacharjee Jul 6 '15 at 9:39
  • $\begingroup$ I have asked the question to clarify if $p\nmid(2^a-1)$ that $p\nmid 2^{ab}-1$. Is this correct? $\endgroup$ – Kurtul Jul 6 '15 at 11:33

Hint: Do you know the proof of $$x \equiv a \mod m \implies x^n \equiv a^n \mod m$$

For any integer $n>0$ and given $x,a,m$? If not, try to prove this by induction first.

  • $\begingroup$ $x^n-a^n=(x-a)(x^{n-1}+x^{n-2}a+\cdots+a^{n-1})$ proves it. $\endgroup$ – user26486 Jul 6 '15 at 11:39

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.