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: 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
    x = 31k_1 + 10 = 73k_2 + 35 = 111k_3+29, \tex{ then?}

    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,
    x = 111\times73\times31\times u_1
    +73\times31\times u_2
    + 31\times k_3 + 10
    But it seems to be not so helpful.
    Any ideas? thanks in advance.
  2. jcsd
  3. Dec 21, 2008 #2


    User Avatar
    Science Advisor

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