Wednesday 23 September 2015

modular arithmetic - General solution for $x^2 equiv x bmod p$




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.


Answer



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


No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...