# Finding common terms of two arithmetic sequences using Extended Euclidean algorithm

I have a problem which could be simplified as: there are two arithmetic sequences, a and b. Those can be written as

a=a1+m*d1
b=b1+n*d2


I need to find the lowest term, appearing in both sequences. It is possible to do by brute force, but that approach is not good enough. I was given a hint - extended Euclidean algorithm can be used to solve this. However, after several frustrating hours I cannot figure it out.

For example:

a1 = 2
d1 = 15

b1 = 67
d2 = 80

That gives these sequences
2 17 32 47 62 77 ... 227 ...
67  147  227
^
Needed term


Could you somehow point me to how to use the algorithm for this problem? It's essentially finding the lowest common multiple, only with an "offset"

Thank you

-
It minimum, you require $\gcd(d_1,d_2)$ to be a divisor of $a_1-b_1$. – Thomas Andrews Nov 5 '12 at 13:54
If a1-b1 is divisible by gcd(d1, d2), then there is a solution. If not, there isn't. I have a equivalent check in my program. But still, I don't know how to speed it up using this. (I hope I understood you right) – Martin Melka Nov 5 '12 at 14:49
(+1) because your example helped me to give you a (hopefully) clear answer. – adam W Nov 5 '12 at 16:28

Your equations: $$a(m) = a_1 + m d_1$$ $$b(n) = b_1 + n d_2$$

You want $a(m) = b(n)$ or $a(m)-b(n)=0$, so it may be written as $$(a_1-b_1) + m(d_1) +n(-d_2) = 0$$ or $$m(d_1) +n(-d_2) = (b_1-a_1)$$

You want $n$ and $m$ minimal and that solves that. This is of course very similar to the EGCD, but that the value of $b_1 - a_1$ is the desired value intead of the value $1$. EGCD sovles it for the value of $1$ (or the gcd of $d_1$ and $d_2$).

This is actually a lattice reduction problem since you are interested in the minimum integer values for $m$ and $n$. That is an involved problem, but this is the lowest dimension and thus is relatively easy.

The method I have written in the past used a matrix form to solve it. I started with the matrix $$\pmatrix{1 & 0 & d_1 \\ 0 & 1 & -d_2}$$

which represents the equations \begin{align} (1)d_1 + (0)(-d_2) = & \phantom{-} d_1 \\ (0)d_1 + (1)(-d_2) = & -d_2 \\ \end{align}

Each row of the matrix gives valid numbers for your equation, the first element in the row is the number for $m$, the second is for $n$ and the third is the value of your equation for those $m$ and $n$. Now if you combine the rows (such as row one equals row one minus row two) then you still get valid numbers. The goal then is to find a combination resulting in the desired value of $b_1 - a_1$ in the final column.

If you use EGCD you can start with this matrix: $$\pmatrix{d_2 \over g & d_1 \over g & 0 \\ u & -v & g}$$

where $u$, $v$, and $g$ are the outputs of the EGCD (with $g$ the gcd) since EGCD gives you $ud_1 + vd_2 = g$

In your example you would have: $$\pmatrix{16 & 3 & 0 \\ -5 & -1 & 5}$$ From there you can scale the last row to get $kg = (b_1 - a_1)$ for some integer $k$, then to find the minimal values use the first row to reduce, since the zero in the first row will not affect the result.

Again, for your example, $k=13$ which gives $$\pmatrix{16 & 3 & 0 \\ -65 & -13 & 65}$$

Adding $5$ times the first row gives $$\pmatrix{15 & 2 & 65}$$

Which represents the $16$th and $3$rd terms (count starts at $0$) respectively.

-
Wonderful answer. Thank you for that. I have a question regarding the last step. Say I have the last-but-one matrix. Do I understand it correctly that now I am trying to combine the two rows into one, where the first two numbers would be minimal, but positive? – Martin Melka Nov 6 '12 at 10:20
Is it somehow possible for this algorithm not only to calculate the first term, but also the following? I have several different sequences and I need to find a term they all contain. So I was thinking that I would be able to quickly calculate terms that two sequences contain and then check them against the remaining sequences. This is kinda brute force, but not as slow as checking all the terms. (the next common term for the example given is 1352) – Martin Melka Nov 6 '12 at 14:47
@Martin yes to the minimal but positive. The row 16 3 0 shows that wherever the sequences are equal, count another 16 on one and 3 on the other and they are equal there also. And another 16 and 3 to find the next one after that, etc. – adam W Nov 9 '12 at 15:50
@Martin if you have more than two sequences, then it becomes more involved, the comment I made about lattice reduction becomes more important. If you have three or more sequences, then there are two or more homogenous rows to be able to combine (the 16 3 0 in your example). But yes, doing for two first does reduce some work. Could you not just define a sequence from where the two are equal then combine that with the next sequence and so on? – adam W Nov 9 '12 at 15:56