Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

2 elevators problem, gcd

  1. Dec 4, 2005 #1
    Hello everyone,
    I have such problem: there are 2 elevators which go only upwards, and stop on only particular floors, each elevator is described by 2 numbers: (a,r) where a is a number of floor on which the elevator starts and r is a number which is a period of elevator's stops. For example, if we have elevator a=1, r=3 then it stops on that floors: 1,4,7,10,13,16,19 and so on and so forth. And now my question: how to find the first common floor of those 2 elevators and the period of repeating common floors. I know that two elevators (first elevator (a1,r1), second elevator (a2,r2) ) have common floor when GCD(r1,r2)|p where p is |a1-a2| so it should be something like that:
    a1+x*r1 = a2+y*r2
    x*r1 + (-y)*r2 = a2 - a1
    I don't know what to do know and if it is a good way of solving that problem, I though about The Extended Euclidean Algorithm which says:

    So we could try to do something like that:
    x*r1 + (-y)*r2 = gcd(r1,r2)*k
    But... afair a,b in extended euclidean algorithm must be integers so we can't divide it by k.
    Doest anyone know how to solve it ? Maybe there is some other way to solve it?

  2. jcsd
  3. Dec 4, 2005 #2
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook