General solution for $x^2 \equiv x \bmod p$

Question

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.

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

score 2 · Accepted Answer · answered Jun 27 '17 at 11:04

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

General solution for $x^2 \equiv x \bmod p$

1 Answers1