0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Where are these questions coming from? This same kind of question, in the same style, just popped up at math.stackexchange.com/questions/1510638/… $\endgroup$ – alex.jordan Nov 3 '15 at 6:02
  • $\begingroup$ @alex.jordan I think jack posted this He was having doubt in the question.He posted in this question comments too. $\endgroup$ – justin takro Nov 3 '15 at 6:16
2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Why you multiplied by 100 i.e"100 .123"?.. and what will be the approach when we divide by 101? $\endgroup$ – Jack Nov 3 '15 at 4:29
  • 1
    $\begingroup$ @jack I think 100 group of 3 digits are added.So,It is multiplied by 100.I don't know what will be approach when we divide it by 101or 1001 $\endgroup$ – justin takro Nov 3 '15 at 4:32
  • $\begingroup$ @Steven Gregory Please explain the approach for the N to be divided by 1001? $\endgroup$ – Jack Nov 3 '15 at 4:33
  • 1
    $\begingroup$ I multiplied by 100 because there are 100 occurrences of 123. I did not divide by 1001. I broke 12300 into two groups of "three": 012 and 300, then added the two groups. $\endgroup$ – steven gregory Nov 3 '15 at 6:58
  • $\begingroup$ @StevenGregory Thanku Very Nice Explanation.+1 $\endgroup$ – justin takro Nov 3 '15 at 8:31
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ How u get p which is repeated $25$ times? $\endgroup$ – justin takro Nov 3 '15 at 5:59
  • $\begingroup$ what do you mean by "p which is repeated 25 times?" $\endgroup$ – Satish Ramanathan Nov 3 '15 at 6:06
  • $\begingroup$ 123 123 123 123p= repeated 25 times I mean this?How it came 123p?How you know it is repeated 25 times. $\endgroup$ – justin takro Nov 3 '15 at 6:08
  • $\begingroup$ Just a typo, I will edit it, sorry $\endgroup$ – Satish Ramanathan Nov 3 '15 at 6:10
  • $\begingroup$ Why are you repeating it $25$ times? $\endgroup$ – justin takro Nov 3 '15 at 8:30

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.