# Find the remainder when a number is divided by 999 given the following conditions

Find the Remainder when $123$,$123$…(upto $300$ digits) is divided by $999$

MyApproach

This question is of the type when the remainder is divided by $10^n$ + – $1$

I am not able to solve the problem because of type involved and I haven’t understood these type of questions.

Can Anyone explain how to solve this type of problem?

#### Solutions Collecting From Web of "Find the remainder when a number is divided by 999 given the following conditions"

I don’t want to bury you in notation, so I will settle for examples and I hope you will see the implied pattern.

\begin{align}
1234567\pmod 9
&= (1+2+3+4+5+6+7) \pmod 9\\
&= 28 \pmod 9\\
&= (2+8) \pmod 9\\
&= 10 \pmod 9\\
&= (1+0) \pmod 9\\
&= 1\\
\end{align}

\begin{align}
1234567\pmod{99}
&= (1+23+45+67) \pmod{99}\\
&= 136 \pmod{99}\\
&= (1 + 36) \pmod{99}\\
&= 37\\
\end{align}

\begin{align}
1234567\pmod{999}
&= (1+234+567) \pmod{999}\\
&= 802
\end{align}

The verification of that last computation would look like this

\begin{align}
1234567
&= 1 \times 1000000 + 234 \times 1000 + 567 \pmod{999}\\
&= 1 \times (1 + 999999) + 234 \times (1 + 999) + 567 \pmod{999}\\
&= (1 + 999999) + (234+ 234 \times 999) + 567 \pmod{999}\\
&= 1 + 234 + 567 \pmod{999}\\
\end{align}

So

\begin{align}
123,123, \ldots ,123 \pmod{999}
&= 123+123+\ldots + 123 \pmod{999}\\
&= 100 \times 123 \pmod{999}\\
&= 12300 \pmod{999}\\
&= (12 + 300) \pmod{999}\\
&= 312
\end{align}

For the case $10^n + 1$, it looks like this

\begin{align}
1234567\pmod{11}
&= (7-6+5-4+3-2+1) \pmod{11}\\
&= 4 \pmod{11}\\
&= 4\\
\end{align}

\begin{align}
1234567\pmod{101}
&= (67 – 45 + 23 – 1) \pmod{101}\\
&= 44\\
\end{align}

\begin{align}
1234567\pmod{1001}
&= (567-234+1) \pmod{1001}\\
&= 334
\end{align}

The verification of that last computation would look like this

\begin{align}
1234567
&= 1 \times (1001000 – 1001 + 1) + 234 \times (1001-1) + 567 \pmod{1001}\\
&= 1 – 234 + 567 \pmod{1001}\\
&= 1 \times (-1001 + 1) + 234 \times (-1) + 567 \pmod{1001}\\
&= 567 – 234 + 1 \pmod{1001}\\
&= 334\\
\end{align}

Note similarly that
$$10^9 = 1000000000 = 1001000000 – 1001000 + 1001 – 1 = -1 \pmod{1001}$$

HINT: Let $a_n$ be the $3n$-digit number consisting of $n$ blocks of $123$, so that the number in the question is $a_{100}$. Then

$$a_n=1000a_{n-1}+123=999a_{n-1}+a_{n-1}+123\;,$$

so

$$a_n\equiv a_{n-1}+123\pmod{999}\;.$$

This implies that

$$a_n\equiv a_{n-k}+123k\pmod{999}$$

for $0\le k\le n$. What happens if you take $k=n$?

Since $1000\equiv 1\mod 999$,
$$\underbrace{123,123,\dots,123}_{100\ \text{groups}\ \text{of}\ 3\ \text{digits}}=\sum_{i=0}^{99}123\cdot10^{3i}\equiv\sum_{i=0}^{99}123\equiv12300 \equiv\color{red}{312}.$$

Similar to casting out nines to find the remainder when divided by 9, you can cast out 999’s to find the remainder when divided by 999. The reason this works is the same: 1000 = 1 modulo 999, so xyz000…000 = xyz modulo 999. But instead of just adding up the digits, you have to add three-digit groups.

Take for instance the number 12345678. Break this into three-digit groups (starting from the right):

12 345 678

Take the sum:

12 + 345 + 678 = 1035

Reduce modulo 999, using the same trick:

1035 = 1 + 035 = 36 mod 999

So 12345678 = 36 mod 999.

In your case, we have

123 123 123 123=

repeated 25 times:

25 * (123 + 123 + 123 + 123) = 25 * 492 = 12300

So 123123123…123 = 12300 = 12 + 300 = 312 modulo 999.