A natural number $a$ has four digits and $a^2$ ends with the same four digits as that of $a$. Find the value of $a$? 
A natural number $a$ has four digits and $a^2$ ends with the same four digits as that of $a$. Find the value of $a$?

This question appeared in a math contest. I tried for a while and came up with this condition: $10^4|(a-1)a$. But I'm not able to take it further. It is clear that out of the two ($a-1$ and $a$) the one which is odd will contain no powers of 2 and hence the other one would contain the $2^4$. But there are to many possibilities for one to see by trial and error. 

The equation $a^2 = a$ has exactly two solutions ($0$ and $1$) modulo any prime power, because:


*

*Mod $p$, it has only two roots $0$ and $1$, because it's quadratic, and $\mathbb F_p$ is a field;

*By Hensel's lemma, since the derivative of $a^2-a$ is $2a-1$ and is nonzero when $a=0$ or $a=1$ we can lift those solutions.


So we know that:


*

*$a^2 \equiv a \pmod{2^4}$ only if $a \equiv 0 \pmod{2^4}$ or $a \equiv 1 \pmod{2^4}$,

*$a^2 \equiv a \pmod{5^4}$ only if $a \equiv 0 \pmod{5^4}$ or $a \equiv 1 \pmod{5^4}$.


However, modulo $10^4$, we have more freedom, because we can glue these solutions any way we like by the Chinese remainder theorem. Our options are
\begin{align}
   a\equiv 0 \pmod{2^4}\text{ and }a\equiv 0 \pmod{5^4} &\implies a \equiv 0 \pmod{10^4} \\
   a\equiv 0 \pmod{2^4}\text{ and }a\equiv 1 \pmod{5^4} &\implies a \equiv 9376 \pmod{10^4} \\
   a\equiv 1 \pmod{2^4}\text{ and }a\equiv 0 \pmod{5^4} &\implies a \equiv 625 \pmod{10^4} \\
   a\equiv 1 \pmod{2^4}\text{ and }a\equiv 1 \pmod{5^4} &\implies a \equiv 1 \pmod{10^4}
\end{align}
(To compute the two middle values, take $2^4$ times the inverse of $2^4$ modulo $5^4$, and $5^4$ times the inverse of $5^4$ modulo $2^4$, respectively.)
So in general (modulo $10^n$ for other $n$) there's two solutions other than $0$ and $1$, but because $625$ is not actually a four-digit number, the correct one here is just $9376$.

I guess a simpler way to get to the Chinese remainder step is to observe that if $10^4 \mid a(a-1)$, one of $a$ and $a-1$ is odd, and one of $a$ and $a-1$ is not divisible by $5$, so we must have $2^4 \mid a$ and $5^4 \mid a-1$ or the reverse to get a nontrivial solution. But I don't see a way to avoid the Chinese remainder theorem.
