# 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.

• I wasn't able to understand. Could you explain in more simpler terms? I'm not acquainted with congruences and the Chinese remainder theorem. Mar 29, 2017 at 2:11
• It's not true that a quadratic equation has exactly two solutions mod any prime power...there could be less than two solutions (e.g. $x^2=2$ mod $4$) or more than two solutions (e.g. $x^2=0$ mod $9$). You need to use something more specific about $a^2=a$. Mar 29, 2017 at 2:11
• @EricWofsey Thank you; hopefully I fixed it in a way that won't embarrass my undergrad-knowing-number-theory past self. Of course, now the argument is even more technical. Mar 29, 2017 at 2:19
• Instead of using Hensel's lemma, you can say that $a$ and $a-1$ are relatively prime, so only one can contribute powers of $p$. Mar 29, 2017 at 2:25

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$.

• Well, I feel really stupid now. :) Mar 29, 2017 at 2:25

$$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,

1. $$a=625x$$ and $$a-1=16y$$, $$625x=16y+1$$
2. $$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$$.