euclidean algorithm and linear combination for gcd

Question

(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?

Answer 1

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)

Answer 2

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$

Answer 3

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}