elementary number theory - Using Extended Euclidean Algorithm for $85$ and $45$

Apply the Extended Euclidean Algorithm of back-substitution to find the value of $\gcd(85, 45)$ and to express $\gcd(85, 45)$ in the form $85x + 45y$ for a pair of integers $x$ and $y$.

I have no idea what is the difference between the regular EEA and the back-substitution EEA. The only thing that I have been taught is constructing the EEA table, for some values a, b. Can anyone help me explain this? Thanks a ton!

Answer

You’re probably intended to do the substitutions explicitly. You have

$$\begin{align*} 85&=1\cdot45+40\\ 45&=1\cdot40+5\\ 40&=8\cdot5\;. \end{align*}$$

Now work backwards:

$$\begin{align*} 5&=1\cdot45-1\cdot40\\ &=1\cdot45-1\cdot(1\cdot85-1\cdot45)\\ &=(-1)\cdot85+2\cdot45\;. \end{align*}$$

The tabular method is just a shortcut for this explicit back-substitution.