Find the smallest natural number which is a multiple of $2009$ and whose sum of (decimal) digits equals $2009$ Proposed by Milos Milosavljevic
Problem
Source:
Tags: number theory
25.07.2016 04:29
Since $2009=9.223+2=41.7^2$ the number has at least $224$ digits. Let $N=\overline{a_{224}a_{223}...a_1}$ it is easy to note that $a_{224}\geq 2$ If $a_{224}=2$ $\Longrightarrow$ $N=299...9=3.10^{223}-1$, since $10^{5}\equiv 1\pmod {41}$ $\Longrightarrow$ we get $ N\equiv 3.10^{223}-1\equiv3.10^3-1\equiv 6\pmod {41}$ $\Longrightarrow$ $41|2009|299...9$ is a contradiction. If $a_{224}=3$ $\Longrightarrow$ $N$ has only one digit $a_i=8$ and the rest are $9$ $\Longrightarrow$ $N=39...89....9=4.10^{223}-10^x-1$. Suppose that $2009|4.10^{223}-10^x-1$ $\Longrightarrow$ $41|4.10^{223}-10^x-1$, since $10^{5}\equiv 1\pmod {41}$ we get $41|63-10^x-1$ $\Longrightarrow$ $10^x\equiv 21\pmod {41}$, but $10^t=\{10,18,16,37,1\}\pmod {41}$ $\Longrightarrow$ is a contradiction. If $a_{224}=4$ $\Longrightarrow$ $N$ has only one digit $a_i=7$ or two digits equal to $a_k=a_j=8$ and the rest are $9$ If $N$ has only one digit $a_i=7$ $\Longrightarrow$ $N=49...79..9=5.10^{223}-2.10^x-1$. Suposse that $41|2009|5.10^{223}-2.10^x-1$, since $10^5\equiv 1\pmod {41}$ we get $41|39-10^x-1$ $\Longrightarrow$ $10^x\equiv 38\pmod {41}$ but $10^t=\{10,18,16,37,1\}\pmod {41}$ $\Longrightarrow$ is a contradiction. If $N$ has two digits $a_k=a_j=8$ $\Longrightarrow$ $N=49...89...89...9=5.10^{223}-10^x-10^y-1$. Suppose that $41|2009|5.10^{223}-10^x-10^y-1$, since $10^5\equiv 1\pmod {41}$ we get $41|39-10^x-10^y-1$ $\Longrightarrow$ $10^x+10^y\equiv 38\pmod {41}$ but $10^t=\{10,18,16,37,1\}\pmod {41}$ $\Longrightarrow$ $(x,y)\equiv (0,4),(4,0)\pmod 5$ $\Longrightarrow$ $x,y\leq 220$ since $N$ is minimun we assume that $x=220$ $\Longrightarrow$ $y=5k+4$ for some $k$. On the other hand $49|N$ $\Longrightarrow$ $49|5.10^{223}-10^{220}-10^{5k+4}-1$, since $10^{42}\equiv 1\pmod {49}$ we get $49|5.10^{13}-10^{10}-10^{5k+4}-1$ $\Longrightarrow$ $49|37-10^{5k+4}$, but $10^7\equiv 31\pmod {49}$ $\Longrightarrow$ $5k+4\equiv 7\pmod{42}$ $\Longrightarrow$ since $N$ is minimun we get $y=49$ hence $N$ minimun is $5.10^{223}-10^{220}-10^{49}-1$.