5

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.

Frank
  • 5,984
  • 2
    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. – fleablood Oct 15 '16 at 20:48

4 Answers4

5

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

Evariste
  • 2,511
  • 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}$$ – Frank Oct 15 '16 at 19:09
  • 3
    @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$ – JMoravitz Oct 15 '16 at 19:12
  • 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$. – Evariste Oct 15 '16 at 19:12
  • @JMoravitz So the problem simply reduces to finding $1+2+3+\ldots +2010$, then dividing that by $9$? – Frank Oct 15 '16 at 19:13
  • 4
    @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. – JMoravitz Oct 15 '16 at 19:14
  • @JMoravitz Um... You get the middle digit of the consecutive integers? – Frank Oct 15 '16 at 19:16
  • @Frank try adding $x+(x+1)+(x+2)+\dots+(x+8)$ and see what happens. Note: $x+(x+1)+\dots+(x+8)=9x+(1+2+\dots+8)$. What is the remainder of that when divided by nine? Once you have this step done, its figuring out how much of the sum $1+2+3+\dots+2010$ actually requires thought. – JMoravitz Oct 15 '16 at 19:20
  • @JMoravitz $$x+(x+1)+(x+2)+\ldots +(x+8)=9x+36$$ as you said. So$$\frac {9x+36}{9}=x+4$$ so it is the middle number. – Frank Oct 15 '16 at 19:22
  • @Frank $\dots=x+4=x+4+\frac{0}{9}$. What is the remainder again? What is the remainder of 36 when dividing by nine? Don't confuse remainder and quotient. – JMoravitz Oct 15 '16 at 19:23
  • @JMoravitz $0$? Do you want to move this to chat? – Frank Oct 15 '16 at 19:26
  • Let us continue this discussion in chat. – JMoravitz Oct 15 '16 at 19:26
  • Frank. Take lots of scratch paper and play with it for a few hours you will find a pattern, and you will, convince yourselves you can repeat it... and repeat it... and you will find that you have absolutely convinced yourself. – fleablood Oct 15 '16 at 21:15
  • Take a simpler case. What is the remainder of 12345=10000+2x1000+3x100+4x10+5=(9999+1)+(2x999+2)+(3x99+3)+(4x9+4)+5=[9999+2x999+3x99+4x9]+(1+2+3+4+5). So remainder is remainder of 1+2+3+4+5=15. And 15=10+6=9+1+5. So remainder is same as remainder of 1+5=6. Which is 6. Can you see how that can always be extended. – fleablood Oct 15 '16 at 21:25
4

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*}

Bernard
  • 175,478
1

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.

fleablood
  • 124,253
1

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$.

Browning
  • 659