4
$\begingroup$

Find the remainder when the number $$1234567891011121314151617\ldots200820092010$$ is divided by $9$. Show your work.


I don't even know where to begin. Is there an underlying trick in finding the remainder of a number after being divided by $9$? Morever, how do we even find the remainder when the number is this large...

This was a challenge problem. Meaning I didn't learn this in class.

$\endgroup$
1
  • 1
    $\begingroup$ Is there an underlying trick? ABSOLUTELY!!! The remainder of the number is the same as the remainder for the sum of its digits which is the same as the remainder for the sum of its digits. Example: the remainder of 53862 is the same as the remainder of 5+3+8+6+2=24 which is 2+4=6. Just add the digits, add those digits, add those etc until you get a single digit. That will be the remainder when you divide by 9. $\endgroup$
    – fleablood
    Oct 15 '16 at 20:48
5
$\begingroup$

Hint : $\sum a_k\times10^k\equiv\sum a_k \pmod {9}$

$\endgroup$
13
  • $\begingroup$ Wait, I'm not very familiar with this Sigma notation. I thought there is supposed to be a "dummy variable" underneath, and the limit on the top. Such as $$\sum_{k=1}^{n}$$ $\endgroup$
    – Frank
    Oct 15 '16 at 19:09
  • 3
    $\begingroup$ @Frank he opted not to use limits because the number is of a difficult to quickly determine number of digits long. He means to say that the remainder of a number when dividing by nine (in base 10) is equal to the remainder of the sum of the digits when dividing by nine. E.g. $381$ has remainder $3$ when dividing by $9$ since $381\mapsto 3+8+1=12\mapsto 1+2=3$ $\endgroup$
    – JMoravitz
    Oct 15 '16 at 19:12
  • $\begingroup$ Without sigma notation : the remainder of a number when divided by $9$ is the remainder of the sum of its digits (in base 10) when divided by $9$. E.g. the remainder of $137$ by $9$ is the remainder of $1+3+7=11$, which is $2$. $\endgroup$
    – Evariste
    Oct 15 '16 at 19:12
  • $\begingroup$ @JMoravitz So the problem simply reduces to finding $1+2+3+\ldots +2010$, then dividing that by $9$? $\endgroup$
    – Frank
    Oct 15 '16 at 19:13
  • 4
    $\begingroup$ @Frank yes. Now, do you notice a pattern for what happens if you add nine consecutive numbers together and divide by nine? Alternatively, you could indeed find the actual number $1+2+\dots+2010$ using a well known trick related to triangle numbers, but I would think that is more difficult of an approach. $\endgroup$
    – JMoravitz
    Oct 15 '16 at 19:14
4
$\begingroup$

The sum of $9$ consecutive integers is divisible by $9$, hence \begin{align*}123456789101112\dots200820092010\bmod 9&=\sum_{n=1}^{2010} n\bmod9=\sum_{n=1}^{223\times 9} n\bmod9+\!\!\!\sum_{n=2008}^{2010}\!\!n\\ &=2008\bmod 9+2009\bmod9+2010\bmod9=\color{red}{6}. \end{align*}

$\endgroup$
2
  • 4
    $\begingroup$ (or just the sum of the first 3 digits : 1+2+3) $\endgroup$
    – Evariste
    Oct 15 '16 at 19:29
  • $\begingroup$ @Evariste: Very cute. I didn't even think of counting numbers backwards! $\endgroup$
    – Bernard
    Oct 15 '16 at 19:36
1
$\begingroup$

Hint: the number $ac=10a+c $ is equal to $ac=10a+c=(9+1)a+c=9a +(a+c) $ So $ac =10a+c$ divided by 9, will have same remainder as $a+c$ divided by 9.

This is assuming you know the elementary school trick that a number is divisible by 9, if and only if the sum of its digits is divisible by 9.

And then it assumes you realize that that means the divisor when divided by 9 is going to have the same divisor as the sum of the digits divided by 9. Which we can figure out by adding those digits.

Ultimately the divisor is exactly equal to the sum of the sum of the sum of .... the digits.

So add up the numbers 1+2+3+4...... that's long but play with it and see if you can find shortcuts. Example: if 2+7=9 eventually in a future step you will want the remainder after dividing by 9 so that will be 0. So you can toss out any a+b=9. Keep playing and see what happens.

Now... you are simply taking the word of some stranger on the Internet the the remainder when divided by 9 is the same thing as the sum of the digits. Play with it and try to convince yourself it is true.

Hint: the number ac is 10a + c. 10 is (9+1) so ac=10a + c = 9a + (a+c). So ac and a+c will have the same divisor when divided by 9.

$\endgroup$
1
$\begingroup$

Your number has the same remainder when divided by $9$ as $(1 + 2010) + (2 + 2009) + ... + (1005+1006)$ $= 2011 * 1005$. This number has the same remainder as $4*6$ when we divide by $9$, namely $6$.

$\endgroup$

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.