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: Number theory problem

  1. Dec 21, 2008 #1
    1. The problem statement, all variables and given/known data
    A given number [tex]x[/tex], if divided by 31, the remainder is 10, if divided by 73, the remainder is 35, if divided by 111, the remainder is 29. Then, what's the number [tex]x[/tex]?


    2. Relevant equations
    [tex]
    x = 31k_1 + 10 = 73k_2 + 35 = 111k_3+29, \tex{ then?}
    [/tex]


    3. The attempt at a solution

    I roughly remember this is a famous problem in high school mathematics, but I can't remember the way to solve this type of problems. The number of unknowns seem to be larger than the number of equations. I tried to write these equations in a way like,
    [tex]
    x = 111\times73\times31\times u_1
    +73\times31\times u_2
    + 31\times k_3 + 10
    [/tex]
    But it seems to be not so helpful.
    Any ideas? thanks in advance.
     
  2. jcsd
  3. Dec 21, 2008 #2

    HallsofIvy

    User Avatar
    Science Advisor

    This uses the "Chinese remainder theorem".
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook