Formula to find the first intersection of two arithmetic progressions Formula to find the first intersection of two arithmetic progressions
I am not good in math, but I need to determine if two generic arithmetic progressions have an intersection point and, in that case, find the first intersection. I've searched the web and found some solutions, but I couldn't understand them.
Is it possible to have a simple formula or algorithm that finds the first intersection point of two arithmetic progressions?
Example 1:
$$
A_n = A_1 + (n - 1)d \\
AP1: A_1 = 1, d = 14 \Rightarrow \{1, 15, 29, 43, \dotsc \} \\
AP2: A_1 = 8, d = 21 \Rightarrow \{8, 29, 50, 71, \dotsc \} \\
$$
Result: First intersection point on $A_n = 29$
Example 2:
$$
A_n = A_1 + (n - 1)d \\
AP1: A_1 = 1, d = 14 \Rightarrow \{1, 15, 29, 43, \dotsc \} \\
AP2: A_1 = 8, d = 28 \Rightarrow \{8, 36, 64, 92, \dotsc \}
$$
Result: Does not have an intersection point
The reason I need this is because I am developing a calendar (like Google Calendar) but where it is not allowed to create two event series that intersect each other. I've posted a similar question here.
 A: Assume the two progressions are
$$
A_n = A_1 + (n-1) \, d \\
B_m = B_1 + (m-1) \, D
$$
You want to check
\begin{align}
A_n &= B_m \\
A_1 + (n-1) \, d  &= B_1 + (m-1) \, D \iff \\
A_1 - B_1 + D - d &= -n \, d + m \, D \iff \\
-d \, n + D \, m &= A_1 - B_1 + D - d \quad (1) 
\end{align}
Interpretation as Linear Diophantine Equation
Equation $(1)$ can be interpreted as a linear Diophantine equation
$$
a X + b Y = c \quad (X, Y \in \mathbb{Z}) \quad (2)
$$
with $a = -d$, $b = D$ and 
$c = A_1 - B_1 + D - d \in \mathbb{Z}$ 
and variables $X = n$ and $Y = m$, where one is only interested in the positive solutions $X > 0, Y > 0$.
For this kind of equations there exists an algorithm to determine the solutions.
Criterion for Solutions:
For solutions to exist, one needs $g = \gcd(a, b)$ to divide $c$, $g \mid c$.
Here we have 
$$
g = \gcd(-d, D) = \gcd(d, D)
$$
So the criterion for a solution is
$$
\gcd(d, D) \mid A_1 - B_1 + D - d  \quad (3)
$$
Because $\gcd(d, D) \mid D - d$, it suffices to check
$$
\gcd(d, D) \mid A_1 - B_1 \quad (4)
$$
Solution of the Homogeneous Equation:
The homogeneous equation $a X_h + b Y_h = 0$ has the solutions 
$$
(X_h,Y_h) = (t \, b', -t\, a') \quad (t \in \mathbb{Z}) \quad (5)
$$ 
with $a' = a / g = -d / \gcd(d,D)$, $b' = b / g = D / \gcd(d, D)$.
Finding one Particular Solution:
A particular solution of $(2)$ is usually found by finding a solution $(u, v)$ to
$$
a u + b v = g \iff \\
-d u + D v = \gcd(d, D)
$$
these numbers are calculated by the extended Euclidean algorithm for $-d$ and $D$.
A particular solution is
$$
(X_p, Y_p) = \left(\frac{c}{g} u, \frac{c}{g} v \right) \quad (6)
$$ 
General Solution:
The general solution is: 
\begin{align}
(X, Y) 
&= (X_h + X_p, Y_h + Y_p) \\
&= \left(\frac{c}{g} u + t \, b', \frac{c}{g} v -t\, a' \right) \\
&= \left(\frac{c}{g} u + t \, \frac{D}{g}, \frac{c}{g} v + t\, \frac{d}{g} \right) \quad (7)
\end{align}
Reducing to the First Positive Solution:
We need to choose a $t$ with
$$
X(t) = \frac{c}{g} u + t \, \frac{D}{g} > 0 \\
Y(t) = \frac{c}{g} v + t\, \frac{d}{g} > 0
$$
Among those $t$ one needs to choose the one which minimizes $(X,Y)$:
$$
t = \max \left\{ 
\left\lfloor -\frac{c}{D} u \right\rfloor + 1,
\left\lfloor -\frac{c}{d} v \right\rfloor + 1
\right\} \quad (8)
$$
Example:
For your first example we had $A_1 = 1$, $B_1 = 8$, $d = 14$, $D = 21$.
We have $g = \gcd(14, 21) = 7$. 
The extended Euclidean algorithm gives (e.g. see here)
$$
(u, v) = (1, 1) \\
-14 \, 1 + 21 \, 1 = 21 - 14 = 7 = \gcd(14, 21) 
$$
We have $c = 1 - 8 + 21 - 14 = 0$, so we have just a homogenous equation here.
The solution is
$$
(X_h, Y_h) = (t b', -t a') = (t (21/7), -t(-14/7)) = (3 t, 2 t) 
\quad (t \in \mathbb{Z})
$$
These are all integer solutions. The first positive solution happens for $t = 1$ with
$$
(X, Y) = (3, 2) = (n, m)
$$
and indeed
$$
A_3 = 1 + (3-1) \cdot 14 = 1 + 2 \cdot 14 = 29 \\
B_2 = 8 + (2-1) \cdot 21 = 8 + 21 = 29
$$
A: Let the two series be $ a[n] = p + nq $ and $ b[n] = r + ns $
Assuming it does intersect, then
$ a[x] = b[y] \implies p + xq = r + ys $
It looks daunting with so many variables, but in fact $ p, q, r, s $ are all known, so not too bad. Next we rearrange 
$ p - r = ys - xq $. By the extended euclidean algorithm, we know we can find $ x $ and $ y $ such that $ ys - xq = gcd(s, q) $. 
So the two series intersect if and only if $ p - r $ is a multiple of $ gcd(s, q) $. 
To code the algorithm, just compute the gcd and do a trial division.
