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. 
 A: 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.
A: In addition to only one of $a$ and $a-1$ being even, you can also say that only one of them is divisible by $5$.  It follows that one of them must be divisible by $5^4$, and the other must be divisible by $2^4$ (you can't have one of them divisible by both $2^4$ and $5^4$ because then $a$ could not have four digits).  It is not too bad to check all possible 4-digit multiples of $5^4=625$ (and in fact, you only need to check such multiples that are odd).  For each such multiple $n$, you want to check whether $n\pm 1$ is divisible by $2^4$ (if $n+1$ is, then $n+1$ can be $a$, and if $n-1$ is, then $n$ can be $a$).
You can further greatly reduce the amount of work you need to do with a little modular arithmetic.  Note that $625\equiv 1\pmod{16}$, so $625k\equiv k\pmod{16}$ for any integer $k$.  So if you want $n=625k$ to be either $1$ more or $1$ less than a multiple of $16$, then $k$ needs to be $\pm 1$ mod $16$.  The values of $k$ that give 4-digit numbers are $2\leq k\leq 15$, and so the only one that works is $k=15$.  This gives $n=625\cdot 15=9375$, which is $1$ less than a multiple of $16$, so the value of $a$ you want is $n+1=9376$.
A: $a$ and $a^2$ have the same last four digits. So, $a^2-a$ is divisible by $10,000$.
$$a(a-1)=10,000k=16*625k----(Eq.1)$$
Now, $a$ and $a^2$ have same last digit only if a ends with $0, 1, 5$ or $6$.
$a$ can't end with $0$ as squaring it will give double the zeroes and $a^2$ won't have same last four digits.
For example, if $a$ ends with $10$, $a^2$ ends with $100$. Thus, this is not possible.
Say $a$ ends with 1, $$a=10x+1$$ $$a^2=10x^2+20x+1$$
Thus, they will differ in second last digit. (From the equation, ten's digit for $a$ is $x$ and for $a^2$ is $2x$.)
So, only possible solutions are if $a$ ends with $5$ or $6$.
From Eq. 1 we get two cases,

*

*$a=625x$ and $a-1=16y$, $625x=16y+1$

*$a=16y$ and $a-1=16y$, $625x=16y+1$
So, $625$ is divisible by $16$ with remainder $1$ or $-1$.
Now, $$625\equiv1(\mod16)$$ $$625x\equiv x(\mod16)$$
Hence, solution is $x=15$, which follows then 2nd Case.
$$625*15=9375=16*586-1$$
$\therefore a=16y=16*586=9376$.
