1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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]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?
     
    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:

    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.
     
  4. Nov 16, 2006 #3
    thanks a lot matt grime. your solution is really neat.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: A problem (and my solution)
Loading...