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?


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


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.