Exercise 2.3.45* (Number of solutions of $x^2 \equiv x \pmod m$)

Write $N(m)$ the number of solutions of $x^2\equiv x(modm)$. We first determine $N(m)$ if $m=p^{\alpha }$ is a power of a prime $p$ ( $\alpha \ge 1$).

Then

Since $x$ and $x-1$ are relatively prime,

because $p^u\mid x$, with $u>0$ and $p^v\mid x-1$, with $v>0$ ( $u+v=\alpha$) imply $p\mid x\wedge (x-1)=1$: this is impossible.

Therefore

This gives $N(p^{\alpha })=2.$

Now let $m$ be an integer greater than $1$, and $m=p_1^{a_1}\cdots p_k^{a_k}$ its decomposition in prime factors. Then, using (1),

So $x^2\equiv x(modm)$ if and only if $x$ is a simultaneous solution of one of the $2^k$ systems of congruences

where $({\eta }_1,{\eta }_2,\dots ,{\eta }_k)\in {\{0,1\}}^k$. The Chinese Remainder Theorem shows that these systems have exactly one solution modulo $m=p_1^{a_1}\cdots p_k^{a_k}$. Since there are $2^k$ such system, $N(m)=2^k$ where $k$ is the number of prime divisors of $m$.

The number of solutions of $x^2\equiv x(modm)$ is $2^k$, where $k$ is the number of prime divisors of $m$.

I checked this result with a Python program, up to $m=250$. The maximum is for $m=210=2\cdot 3\cdot 5\cdot 7$, for which $x^2\equiv x(mod210)$ has $16$ solutions.