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:
    ax+by=gcd(a,b)

    So we could try to do something like that:
    (a2-a1)/gcd(r1,r2)=k
    a2-a1=gcd(r1,r2)*k
    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?

    Regards,
    apacz
     
  2. jcsd
  3. Dec 4, 2005 #2
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: 2 elevators problem, gcd
  1. GCD question` (Replies: 3)

  2. GCD in PROOF? (Replies: 3)

  3. Gcd and lcm (Replies: 59)

  4. GCD question (Replies: 6)

Loading...