0
$\begingroup$

How would you find the remainder when you divide

$$1234567891011121314151617\ldots201120122013$$

(The number formed by combining the numbers from $1$ to $2013$)

by $75$?

$\endgroup$
2
  • $\begingroup$ How would you figure it out if you were dividing by 300 instead? $\endgroup$ Nov 19, 2013 at 2:02
  • $\begingroup$ Still have no idea $\endgroup$
    – 1110101001
    Nov 19, 2013 at 2:29

1 Answer 1

12
$\begingroup$

The Chinese Remainder Theorem tells you that to calculate a remainder mod $75$ is the same as calculating mod $25$ and mod $3$. For the former, note that $25$ divides $100$; therefore the remainder for your number is $13$.

For the latter, note that $10$ gives remainder $1$ when divided by $3$, and so the remainder of any decimal number mod $3$ is the remainder of the sum of its digits. More generally, $10^k$ gives remainder $1$ upon division by $3$, and so $n \times 10^k$ gives the same remainder as $n$ upon division by $3$. It follows that your number gives the same mod-$3$ remainder as does $\sum_{i=1}^{2013} i = \frac12 \times 2013 \times 2012 = 2013 \times 1006$. But $2013$ is divisible by $3$ (e.g. by summing the digits) and so your number is too.

Thus the remainder is the number between $0$ and $75$ which is divisible by $3$ and which is $13$ more than a multiple of $25$. This number is $63$.

$\endgroup$
4
  • $\begingroup$ How did you get that the remainder for the number when divided by 25 is 13? $\endgroup$
    – 1110101001
    Nov 19, 2013 at 2:26
  • $\begingroup$ Also, when summing the digits how did you get 2012 and 2013 - Don't you have to add them as 2+0+1+2+2+0+1+3+...? $\endgroup$
    – 1110101001
    Nov 19, 2013 at 2:28
  • $\begingroup$ Since $25$ divides $100$, it divides any multiple of $100$, including $12\dots20122000$. $\endgroup$ Nov 19, 2013 at 2:29
  • $\begingroup$ The point is that $2012$ and $2+0+1+2$ have the same remainders upon division by $3$ --- and that "remainder by three" is additive and multiplicative. Your number is $1 \times 10^? + 2 \times 10^? + 3 \times 10^? + \dots + 2013 \times 10^?$, for varying values of $?$. But $k \times 10^n$ and $k$ have the same remainder mod $3$. And I just noticed a typo in my answer, writing $k$ twice when I should have had an $n$. $\endgroup$ Nov 19, 2013 at 2:31

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.