Chinese remainder theorem?

Question

In the 2014 AIME 1, number 8 says:

The positive integers $N$ and $N^2$ both end in the same sequence of four digits $abcd$ when written in base 10, where digit $a$ is not zero. Find the three-digit number $abc$.

I solved this problem using modular arithmetic and a little bit of logic (mainly the realization that if $N^2 - N$ is congruent to $0 \pmod{10000}$ then either $N$ is divisible by $2^4$ and $N-1$ is divisible by $5^4$ or vice versa.)

I saw a solution that used the Chinese remainder theorem, something I've never seen before. How does this theorem work, and how would it apply to this problem?

Answer 1

The last $4$ digits of $n$ are $\,n\ {\rm mod}\ 10000,\,$ so if they are the same for both $\,n\,$ and $\,n^2\,$ then $\,10000\mid n^2-n,\,$ so $\,10^4 = 2^4 5^4\mid n(n\!-\!1).\,$ By $\,n,\,n\!-\!1\,$ coprime, either $\,2^4\mid n\,$ or $\,2^4\mid n\!-\!1,\,$ and $\,5^4\mid n\,$ or $\,5^4\mid n\!-\!1,\,$ leading to the following four possible cases

$$\begin{eqnarray} 2^4 5^4&&\mid n\\ 2^4 5^4&&\mid n-1\\ 2^4\mid n,\ 5^4&&\mid n-1\\ 5^4\mid n,\ 2^4&&\mid n-1\end{eqnarray}$$

This yields the solutions $\ n\equiv 0,1, 625,9376\pmod{10000}\,$ by the Chinese Remainder Theorem. For example, in case four $\,5^4\mid n,\,$ so $\,n=5^4k,\,$ so $\,{\rm mod}\,\ 2^4\!:\,\ 1 \equiv n = 5^4 k\equiv (-9)^2 k\equiv k,\,$ hence $\,k = 1+2^4j,\,$ hence $\, n = 5^4k = 5^4(1+2^4j) = 5^4+ 10^4j\equiv 625\pmod{10000}$

Answer 2

You could start with Wikipedia A web search will turn up many references. It looks like you were applying it without knowing it. Here you are looking to solve $N \equiv 0 \pmod {2^4}, N\equiv -1 \pmod {5^4}$ or the other way around. Because $2^4,5^4$ are relatively prime, CRT says there will be exactly one solution $\pmod {2^4\cdot 5^4}$ Note that without $a \neq 0$ the strings $0000$ and $0001$ also solve the problem.