For how many numbers $X^2 \equiv X \mod 10^n$?

Question

I've been looking through this post:

Square of four digit number $a$

And wanted to see if there's a way to generalize the idea, in order to answer the following question:

For how many numbers $X^2 \equiv X \mod 10^n$?

Also, is $9376$ the only four digit number such that $9376^2 \equiv 9376 \mod 10^4$

Thanks

Answer 1

The number of distinct numbers modulo $10^n$ solving $$x^2\equiv x\pmod{10^n}\tag1$$ is four.

To see this by the Chinese remainder theorem $x$ solves (1) iff both $$x^2\equiv x\pmod{2^n}\tag2$$ and $$x^2\equiv x\pmod{5^n}\tag3.$$ These congruences state that $p^n\mid x(x-1)$ for $p=2$ or $5$. As $x$ and $x-1$ have no common factor then $p^n\mid x$ or $p^n \mid(x-1)$. So the solutions are $x\equiv 0$ or $1\pmod{p^n}$.

By the Chinese remainder theorem again these can be assembled into four solutions modulo $10^n$. Two are obvious: $0$ and $1$. The other two are $x_n$ and $1-x_n$ where $x_n\equiv 0\pmod{2^n}$ and $x_n\equiv 1\pmod{5^n}$. These can be found by applying the extended Euclidean algorithm to $2^n$ and $5^n$.

For $n=4$ you have $x_4=9376$, as you say, so $1-9376\equiv 625\pmod{10^4}$. So in this case $x_4$ is the only solution between $10^3$ and $10^4-1$ inclusive, that is "with four digits".