remainder when 67896789...(300 digits) divided by 999

Question

What is the remainder when 678967896789... (300 digits)is divided by 999? i tried to divide it manually to find some pattern in remainder. But was getting bit lengthy. so please suggest me some short method.

Answer 1

We have $$6789\sum_{r=0}^{74}10^{4r}$$

But $\displaystyle 10^1\equiv10,10^2\equiv100,10^3\equiv1\pmod{999}$

$$\implies \sum_{r=0}^{74}10^{4r}=\sum_{r=0}^{24}(1+10+100)\pmod{999}\equiv25(111)$$

We need to find $6789\cdot25\cdot111\pmod{999}$

$\displaystyle25\equiv-2,6789\equiv3\pmod9\implies25\cdot6789\equiv-2(3)\equiv-6\equiv3\pmod9$

$\implies6789\cdot25\cdot111\equiv3(111)\pmod{9(111)}$

Answer 2

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

678 967 896 789

repeated 25 times:

25 * (678 + 967 + 896 + 789) = 25 * 3330 = 83250

So 67896789...6789 = 83250 = 83 + 250 = 333 modulo 999.

Answer 3

Answer: If you do not know how to use modular arithmetic, here is an interesting observation:

Remainder of 6789/999 = 795

Remainder of 67890000/999 = 957

Remainder of 678900000000/999 = 579

This repeats itself for every addition of 10000.

300 digits/(3*4) = 25

Sum of the remainders = 25*(795+957+579) = 58275

Remainder of 58275/999 = 333.

Two other solutions are elegant, but this is just to add flavor.

Goodluck.

Satish