# finding minimum common element in two arithmetic sequences

i have two different arithmetic sequences and i know their first term and common difference. Is there any short technique or some formula by which i can find the first element which is common in both the sequences. There is one post regarding this in the site but could not understand anything from it. Kindly help

## 1 Answer

Given $a_i=a_0+id$ and $b_i=b_0+ie$, you want tor find $n,m$ such that $a_n=b_m$. The condition reads $a_0-b_0=me-nd$. Let $f=\gcd(d,e)$. Then $f\mid me-nd$, so if $f\nmid a_0-b_0$, the sequences have no terms in common. Assume therefore that $f\mid a_0-b_0$, say $a_0-b_0=kf$. If $k=0$, then clearly $a_0=b_0$ is the first common term. Assume therefore that $k\ne0$.

By the extened Euclidean algorith, you find $u,v\in \mathbb Z$ with $ud+ve=f$. Then the general soultion to $xd+ye=f$ is $x=u+re$, $y=v-rd$, $r\in\mathbb Z$. Then general solution to $me-nd=a_0-b_0$ is therefore $$m=k(rd-v),\quad n=k(re+u),\quad r\in\mathbb Z.$$ Depending on the signs of $k,d,e$, we obtain different conditions on $r$:

• If $kd>0$, we need $r\ge\lceil\frac vd\rceil$ and smaller $r$ means smaller $m$
• if $kd<0$, we need $r\le\lfloor\frac vd\rfloor$ and greater $r$ means smaller $m$
• If $kd=0$, then we can let $n=0$ and $m=-kv$, provided this is $\ge0$

Similarly,

• If $ke>0$, we need $r\ge\lceil\frac {-u}e\rceil$ and smaller $r$ means smaller $n$
• if $ke<0$, we need $r\le\lfloor\frac {-u}e\rfloor$ and greater $r$ means smaller $n$
• If $ke=0$, then we can let $m=0$ and $n=ku$, provided this is $\ge0$

Combining the restrictions from both sets of conditions, we either obtain contardictory conditons (for example $a_n=7+n$ and $b_n=5-n$ have no term in common). Or conditions of the form $r_1\le r\le r_2$ giving us a finite range of common terms (e.g. $a_i=1+3i$ and $b_j=13-2j$ have $a_0=b_6=1$, $a_2=b_3=7$, and $a_4=b_0=13$ in common) and the precise notion of "first" common term may be problematic. Or we obtain an unbounded range (i.e. of the form $r\ge r_1$ or of the form $r\le r_1$), in which case the boundary case give us the first common term of the sequences.