Old bell rang problem with different starting time Suppose two bells rang at particular intervals but starting from a different time. First time when it will ring together is ?
e.g.,
First bell starts at 3, and repeats at regular interval of 5.
Second bell starts at 2, and repeats at regular interval of 2.
\begin{array}{|c|c|c|c|c|c|}
\hline
Time& 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ \hline
Bell1& - & -& \checkmark & - & - & - & - &\checkmark\\ \hline
 Bell2&  -& \checkmark& - & \checkmark & - & \checkmark & - & \checkmark\\ \hline
\end{array}
Approach: Suppose we are given 4 integers namely,  n, m, a, and k.
We have to find $n + \alpha m = k + \beta a$.
Since brute force will be slow, I used Extended Euclid algorithm.
$k - n = \alpha m - \beta a$ for k > n, and find $\alpha$ and $\beta$.
The problem is, for the given example it gives $3 - 2 = -2 * 2 + 1*5$ which is equivalent to $3 - 2 = 3*2 - 1*5$ and I need the second one to find the answer but my extended Euclid algo gives the first one. To solve this again I reverse the sign of both $\alpha$ and $\beta$ and then tried to match the value which is slow.
 A: Good work so far. The "problem" with the first solution, $(\alpha, \beta) = (-2, 1)$, is that the $-2$ is negative. And so you add $(4, -2)$ to it to get a new solution $(4, -1)$, and now the first entry is positive and you're good to go. 
Let me answer in two ways from here:


*

*how do you find $(p, q) = (4, 2)$, the "thing to add"? 


Well, you know that $\alpha p + \beta q$ must be zero? So you can apply the extended euclidean algorithm again! It's possible that when you do so, you'll get a $p$ that's negative; if so, you can just replace $p$ with $-p$ and $q$ with $-q$, because
$$
\alpha (-p) + \beta(-q) = -(\alpha p + \beta q) = -0 = 0
$$
as well. 


*Why find that "thing to add" at all? 


An alternative to this is to say that if the bells rang together at time $-2$ (which is what your initial answer tells you), then they'll next ring together after $d = lcm(n, m)$ time units. So the times when they'll ring together are $-2, -2 + d, -2 + 2d, \ldots$, and you just need to find the first of these that's nonnegative. I'll bet you can do that yourself. 
