9
$\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

$\endgroup$

2 Answers 2

Reset to default
8
$\begingroup$

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.

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

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

$\endgroup$
1
  • $\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.
    Commented Aug 15, 2012 at 20:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .