Intersection of two Arithmetic progressions

Question

Let us say I have two Arithmetic progressions

$AP_1 = a + nb$

$AP_2 = c + nd$

Can we find a new Arithmetic progression $AP_3$ which is intersection of both $AP_1$ and $AP_2$?

Answer 1

We have that for any two arithmetic progressions, $AP_1, AP_2$, we have that their intersection are those points where

$b(n_1)+a = d(n_2)+c \iff b(n_1)= d(n_2)+c-a $

for some $n_1, n_2 \in \mathbb{Z}$. If no such $n$s exist, then the intersection is empty. If they exist, we can proceed as follows.

This means that the intersection of these two sets produce the set $AP_3 =(b\cdot d)(n) + (d \cdot k + c)$ for some $k \in \mathbb{Z}$ such that $b \cdot k_1 = (d\cdot k + (c-a))$ for some $k_1 \in \mathbb{Z}$.

We can see this: $(b\cdot d)\cdot(n) + (d \cdot k + c) = (b)\cdot (d\cdot n) + (b \cdot k_1 + a) = (b)\cdot (d\cdot n + k_1) + a$, which is clearly a subset of $AP_1$.

We also see that $(b\cdot d)\cdot(n) + (d \cdot k + c) = (d)\cdot (b\cdot n + k) + c$, which is clearly a subset of $AP_2$, as required.

Answer 2

The answer is clear when you use modular arithmetic. The numbers $x$ in arithmetic sequence $$ a+bn,\qquad n\in\mathbb{Z} $$ are simply those such that $$ x\equiv a\bmod b. $$ Thus deciding whether two (or more) arithmetic sequences have common elements is equivalent to solving systems of congruences $$ \left\{ \begin{array}{l} x\equiv a_1\bmod b_1\\ x\equiv a_2\bmod b_2 \end{array} \right.\qquad\qquad(\ast) $$ When $\mathrm{gcd}(b_1,b_2)=1$ the Chinese Remainder Theorem says that a solution always exists.

When $\mathrm{gcd}(b_1,b_2)=d>1$ one has $N=\mathrm{lcm}(b_1,b_2)=dB_1B_2$ where $b_1=dB_1$ and $b_2=dB_2$. Then the pairs $(a_1,a_2)$ that make the system $(\ast)$ solvable are those in the image of the canonical quotient map $$ \pi:\frac{\mathbb{Z}}{N\mathbb{Z}}\longrightarrow \frac{\mathbb{Z}}{dB_1\mathbb{Z}}\times\frac{\mathbb{Z}}{dB_1\mathbb{Z}}. $$ Since $\pi(\bar x)=(\bar x,\bar x)$, the pairs $(a_1,a_2)$ for which $(\ast)$ has a solution are exactly those for which $$ a_1\equiv a_2\bmod d. $$ Moreover, if $A$ is a solution of $(\ast)$ the intersection between the two arithmetic sequences is the arithmetic sequence $$ A+nN,\qquad n\in\mathbb{Z}. $$