# euclidean algorithm and linear combination for gcd

(i) Use the Euclidean Algorithm to find gcd(1253, 7930).

(ii) Using the workings in (i), find m, n ∈ Z such that gcd(1253, 7930) = 1253m + 7930n.

i) 7930 = 1253*6 + 412

1253 = 412*3 + 17

412 = 17*24 + 4

17 = 4*4 + 1

4 = 1*4 + 0

So gcd = 1.

ii)1 = 1*17 + -4(4)

4 = 1*(412) + -24*(17)

17 = 1*(1253) + -3*(412)

412 = 1*(7930) + -6*(1253)

So 1 = 1*(17) + -4*(4)

= 1*(17) + -4((1*(412) + -24*(17))) enter image description here

I'm up to ii) but I got confused. I tried following an example online but I got lost and idk if I'm on the right track or where to go from here? where I have the 412 in the last line I wrote, would I substitute in the 1 * 7930 + -6*1253 thing? and in the 17 part in the last line I'd substitute in 11253 + - 3412? what would I do from there to find m and n?

• Welcome to Maths SX! There exists an extended Euclidean algorithm which makes all these computations automatic, without having to calculate backwards. – Bernard Aug 10 at 10:01
• It is usually simpler and far less error prone to compute the Bezout identity in the forward direction by using this version of the Extended Euclidean algorithm, which keeps track of each remainder's expression as a linear combination of the gcd arguments. – Bill Dubuque Aug 10 at 12:14

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)