Can anyone help me with such task?
I'm preparing for my exam session and got stuck with that:

Prove, that for every natural number $n$, there exists another natural number $S$,
which is divisible by $n$ and its sum of digits (in decimal system) equals to $n$.

I presume that Chinese remainder theorem would be helpful here,
yet I don't know how to use it properly. Any ideas?

Thanks for your help


Robert Israel has given a hint (look at a sum of $n$ distinct powers of $10$) that quickly leads to a solution of the problem. We give a little added detail.

Let $n=ab$, where $a$ is divisible by no prime other than possibly $2$ and/or $5$, and $b$ is relatively prime to $10$.

By Euler's Theorem, we have $$10^{\varphi(b)}\equiv 1\pmod{b}.$$ Let
$$S_b=10^{\varphi(b)}+10^{2\varphi(b)}+10^{3\varphi(b)}+\cdots +10^{n\varphi(b)}.$$ Then the decimal expansion of $S_b$ consists only of $0$'s and $1$'s, and the digit sum of $S_b$ is $n$.

We have $10^{k\varphi(b)}\equiv 1\pmod b$, so $S_b\equiv n\equiv 0 \pmod{b}$.

It is possible that $S_b$ is not divisible by $a$. Let $S$ be $S_b$ multiplied by a sufficiently high power of $10$ to ensure divisibility by $a$. The digit sum does not change.

  • $\begingroup$ Thanks a lot! I got stuck with Chinese remainder theorem instead of trying to apply the most basic one - Euler's... $\endgroup$ – sr. Aug 16 '12 at 9:39

Hint: Try a sum of $n$ different powers of $10$.

  • $\begingroup$ That was my first thought as well, I spent more than an hour thinking how to apply Chinese remainder theorem to that - and failed. Could you give me anything more? Am I right about this Chinese theorem at least? $\endgroup$ – sr. Aug 15 '12 at 20:36

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.