For a positive integer $n$, let $f(n)$ denote the number obtained by reversing the digits of $n$ in decimal notation. (So $f(2500)=52, f(1456)=6541$.) Find all positive integers $k$ such that for any multiple $n$ of $k$, $k$ is also a divisor of $f(n)$.
Solution. We will briefly refer to the numbers we are looking for as good. Suppose $k$ is good. Then $k<10^{m}$ holds for some positive integer $m$, so $k$ has a multiple $n$ such that $10^{m} \leq n<2 \cdot 10^{m}$. For this $n$, the last digit of $f(n)$ is 1, meaning $f(n)$ is not divisible by either 2 or 5. Therefore, the number $k$ is coprime with 10. According to the Euler-Fermat theorem, $9k$ is a divisor of $10^{t}-1$, where $t=\varphi(9k)$. Therefore, $k$ is also a divisor of the $t$-digit number $K=\frac{10^{t}-1}{9}$, which consists entirely of 1s. Thus,

$$
k \mid 19 K=20 K-K=\underbrace{22 \ldots 2}_{t} 0-\underbrace{11 \ldots 1}_{t}=2 \underbrace{11 \ldots 1}_{t-2} 09
$$

from which

$$
k \mid f(19 K)=90 \underbrace{11 \ldots 1}_{t-2} 2
$$

follows. From this,

$$
k \mid L=f(19 K)-80 K=90 \underbrace{11 \ldots 1}_{t-2} 2-\underbrace{88 \ldots 8}_{t} 0=1 \underbrace{22 \ldots 2}_{t-3} 32
$$

and then

$$
k \mid 2 K-L=\underbrace{22 \ldots 2}_{t}-1 \underbrace{22 \ldots 2}_{t-3} 32=10^{t-1}-10
$$

follows. Combining everything, we get

$$
k \mid\left(10^{t}-1\right)-10\left(10^{t-1}-10\right)=99
$$

which means the possible values of $k$ are $1,3,9,11$, 33, and 99. Using the divisibility rules for 3, 9, and 11, we can easily verify that all six of these numbers are indeed good.

Remark. In the solution, the Euler-Fermat theorem was only needed to show that $k$ has a multiple consisting entirely of 1s. This, however, can also be obtained by applying the pigeonhole principle. For this, consider the numbers $1,11,111,1111, \ldots$. If we extend this sequence long enough, there will certainly be two numbers that give the same remainder when divided by $k$; if these are the numbers consisting of $a$ and $b$ ones (where $a<b$), then their difference

$$
\underbrace{11 \ldots 1}_{b-a} \underbrace{00 \ldots 0}_{a}=10^{a} \cdot \underbrace{11 \ldots 1}_{b-a}
$$

is divisible by $k$. Since $k$ is coprime with 10, $\underbrace{11 \ldots 1}_{b-a}$ is also divisible by $k$.