Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

2 Answers 2

up vote 4 down vote accepted

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.

share|improve this answer
    
Thanks a lot! I got stuck with Chinese remainder theorem instead of trying to apply the most basic one - Euler's... –  sr. Aug 16 '12 at 9:39

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

share|improve this answer
    
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? –  sr. Aug 15 '12 at 20:36

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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