What is the link between the quotient and the Bézout coefficients in the Extended Euclidean Algorithm?

Here is an image from the wikipedia page of the EEA for working out the Bézout coefficients for 240·s_k + 46·t_k = r_k where r_k = GCD(240,183):

What I am trying to work out is what s_i and t_i 'mean' at each stage of this equation and how they link to the other elements (I can use the equation and get the correct result). My understanding so far is that the BC effectively track the requisite coefficients to give the remainder in the second column.

How this is calculated in the first two rows is easy to understand. The first says that where there is a remainder of 240, s_i must be 1 and t_i must be 0, and the second where there is a remainder of 46, s_i must be 0 and t_i must be 1. This is trivial, but it's after that point I can't quite follow how they are calculating correctly (which is not to say I cannot do the calculations themselves).

So take the third row. This says that with a remainder of 10, s = 1 and t = -5 (which is clearly correct as 1*240-5*46 = 10). But how is it that by taking the coefficients for r_i-2 and r_i-1 we can then calculate the coefficient for r_i simply from:

s_i = s_i-2 - s_i*q
t_i = t_i-2 - t_i*q

(where q is the quotient)

How is it that that works? I know the equations and I can read the proofs, but they just prove it is valid, which I do not doubt. My question is why is it valid/why does it make sense? The quotient link makes sense in terms of the remainder because that feeds directly back into the quotient and the search for the GCD, but I can't grasp it in terms of the coefficients.

Any help will be greatly appreciated.

Solution 1:

The Extended Euclidean Algorithm is more intuitively presented in the form described here using row operations. Below is the result, in explicit equational form, and in more concise tabular form.

$$\rm\begin{eqnarray} [\![0]\!]\quad \color{#C00}{240}\!\ &=&\,\ \ \ 1&\cdot& 240\, +\ 0&\cdot& 46 \\ [\![1]\!]\quad\ \color{#C00}{46}\ &=&\,\ \ \ 0&\cdot& 240\, +\ 1&\cdot& 46 \\ \color{#940}{[\![0]\!]-5\,[\![1]\!]}\, \rightarrow\, [\![2]\!]\quad \ \color{#C00}{ 10}\ &=&\,\ \ \ 1&\cdot& 240\, -\ 5&\cdot& 46 \\ \color{#940}{[\![1]\!]-4\,[\![2]\!]}\,\rightarrow\,[\![3]\!]\quad\ \ \ \color{#C00}{6}\ &=&\, {-}4&\cdot& 240\, + 21&\cdot& 46 \\ \color{#940}{[\![2]\!]-1\,[\![3]\!]}\,\rightarrow\,[\![4]\!]\quad\ \ \ \color{#C00}{4}\ &=&\,\ \ \ 5&\cdot& 240\, -\color{}{26}&\cdot& \color{}{46}\\ \color{#940}{[\![3]\!]-1\,[\![4]\!]}\,\rightarrow\,[\![5]\!]\quad\ \ \ \color{#C00}{2}\ &=&\, {-}9&\cdot& 240\, + 47&\cdot& 46 \\ \color{#940}{[\![4]\!]-2\,[\![5]\!]}\,\rightarrow\,[\![6]\!]\quad\ \ \ \color{#C00}{0}\ &=&\ \ 23&\cdot& 240\, {-}120&\cdot& 46 \\ \end{eqnarray}\qquad\qquad\quad$$

$$\begin{array}{rrr} 240 & 1 & 0\\ 46 & 0 & 1\\ 10 & 1 & -5\\ 6 & -4 & 21\\ 4 & 5& -26\\ 2 & \color{}{-9} & \color{}{47}\\ 0 & 23 & -120 \end{array}$$