Let $n$, $k$ be positive integers such that $n$ is not divisible by $3$ and $k\ge n$. Prove that there exists a positive integer m which is divisible by $n$ and the sum of its digits in the decimal representation is $k$.
Problem
Source:
Tags: modular arithmetic, number theory, relatively prime
27.09.2007 02:11
Let $ n = a*b$ where $ b$ is not divisible by $ 2$ or $ 5$. Then, $ a$ is of form $ 2^{k}*5^{l}$ so the number $ S = 10^{k+l}$ will be divisible by $ a$ as $ 10^{k+l}= 2^{k+l}5^{k+l}$ Now, because $ b$ is not divisible by $ 2$ or $ 5$, then $ \gcd(10,b) = 1$ hence if $ r$ is the number of integers from $ 1$ to $ b$ that are relatively prime to $ b$, then by Euler's Theorem, $ 10^{r}\equiv 1\pmod b$ so $ 10^{kr}\equiv1\pmod b$, and also $ 10^{kr+1}\equiv 10\pmod b$. Then, the number $ T$ of form $ \sum_{i = 1}^{x}10^{ir}+\sum_{j = 1}^{y}10^{jr+1}\equiv x+10y\pmod b$ and the sum of its digits is $ x+y$. Then, if we can find positive integers $ x,y$ such that $ x+y = k$ and $ b|(x+10y)$ we will find the number $ T$ with sum of digits $ k$ and divisible by $ n$. Now, $ b|(x+10y)\Leftrightarrow b|(9y+(x+y))\Leftrightarrow b|(9y+k)\Leftrightarrow 9y\equiv-k\pmod b$. But $ n$ is not divisible by $ 3$ so $ \gcd(b,9) = 1$ so there exists a positive integer $ z < b\leq k$ such that $ 9z\equiv-k\pmod b$. Then, if we take $ y = z$ and $ x = k-z$ then the integer $ T =\sum_{i = 1}^{x}10^{ir}+\sum_{j = 1}^{y}10^{jr+1}$ is divisible by $ b$ and has the sum of digits $ k$. Then, $ TS = T*10^{k+l}$ has the sum of digits $ k$ and is divisible by $ 10^{k+l}b$ so it is divisible by $ n$, and the result follows.