# Remainder when $123456789101112\ldots$ is divided by $75$

How would you find the remainder when you divide

$$1234567891011121314151617\ldots201120122013$$

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

by $75$?

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

## 1 Answer

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

• How did you get that the remainder for the number when divided by 25 is 13? Nov 19, 2013 at 2:26
• 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+...? Nov 19, 2013 at 2:28
• Since $25$ divides $100$, it divides any multiple of $100$, including $12\dots20122000$. Nov 19, 2013 at 2:29
• 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$. Nov 19, 2013 at 2:31