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

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.
