Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A problem (and my solution)

  1. Nov 15, 2006 #1
    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]=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?
    Last edited: Nov 15, 2006
  2. jcsd
  3. Nov 15, 2006 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    There is an elegant solution that looks like this:


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


    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.
  4. Nov 16, 2006 #3
    thanks a lot matt grime. your solution is really neat.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook