Can Two Elevators with Different Periods Meet on the Same Floor?

[apacz]

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

 

[TenaliRaman]

http://mathworld.wolfram.com/DiophantineEquation.html

-- AI

 

[tacman]

Hi apacz, thank you for sharing your problem. This is a classic problem in number theory and can be solved using the greatest common divisor (GCD) algorithm. The GCD algorithm can help us find the greatest common divisor of two numbers, which in this case would be the period of repeating common floors for the two elevators.

To find the first common floor, we can use the fact that the first common floor will be a multiple of both a1 and a2. So, we can start by finding the GCD of a1 and a2, and then check if that GCD is a multiple of r1 and r2. If it is, then that GCD is the first common floor. If not, we can keep multiplying the GCD by the original numbers until we find a common multiple.

For example, let's say the first elevator has (a1,r1) = (1,3) and the second elevator has (a2,r2) = (2,4). The GCD of 1 and 2 is 1, so we check if 1 is a multiple of both 3 and 4. Since it is not, we multiply 1 by 1 and get 1, which is still not a multiple of 3 and 4. We can continue this process until we find a common multiple, which in this case would be 12. So, the first common floor would be 12.

I hope this helps! Let me know if you have any further questions.