divisibilityeuclidean-algorithm
I'm confused about how to do the extended algorithm. For example, here's the gcd part
gcd(8000,7001)
$$\begin{align}8000 &= 7001\cdot1 + 999\\
7001&=999\cdot 7+8\\
999&=8\cdot 124+7\\
8&=7\cdot 1+1\\
7&=1\cdot 7+0\\
\gcd(8000,7001)&=1\end{align}$$
Now, the extended algorithm
$$\begin{align}1 &= 8 – 1\cdot7\\
&= 8 – 1\cdot(999 – 8\cdot124)\\
&= -1\cdot999 + 8\cdot125\end{align}$$
How do you get this 8*125 from the previous line?
For an (iterative) implementation it is easier to compute the inverse resp. the Bezout coefficients while going down.
You start with $0·497 \equiv r_0=899\mod899$ and $1·497 \equiv r_1=497\mod899$ and apply the same sequence of computations as to the remainder to the quotient sequence starting with $u_0=0, u_1=1$. \begin{align} r_2&=r_0-1·r_1&\implies u_2&=u_0-1·u_1=-1 &:&&-1·497 &\equiv r_2=402\mod899 \\ r_3&=r_1-1·r_2&\implies u_3&=u_1-1·u_2=2 &:&&2·497 &\equiv r_3=95\mod899 \\ r_4&=r_2-4·r_3&\implies u_4&=u_2-4·u_3=-9 &:&&-9·497 &\equiv r_4=22\mod899 \\ r_5&=r_3-4·r_4&\implies u_5&=u_3-4·u_4=38 &:&&38·497 &\equiv r_5=7\mod899 \\ r_6&=r_4-4·r_5&\implies u_6&=u_4-3·u_5=-123 &:&&-123·497 &\equiv r_6=1\mod899 \end{align} Thus the inverse is $-123$ or in the same equivalence class $899-123=776$
Hopefully this layout for the algorithm will help:
Best Answer
$\begin{eqnarray}\!\text{By the distributive law} && \,8\:\!\ \overbrace{ -\, 1\cdot(999\,-\,8\cdot 124)}^{\textstyle -1\,(a\!-\!b) = -a\! +\! b\ }\\ &=&\ 8\cdot\color{#c00}1\, -\, 999\, +\, 8\cdot\color{#c00}{124}\\ &=&\ 8\cdot\color{#0a0}{ 125} - 999\ \ \,{\rm by}\ \ \color{#c00}{124 + 1} = \color{#0a0}{125}\end{eqnarray}$
This common "$\rm\color{#90f}{back}$-substitution" extended Euclidean gcd algorithm is notoriously error-prone. Better, this $\rm\color{#90f}{forward}$ method is simpler to compute and easier to remember. It keeps track of each remainder's expression as a linear combination of the gcd arguments. Here we get the table below, where each line $\,\ a\ \ b\ \ c\ \,$ means $\ a = 8000\, b + 7001\, c.\ $
$\qquad\quad\, \begin{array}{rrr} [\![1]\!]\ \ \ \ 8000 & 1 & 0\\ [\![2]\!]\ \ \ \ 7001 & 0 & 1\\ [\![1]\!]\:\!\ -\:\!\ 1\,[\![2]\!]\,\to\,[\![3]\!] \ \ \ \ \ \ 999 & 1 & -1\\ [\![2]\!]\ \:\!-\:\!\ 7\,[\![3]\!]\,\to\,[\![4]\!]\ \ \ \ \ \ \ \ \ \ 8 & -7& 8\\ [\![3]\!]\!-\!125\,[\![4]\!]\,\to\,[\![5]\!]\ \ \ \ \ \ \ {-}1 & \!\!\color{#c00}{876} & \!\!\!\color{#0a0}{-1001}\\ \end{array}$
Thus the final line implies that: $\,-1 = \color{#c00}{876}(8000)\!\color{#0a0}{-\!1001}(7001)\,\ $ [= negated Bezout equation]
Another example: $ $ we compute $\rm\ gcd(141,19)\,$ as above, with the equations written explicitly
$\qquad\qquad\rm\begin{eqnarray} [\![1]\!]\ \ \ \, \color{#C00}{141}\!\ &=&\,\ \ 1&\cdot& 141\, +\ 0&\cdot& 19 \\ [\![2]\!]\quad\ \color{#C00}{19}\ &=&\,\ \ 0&\cdot& 141\, +\ 1&\cdot& 19 \\ \color{#940}{[\![1]\!]-7\,[\![2]\!]}\, \rightarrow\, [\![3]\!]\quad\ \ \ \color{#C00}{ 8}\ &=&\,\ \ 1&\cdot& 141\, \color{darkorange}{-\ 7}&\cdot& 19 \\ \color{#940}{[\![2]\!]-2\,[\![3]\!]}\,\rightarrow\,[\![4]\!]\quad\ \ \ \color{#C00}{3}\ &=& {-}2&\cdot& 141\, + \color{#90f}{15}&\cdot& 19 \\ \color{#940}{[\![3]\!]-3\,[\![4]\!]}\,\rightarrow\,[\![5]\!]\quad \color{#C00}{{-}1}\ &=&\,\ \ 7&\cdot& 141\, -\color{#0A0}{ 52}&\cdot& \color{#0A0}{19} \\ {\rm negating}\ \Rightarrow\ \ \ \ \ \ {1}\ &=& {-}7&\cdot& 141\, +\color{#0A0}{ 52}&\cdot& \color{#0A0}{19}\ \ \ \rm [Bezout\ equation] \end{eqnarray}$
The prior Bezout equation $\Rightarrow 141^{-1}\equiv \color{c00}{-7}\pmod{\!19},\,$ & $\,\color{#0a0}{19^{-1}\!\equiv 52}\pmod{\!141}\,$ by reducing the Bezout equation $\bmod19\,$ and $\bmod 141\,$ resp., as explained here. Thus we see that using the extended Euclidean algorithm to compute the gcd Bezout equation yields one method of computing modular inverses (and fractions). See here & here for more examples of this and related methods.
Equivalently $\!\bmod 141\!:\ \dfrac{0}{\color{#c00}{141}}\overset{\large\frown}\equiv\dfrac{1}{\color{#c00}{19}}\overset{\large\frown}\equiv\dfrac{\color{darkorange}{-7}}{\color{#c00}8}\overset{\large\frown}\equiv\dfrac{\color{#90f}{15}}{\color{#c00}{3}}\overset{\large\frown}\equiv\dfrac{\color{#0a0}{-52}}{\color{#c00}{-1}}\Rightarrow \color{#0a0}{19^{-1}\equiv 52},\,$ where we used a succinct fractional form of the above extended Euclidean algorithm, which boils down to viewing the above equations $\!\bmod 141.$