discrete mathematics - How do I properly do back substitution and put equations into the form of Bezout's theorem after using the Euclidean Algorithm?

For some problems, even longer ones, I've been able to see the pattern and properly do back substitution to bring a series of equations I've derived using the Euclidean algorithm to the form of Bezout's theorem:

$sa+tm$

Where $s$ and $t$ are parameters.

But, on some problems I get stuck and have no idea how to move forward.

For example, starting from finding the $gcd(3454,4666)$:

Using the Euclidean Algorithm I find:

$4666 = 3454 * 1 + 1212$ ------------- $1212 = 4666 - 3454 * 1$

$3454 = 1212 * 2 + 1030$ ---------------- $1030 = 3454 - 1212 * 2$

$1212 = 1030 * 1 + 182$ ----------------- $182 = 1212 - 1030 *1$

$1030 = 182 * 5 + 120$ ------------------ $120 = 1030 - 182 * 5$

$182 = 120 * 1 + 62$ --------------------- $62 = 182 - 120 * 1$

$120 = 62 * 1 + 58$ ---------------------- $58 = 120 - 62*1$

$62 = 58 * 1 + 4$ ------------------------ $4 = 62 - 58 * 1$

$58 = 4 * 14 + 2$ ------------------------ $2 = 58 - 4 * 14$

For my first step I substitute for the $4$ :

$2 = 58 - (62 - 58) * 14$

Where do I go from here? What are some general strategies to solve problems of this form? I'm having an inordinately hard time with some of these problems, but find others trivial--what is going on? What should I look out for when approaching problems of this type?

If you would like me to clarify content, please ask me such and I will edit accordingly. Thank you for taking the time to read this!

Answer

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. Below is the computation in your example - so simple that it can be done purely mentally in a few minutes. Here we use least magnitude remainders to speed it up, e.g. $\bmod 1212\!:\,\ 3454\equiv 1030\equiv -182$.

$$\rm\begin{eqnarray} [\![0]\!]\quad \color{}{4666}\ &=&\,\ \ \ 1&\cdot& 4666\, +\ 0&\cdot& 3454 \\ [\![1]\!]\quad \color{}{3454}\ &=&\,\ \ \ 0&\cdot& 4666\, +\ 1&\cdot& 3454 \\ \color{}{[\![0]\!]\ -\,\ [\![1]\!]}\, \rightarrow\, [\![2]\!]\quad \color{}{1212}\ &=&\,\ \ \ 1&\cdot& 4666\, -\ 1&\cdot& 3454 \\ \color{}{[\![1]\!]-3\,[\![2]\!]}\,\rightarrow\,[\![3]\!]\ \ \ \color{}{{-}182}\ &=&\, {-}3&\cdot& 4666\, +\, 4&\cdot& 3454 \\ \color{}{[\![2]\!]+7\,[\![3]\!]}\,\rightarrow\,[\![4]\!]\ \ \ \ \ \color{}{{-}62}\ &=& {-}20&\cdot& 4666\, +\color{}{27}&\cdot& \color{}{3454}\\ \color{}{[\![3]\!]-3\,[\![4]\!]}\,\rightarrow\,[\![5]\!]\qquad\ \ \color{}{4}\ &=&\, \ \ 57&\cdot& 4666\, -77&\cdot& 3454 \\ \color{}{[\![4]\!]\!+\!15[\![5]\!]}\,\rightarrow\,[\![6]\!]\quad\ \ \, \color{}{{-}2}\ &=&\ \ 835&\cdot& 4666\, {-}1128&\cdot& 3454 \\ \end{eqnarray}\qquad$$

Negating the final equation yields the Bezout equation for the gcd $= 2$.

As an optimization we can omit one of the RHS columns, it being computable from the other, e.g. $1128 = ((835\cdot 4666)+2)/3454$. Then the equations may be viewed in fractional form. But it is best to master the above explicit equational form before proceeding to the optimizations.