2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.