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.

  • $\begingroup$ Did you try proof by contradiction? $\endgroup$ – Arjun Dhiman Jul 14 '15 at 12:24
  • $\begingroup$ just for fun, here are the first k for every number unto 50: link $\endgroup$ – john Jul 14 '15 at 12:43
  • $\begingroup$ @zero I tried to find something but I can't see hoe to reach a contradiction. $\endgroup$ – Jorge Fernández Hidalgo Jul 14 '15 at 13:29
  • $\begingroup$ See also OEIS A$180011$. $\endgroup$ – Lucian Jul 14 '15 at 13:36
  • $\begingroup$ 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$. $\endgroup$ – 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.

  • $\begingroup$ 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. $\endgroup$ – 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.