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?
Best Answer
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}$$