8
$\begingroup$

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

2 Answers 2

6

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.

  • 0
    Thanks a lot! I got stuck with Chinese remainder theorem instead of trying to apply the most basic one - Euler's...2012-08-16
4

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

  • 0
    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?2012-08-15