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):

[tex]11...1[/tex]

[tex]=10^{999} + 10^{998} + \cdots + 10^{0}[/tex]

[tex]=\frac{10^{999} - 1}{9}[/tex]

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

[tex]10^{6} \equiv 1 \left(\bmod 1001\right)[/tex]

[tex]10^{996} \equiv 1 \left(\bmod 1001\right)[/tex]

[tex]10^{996}.10^{4} \equiv 10^{4} \equiv 991 \left(\bmod 1001\right)[/tex]

[tex]10^{1000} - 1 \equiv 990 \left(\bmod 1001\right)[/tex]

[tex]\frac{10^{999} - 1}{9} \equiv 110 \left(\bmod 1001\right)[/tex]

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.