# Find the number of solutions of $x^2=x\mod m$ for any integer $m$

Find the number of solutions of $x^2=x\mod m$ for any integer $m$.

I was thinking about bringing the $x$ over to the other side and somehow apply chinese remainder thm.

-

$$x^2 - x = x(x-1) \equiv 0 \mod m$$ Now, if $m=p^an$, where $p$ is a prime and $p\not| n$, then you can write that $$x(x-1) \equiv 0 \mod p^a$$ Determine under which conditions you get a solution to this, and repeat for each prime factor of $m$. Then consider the total number of solutions based on the same reasoning as the Chinese Remainder Theorem (no need to actually use the theorem, unless you're finding all of the solutions).