IMC 2006 · Day 1 · P2

Let $S_k = \left\{ 0 < x < 10^k \mid x^2 - x \text{ is divisible by } 10^k \right\}$ and $s(k) = |S_k|$, $k \ge 1$. Let $x = a_{k+1} a_k \dots a_1$ be the decimal writing of an integer $x \in S_{k+1}$, $k \ge 1$. Then obviously $y = a_k \dots a_1 \in S_k$. Now, let $y = a_k \dots a_1 \in S_k$ be fixed. Considering $a_{k+1}$ as a variable digit, we have $x^2 - x = \left( a_{k+1} 10^k + y \right)^2 - \left( a_{k+1} 10^k + y \right) = (y^2 - y) + a_{k+1} 10^k (2y - 1) + a_{k+1}^2 10^{2k}$. Since $y^2 - y = 10^k z$ for an iteger $z$, it follows that $x^2 - x$ is divisible by $10^{k+1}$ if and only if $z + a_{k+1} (2y - 1) \equiv 0 \pmod{10}$. Since $y \equiv 3 \pmod{10}$ is obviously impossible, the congruence has exactly one solution. Hence we obtain a one-to-one correspondence between the sets $S_{k+1}$ and $S_k$ for every $k \ge 1$. Therefore $s(2006) = s(1) = 3$, because $S_1 = \{1, 5, 6\}$.

Since $x^2 - x = x(x-1)$ and the numbers $x$ and $x-1$ are relatively prime, one of them must be divisible by $2^{2006}$ and one of them (may be the same) must be divisible by $5^{2006}$. Therefore, $x$ must satisfy the following two conditions: $$x \equiv 0 \text{ or } 1 \pmod{2^{2006}};$$ $$x \equiv 0 \text{ or } 1 \pmod{5^{2006}}.$$ Altogether we have 4 cases. The Chinese remainder theorem yields that in each case there is a unique solution among the numbers $0, 1, \dots, 10^{2006} - 1$. These four numbers are different because each two gives different residues modulo $2^{2006}$ or $5^{2006}$. Moreover, one of the numbers is 0 which is not allowed.

Therefore there exist 3 solutions.