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