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.
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 $$