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
 A: 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.
