euclidean algorithm and linear combination for gcd

Use the Extended Euclidean Algorithm.

That is, given $n,m$ follow the dollowing algorithm $$ \eqalign{ & r_{\, - 2} = n = 1\,n + 0\,m \cr & r_{\, - 1} = m = 0\,n + 1\,m \cr & r_{\,0} = r_{\, - 2} - \left\lfloor {{{r_{\, - 2} } \over {r_{\, - 1} }}} \right\rfloor r_{\, - 1} = \bmod \left( {r_{\, - 2} ,\;r_{\, - 1} } \right) = \bmod \left( {n,\;m} \right) = k_{\,0} \,n + l_{\,0} \,m \cr & r_{\,1} = \bmod \left( {r_{\, - 1} ,\;r_{\, - 0} } \right) = k_{\,1} \,n + l_{\,1} \,m \cr & \vdots \cr & r_{\,j} \quad \left| {\;0 \le j} \right.\quad = \bmod \left( {r_{\,j - 2} ,\;r_{\,j - 1} } \right) = k_{\,j} \,n + l_{\,j} \,m \cr & \vdots \cr & r_{\,h - 1} = \gcd (m,n) = \bmod \left( {r_{\,h - 3} ,\;r_{\,h - 2} } \right) = k_{\,\,h - 1} \,n + l_{\,h - 1} \,m = n'\,n + m'\,m \cr & r_{\,h} = 0 = \bmod \left( {r_{\,h - 2} ,\;r_{\,h - 1} } \right) = k_{\,\,h} \,n + l_{\,h} \,m = \left( { - m^ * } \right)n + n^ * \,m = m^ * \,n + \left( { - n^ * } \right)m \cr} $$

At the last but one step you get $r_{h-1}= \gcd(m,n)= n' n + m'm$

Here is a standard layout of the extended Euclidean algorithm: $u_i$ and $v_i$ denote the coefficients of a Bézout's relation: $\;r_i=1253 u_i +7930v_i$ for the remainder at the $i$-th step of the Euclidean algorithm and $q_i$ is the corresponding quotient: \begin{array}{rrrrl} r_i&u_i&v_i&q_i \\\hline 7930 & 0 & 1 \\ 1253 & 1 & 0 & 6 \\\hline 412 & -6 & 1 & 3 \\ 17 & 19 & -3 & 24 \\ 4 & -462 & -73 & 4 \\ \color{red}1 & \color{red}{1867} & \color{red}{-295} \\ \hline \end{array}

You're on the right track. You started out with 1 as a linear combination of 17 and 4, and then a combination of 412 and 17 (although you could stand to make it prettier :). Next you have to make it a combination of 1253 and 412 and finally a combination of 7930 and 1253.

Like this:

1   =   17-4(4)
    =   17-4(412-24(17))
    =   17-4(412)+96(17)
    =   97(17)-4(412)
    =   97(1253-3(412))-4(412)
    =   97(1253)-291(412)-4(412)
    =   97(1253)-295(412)
    =   97(1253)-295(7930-6(1253))
    =   97(1253)-295(7930)+1770(1253)
    =   1867(1253)-295(7930)