2. Find the smallest natural number which is a multiple of 2009 and whose sum of (decimal) digits equals 2009.

(Miloš Milosavljević)
2. Since $2009=223 \cdot 9+2$, the required number has at least 224 digits. We shall consider the possible 224 -digit numbers $x=\overline{c_{223} c_{222} \ldots c_{1} c_{0}}$. Clearly $c_{223} \geq 2$. Also, if $c_{223}=2$ then $c_{222}=\cdots=c_{0}=9$, so $x=3 \cdot 10^{223}-1 \equiv 3 \cdot 10-1 \equiv 1$ $(\bmod 7)$ is not divisible by $2009=7^{2} \cdot 41$.

Suppose that $c_{223}=3$. Then exactly one digit $c_{i}, i=0, \ldots, 222$ is equal to 8 , while the others are equal to 9 , so

$$
x=3 \underbrace{99 \ldots 9}_{222-i} 8 \underbrace{99 \ldots 9}_{i}=4 \cdot 10^{223}-10^{i}-1 .
$$

The order of 10 modulo 41 divides 40 , and an easy inspection shows that $10^{5} \equiv 1(\bmod 41)$, so $10^{i}$ is always congruent to one of $1,10^{1}, 10^{2}, 10^{3}, 10^{4}$, i.e. to $1,10,18,16,37(\bmod 41)$. Therefore $x \equiv 4 \cdot 10^{3}-10^{i}-1 \equiv 22-10^{i}(\bmod 41)$ is never divisible by 41 .

Now suppose that $c_{223}=4$. Among $c_{222}, \ldots, c_{0}$, either two are equal to 8 , or one is equal to 7 , while the others are 9 . Thus $x=5 \cdot 10^{223}-10^{i}-10^{j}-1 \equiv 38-\left(10^{i}+10^{j}\right)$ $(\bmod 41)$, where $i$ and $j$ may be equal. It is easy to see from above that $10^{i}+10^{j} \equiv$
$38(\bmod 41)$ if and only if one of $(i, j) \equiv(0,4)$ or $(4,0)(\bmod 5)$. In particular, $i \neq j$ and $i, j \leq 220$.

Next we assume that $j=220$ and $i \equiv 4(\bmod 5)$. Now we only need to choose $i$, if possible, so that $7^{2} \mid x$. By Euler's theorem, $1 \equiv 10^{\varphi(49)}=10^{42}(\bmod 49)$, and since $10^{k} \equiv 10,2,20,8,31,30,48$ for $k=1,2,3,6,7,14,21$ respectively, we deduce that the order of 10 modulo 49 equals 42 . We have $x=5 \cdot 10^{223}-10^{220}-10^{i}-1 \equiv$ $5 \cdot 10^{13}-10^{10}-10^{i}-1 \equiv 31-10^{i}(\bmod 49)$, so $49 \mid x$ if and only if $10^{i} \equiv 31 \equiv 10^{7}$ $(\bmod 49)$, i.e. $i \equiv 7(\bmod 42)$. The last condition together with $i \equiv 4(\bmod 5)$ yields $i \equiv 49(\bmod 210)$, so the only possibility is $i=49$. It follows that the required number is

$$
4998 \underbrace{9 \ldots 99}_{170} 8 \underbrace{99 \ldots 9}_{49} .
$$