Hello everyone,(adsbygoogle = window.adsbygoogle || []).push({});

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

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# 2 elevators problem, gcd

**Physics Forums | Science Articles, Homework Help, Discussion**