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