1. Not finding help here? Sign up for a free 30min 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!

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...