Number of solutions for $x^2 \equiv x \pmod m$ What is the number of solutions of $x^2 \equiv x \pmod m$ for any positive integer $m$?
 A: The problem is to count the roots of $x^2 - x \equiv 0 \pmod m$.
Exploring the problem for specific numbers of $m$ first, we see it can have:


*

*$2$ roots mod $2$: 0,1

*$4$ roots mod $6 = 2\cdot 3$: 0,1,3,4

*$8$ roots mod $30 = 2\cdot 3\cdot 5$: 0,1,6,10,15,16,21,25,30

*$16$ roots mod $210 = 2\cdot 3\cdot 5\cdot 7$


A good guess is it has $2^r$ roots, for some $r$ depending on $m$.
With some more exploring you can notice that:


*

*There is $2$ roots modulo a prime power.

*There is $2^r$ roots, where $r$ is the number of prime factors of $m$.



A degree $d$ polynomial can only have at most $d$ roots mod some prime $p$. It can have more roots than its degree modulo prime powers though. We need to prove that this special polynomial has exactly $2$ roots mod each prime power $p^k$.
Lemma $x^2-x \equiv 0$ has $2$ roots $\pmod {p^k}$.
proof: Clearly $x=0$ and $x=1$ are roots, as you have pointed out. We just need to show now that if $z$ is a root then $z=0$ or $z=1$. To prove that we can split into two cases: When $z|p^k$ and when $z$ is coprime to $p^k$. The coprime case is easy because $z$ is zero or invertible.
For the case $z|p^k$: Put $z = p^h$ (with $h < k$) and consider $$p^{2h} - p^h \equiv 0 \pmod {p^k}.$$ this is impossible of $2h \le k$ so suppose $2h > k$, we have $k < 2h < 2k$ and $p^{2h-k} \equiv p^k$ but this implies $2h-k = k$, so $2h = 2k$, but this contradicts $h < k$.
Secondly we can use the chinese remainder theorem to put together the $2$ roots mod each prime power of $m$ to get $2^r$ roots mod $m$.
Lemma If $a,b$ are coprime then if $P(x)$ has $m$ roots mod $a$ and $n$ roots mod $b$ then it has $mn$ roots mod $ab$.
proof: Label the roots mod $a$ as $\{r_i\}$ and the roots mod $b$ as $\{s_j\}$ then the roots mod $ab$ are $\{(r_i, s_j) \}$ of which there are $|\{r_i\}|\cdot|\{s_j\}| = nm$.

Putting these two lemmas together lets you conclude: There are $2^r$ roots, where $r$ is the number of prime factors of $m$.
A: As I said in my comment above, we have
$$
x^2 \equiv x \pmod m\\
x^2 - x \equiv 0 \pmod m\\
x(x-1) \equiv 0 \pmod m
$$
What if $m$ was a prime $p$, how many solutions would the equation have? What if $m$ was the power $p^n$ of some prime? Here it pays off to think about divisibility and what being a prime means (hint: there are two solutions either way).
Now, for an $m$ that is not the power of a prime, then it can still be written as a product of such:
$$
m = p_1^{n_1}\cdots p_k^{n_k}
$$
At this point, you have either heard about the Chinese remainder theorem or you haven't. If you have, you should know what to do at this point, especially since I just told you about it. Assuming that $p_i \neq p_j$ when $i \neq j$, you get $k$ different congruence relations, each with $2$ solutions, which means that the total number of solutions to the original problem is...?
If you haven't heard about it, then I suggest reading up on it. It is a very important result in number theory and you shouldn't be without it. You could start here, or use google, or if you have a favourite textbook, it's probably in there as well.
A: So we get $x(x-1) \equiv \mod m$ so $m|x(x-1)$.  If $m$ is prime then either $m|x$ and $x \equiv 0 \mod m$ or $m|x -1$ and $x \equiv 1 \mod m$.
But what if $m$ is not prime.  If $m = \prod p_i^{k_i}$ then as $x$ and $x-1$ are relatively prime (they have only a difference of 1) then each $p_i^{k_i}|x$ or divides $x -1$.
In other words we need to find $x \equiv 0 \mod k$ and $x \equiv 1 \mod (j)$ where $m = j*k$ and $\gcd(j,k) = 1$ (Note if $m = \prod p_i^{k_i}$ there will by $2^i$ such sets of equations).  According to the chinese remainder theorem there will be one solution to each set of problems. (So $2^i$ solutions total).
Example 1
Solve $x^2 = x \mod 12 \iff x(x-1) \equiv 0 \mod m$.  $12 = 3 \times 4$ so there will be the following solutions:
A) $x \equiv 0 \mod 12$ and $x \equiv 1 \mod 1$ which has one solution. via CRT.
B) $x \equiv 0 \mod 1$ and $x \equiv 1 \mod 12$ which has one solution.via CRT.
C) $x \equiv 0 \mod 3$ and $x \equiv 1 \mod 4$ which has one solution.via CRT.
D) $x \equiv 0 \mod 4$ and $x \equiv 1 \mod 3$ which has one solution. via CRT.
The solution to A) is $x= 0$, B) is $x =1$, C) $x = 9$ D)$ x = 4$
Example 2
Solve $\ x^2 = x \mod 360$.
$360 \equiv 8 \times 9 \times 5$ so there will be 8 solutions:
$ (x \equiv 0 \mod 360) \rightarrow x = 0$
$ (x \equiv 1 \mod 360) \rightarrow x = 1$
$ (x \equiv 0 \mod 8) \  AND \ \  (x \equiv 1\mod 45) \rightarrow x = 136$
$ (x \equiv 0 \mod 45) \  AND \ \  (x \equiv 1 \mod 8) \rightarrow x = 225$
$ (x \equiv 0 \mod 9) \  AND \ \  (x \equiv 1 \mod 40) \rightarrow x = 81$
$ (x \equiv 0 \mod 40) \  AND \ \  (x \equiv 1 \mod 9) \rightarrow x = 280$
$ (x \equiv 0 \mod 5) \  AND \ \  (x \equiv 1 \mod 72) \rightarrow x = 145$
$ (x \equiv 0 \mod 72) \  AND \ \  (x \equiv 1 \mod 5) \rightarrow x = 216$.
Which would have been practically impossible by trial and error.
