number theory - A positive integer is equal to the sum of digits of a multiple of itself.

Let $n$ be a positive integer, prove there is a positive integer $k$ so that $n$ is equal to the sum of digits of $nk$.

I'm not really sure how I should approach this problem, I tried to do a constructive approach but I got lost.

I tried just proving existence but that didn't work either.

I'm sorry if this doesn't look like a put work into it but I feel like nothing I have done is going to yield any results. So I hope you guys can solve this problem.

Thank you very much in advance, regards.

Answer

There is a simple way to answer this sort of question. And there is a related type of number called Niven numbers.

A Niven number is a number, $N$, for which its sum of digits divides $N$. What you are trying to prove is that every integer is the sum of digits of a Niven number.

Here is how we can go about it. Every number can be written in the form: $$N = b_k 10^k + b_{k-1} 10^{k-1} + \cdots + b_0 10^0$$ for some $k$ and $0 \le b_i \le 9$.

Since $10^i$ can take at most $n$ values modulo $n$, we have $10^{i + j} = 10^i$ for some $j$ and all $i$. In other words the function $f(i) = 10^i$ has period $j$ modulo $n$.

Thus if we consider $N = 10^{nj} + 10^{(n-1)j} + \cdots + 10^{j}$ we have $$N \equiv 10^{nj} + 10^{(n-1)j} + \cdots + 10^{j} \equiv (\underbrace{1+1+\cdots+1}_{n \text{ times}})10^{j} \equiv n10^{j} \equiv 0 \mod n.$$

Ivan Niven introduced Niven numbers as a possible avenue of research accessible to undergraduates. His paper appeared in a journal for undergraduate education. These numbers also go under the name of Harshad numbers, but I believe Niven numbers are more common. The Wiki page for "Harshad" numbers contains many references to papers concerning Niven numbers.