[Math] Find smallest number which is divisible to $N$ and its digits sums to $N$

combinatoricsnumber theory

Someone asked this question in SO:

$1\le N\le 1000$

How to find the minimal positive number, that is divisible by N, and
its digit sum should be equal to N.

I'm wondering if for every integer $N$, can we always find a positive number $q$ such that, it is dividable by $N$ and the sum of its digits is $N$?

Best Answer

For every $N$ there is a number $X$ such that $N$ divides $X$ and the sum of digits of $X$ equals $N$.

Proof: Write $N = RM$ where $M$ is coprime to $10$ and $R$ contains only the prime factors $2$ and $5$. Then, by Euler's theorem, $10^{\varphi(M)} \equiv 1 \pmod M$. Consider $X' := \sum_{i=1}^{N} 10^{i\varphi(M)}$. It is a sum of $N$ numbers each of which is congruent to $1$ modulo $M$, so $X' \equiv N\cdot 1 \equiv 0 \pmod M$. Furthermore, the decimal representation of $X'$ contains exactly $N$ ones, all other digits are $0$, so the sum of digits of $X'$ is $N$. Multiply $X'$ by a high power of ten to get a multiple of $R$, call the result $X$. Then $X$ is divisible by $M$ and $R$, hence by $N$, and it has the same digit sum as $X'$ which is $N$.

Related Question