1
$\begingroup$

I want to find a general solution for $x^2 \equiv x \bmod p$, where $p$ is a prime.

It is easy to see that if $x \equiv 0 \bmod p$ or $x \equiv 1 \bmod p$ , the equation holds.

I got these solutions, but I was not able to figure out any other solutions. which, intuitively, would not seem necessarily wrong.

Is it true that there is never any other solution? and if so how is this provable?

Thank you,

V.

$\endgroup$
  • 2
    $\begingroup$ If $x \neq 0$, then you can multiply both sides of the equation by $x^{-1}$ since $p$ is prime. $\endgroup$ – Joe Johnson 126 Jun 27 '17 at 10:53
  • 2
    $\begingroup$ Hint: What does it mean for $x(x-1)$ to be divisible by a prime? $\endgroup$ – SystematicDisintegration Jun 27 '17 at 10:56
  • 1
    $\begingroup$ A quadratic equation over a field (such as $\mathbf Z/p\mathbf Z$) has at most two roots. $\endgroup$ – Bernard Jun 27 '17 at 10:58
2
$\begingroup$

Following the comment of @SystematicDisintegration if $x(x-1)$ is divisible by a prime , then one of them must be a multiple of that prime since prime has no other divisors other than $1$ and prime itself

So either $x=pk$, or $x-1=pk$ for some intiger $k$

The point of the question is there exist no other solution since $x(x-1)$ is not factorizable in any other form in linear pair of intigers

So by considering two mentioned above , we can conclude $x\equiv 0,1(mod ~p) $ are only solutions

$\endgroup$

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.