# 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.

• Did you try proof by contradiction? – Arjun Dhiman Jul 14 '15 at 12:24
• just for fun, here are the first k for every number unto 50: link – john Jul 14 '15 at 12:43
• @zero I tried to find something but I can't see hoe to reach a contradiction. – Jorge Fernández Hidalgo Jul 14 '15 at 13:29
• See also OEIS A$180011$. – Lucian Jul 14 '15 at 13:36
• I think that's different Lucian. In your source we want $kn$ to have the same digit sum as $n$. In the question we want the sum of digits of $kn$ to be $n$. – Jorge Fernández Hidalgo Jul 14 '15 at 13:40

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.

• I see that you came to a similar conclusion in your answer to your own question. There are a lot of open questions in this field. For instance it has not yet been determined if there are an infinite number of integers that are Niven numbers in both base 2 and base 3. – Joel Jul 15 '15 at 13:59

I got it, I was trying to find a multiple of $n$ that has sum of digits $n$. What we have to do is find a number that has sum of digits $n$ that is a multiple of $n$.

In other words, which numbers have sum of digits $n$? A particular kind of such numbers are the ones that have $n$ ones, and no other digits.

We can build such a number that is multiple of $n$. Write $n$ as $2^a5^bj$ with $(j,10)=1$.

Then $10^{k\varphi(j)}$ is congruent to $1\bmod j$ via Euler, and if $k$ is large enough then $10^{k\varphi(j)}$ is a multiple of $2^a5^b$.

Such just take $n$ numbers of the aforementioned form, add them and you get a number with sum of digits $n$ that is congruent to $n=0\bmod j$ and is a multiple of $2^a5^b$. In other words a multiple of $n$ with sum of digits $n$, as desired.

• "Such just take n numbers of the aforementioned form, add them" can you give an example? – Rehaan Ahmad May 6 '17 at 19:03