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!

Homework Help: Brain teasing problem in number theory

  1. Aug 15, 2010 #1
    1. The problem statement, all variables and given/known data

    Let X=10000000099 represent an eleven digit no. and let Y be a four digit no. which divides X.Find the sum of the digits of the four digit no. Y.


    2. Relevant equations

    None


    3. The attempt at a solution

    I guess I have to factorize X. But it is really difficult to do so as i cant find a prime which divides it. Moreover i am in search for a systematic solution and not any trial method.Any help in this regard would be sincerely appreciated. Thank You.
     
  2. jcsd
  3. Aug 15, 2010 #2
    Last edited by a moderator: Apr 25, 2017
  4. Aug 15, 2010 #3
    How did you find it out
     
  5. Aug 15, 2010 #4
    Here is an approach which is potentially less computation-intensive.

    If we call the 11-digit number N, it's easy to see that
    N = 10^10 + 10^2 -1, so N = P(10), where
    P(x) = x^10 + x^2 - 1.

    If you were a genius, I guess it would be obvious that
    P(x) = (x^4 - x^2 + 1) (x^6 + x^4 - 1).

    Confession: Not being a genius, I used a computer algebra system.
    I guess you can drive this identity from x^5 + x - 1 = (x^2 - x + 1) (x^3 + x^2 - 1), but that's not obvious to me either.

    If you now let x = 10, we have
    N = (10^4 - 10^2 + 1) (10^6 + 10^4 - 1),
    and 10^4 - 10^2 + 1 = 9901.

    This isn't a complete solution, because it's not clear from the above that 9901 is the only 4-digit divisor.
     
    Last edited: Aug 15, 2010
  6. Aug 17, 2010 #5
    Thanks
    I understood it well and it is a very good solution
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook