Closed Form for Solutions of $x^2 \equiv x \text{ mod } 10^n$.

Question

Is there some closed expression to generate $n$-digit numbers $x$ such that the last $n$ digits of $x^2$ are equal to x?

Answer 1

You ask for $x \in \{10^{n-1},10^{n-1}+1,\ldots,10^n-1\}$ such that $10^n \mid x^2-x=x(x-1)$. Note that $\gcd(x,x-1)=1$. Hence we have only four possibilities: $$ x\equiv 0\bmod{2^n} \,\,\,\,\text{ and }\,\,\,\,x\equiv 1\bmod{5^n} $$ or $$ x\equiv 1\bmod{2^n} \,\,\,\,\text{ and }\,\,\,\,x\equiv 0\bmod{5^n}. $$ or $x\equiv 0\bmod{10^n}$ or $x\equiv 1\bmod{10^n}$ (the last ones lead to $0,1$ trivially).

About the first two cases, by the Chinese remainder theorem, there exists exactly one solution modulo $10^n$ for each of them, let's say $a$ and $b$. Hence, there are at most two $n$-digits solutions (we don't know in principle how many digits $a$ and $b$ have).

Answer 2

First, we rewrite to $x(x-1)\equiv 0$. Now we use the Chinese remainder theorem to get $$ \cases{x(x-1)\equiv 0\pmod{5^n}\\x(x-1)\equiv0 \pmod{2^n}} $$ Since $x$ and $x-1$ are coprime (and especially don't share any factors of $2$ or $5$), each of the two above equations have two solutions, so together that makes four solutions.

• $x\equiv 0$ in both cases gives $x = k\cdot 10^n$, which is boring
• $x-1\equiv 0$ in both cases gives $x = k\cdot 10^n + 1$, which is only slightly less boring.

The two remaining solutions are more interesting. One is that $x$ is divisible by $2^n$ and $x-1$ is divisible by $5^n$. For $n = 2$, for instance, this makes $x = k\cdot 100 + 76$. The other one is that $x$ is divisible by $5^n$ and $x-1$ is divisible by $2^n$, which for $n = 2$ is $x = k\cdot 100 + 25$.

I don't know whether these two solutions have a closed form for general $n$, or whether there are any other good, constructive ways to find them, except that if you know what the answer is for some $n$, then the answer for $n+1$ must have the same final $n$ digits. In other words, you can do trial and error one digit at a time, which is a lot faster than trying all multiples of $5^n$ and all multiples of $2^n$ and see which ones work.