What is the Remainder when Dividing a Number with 1000 Ones by 1001?

[murshid_islam]

here is the problem:
1. what is the remainder if 11...1 is divided by 1001? (the dividend has 1000 1's)

this is what i did (please tell me if there is any other methods of doing it):

$$11...1$$

$$=10^{999} + 10^{998} + \cdots + 10^{0}$$

$$=\frac{10^{999} - 1}{9}$$

i noticed that
$$1000 = 10^{3} \equiv -1 \left(\bmod 1001\right)$$

$$10^{6} \equiv 1 \left(\bmod 1001\right)$$

$$10^{996} \equiv 1 \left(\bmod 1001\right)$$

$$10^{996}.10^{4} \equiv 10^{4} \equiv 991 \left(\bmod 1001\right)$$

$$10^{1000} - 1 \equiv 990 \left(\bmod 1001\right)$$

$$\frac{10^{999} - 1}{9} \equiv 110 \left(\bmod 1001\right)$$

is there any problem in my method? is there any other easier way of doing it?

 

[matt grime]

There is an elegant solution that looks like this:

100100
010010
001001

each of those is obviously divisble by 1001, and their sum is

111111

there are 6 1's, so we can delete all but the first 1000 mod 6 =4 1s and we only need to work out the remainder of 1111 on division by 1001, and that is obviously 110.

 

[murshid_islam]

thanks a lot matt grime. your solution is really neat.