How do I show that $x^p \equiv x\pmod p$ has precisely $p$ solutions?

I can use Lagrange's theorem and Fermat's little theorem.

  • $\begingroup$ Is $p{}$ prime? $\endgroup$ – punctured dusk Apr 15 '15 at 9:40
  • $\begingroup$ sorry, yes p is prime $\endgroup$ – cf12418 Apr 15 '15 at 9:43
  • $\begingroup$ which aspect is confusing to you? $\endgroup$ – JonMark Perry Apr 15 '15 at 9:45
  • $\begingroup$ Lagranges theorem shows that x^p-x=0 (mod p) has at most p solutions, I cant figure out the next step to show it has precisely p solutions, using these two theorems, $\endgroup$ – cf12418 Apr 15 '15 at 9:46
  • $\begingroup$ there are p distinct numbers between 0 and p-1, each one is a solution $\endgroup$ – JonMark Perry Apr 15 '15 at 9:55

The formula you expressed holds always when p is a prime.(Fermat's Little Theorem). Lagrange's theorem is useful usually when dealing with the order of subgroups. How familiar are you with modular arithmetic? One way of describing "mod p" is that there are p possible remainders when dividing something mod p. For example, when dividing by 3, you could end up with a remainder of 0,1, or 2. Notice that is three possible "solutions", for mod 3. So in mod p, there will be p possible solutions. Hope that helps...


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.