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

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

• In my first example, A1=1, d=14, B1=8, D=21. In your formula it would be: (|21-14|) | 1 - 8 + 21 - 14 => 7 | 0. What does it mean? Feb 15, 2016 at 2:08
• That is fine. $0 = k \cdot 7$ for $k = 0 \in \mathbb{Z}$. so $7 \mid 0$ is true and this says there are solutions $X = n \in \mathbb{Z}$ to $(2)$ and its special case $(1)$.
– mvw
Feb 15, 2016 at 2:23
• Ok, so 7 | 0 means that 0 is multiple of 7. I didn't know what this symbol mean. Let me try the second example... A1=1, d=14, B1=8, D=28 => (|28-14|) | 1-8+28-14 => 14 | 7 => k=0.5 not Z, so false Feb 15, 2016 at 2:34
• Reading again. Yes. It means $7$ divides $0$ with remainder $0$. The second case runs down to if $14$ divides $-7$, or $14$ divides $7$. Which in both cases it does not.
– mvw
Feb 15, 2016 at 2:35
• It is great to be able to check if the progressions overlap without using GCD. Is it also possible to find the first overlap occurrence? Feb 15, 2016 at 3:07

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.

• Ok, thanks. I can compute the gcd(s,q). After testing that p - r is a multiple of gcd(s,q), is there a formula that I can find the first intersection, or do I need an algorithm with a loop? Feb 15, 2016 at 1:19
• Using the extended euclidean algorithm, you could find the value of x and y, that should lead you to an intersection point. Feb 15, 2016 at 6:56