I'm taking an "Algebra for Computer Science" course, and the professor briefly touched upon an implementation of the Extended Euclidean algorithm I can't seem to understand right now.
In previous algebra courses I learnt the following:
- Use the euclidean algorithm
- Convert each equation from the form $a = qb + r$ to $r = a - qb$
- Starting from the final equation, of the form: $\gcd(a, b) = a - qb$, substitute $b$ with the previous remainder, then distribute and sum, then repeat. The procedure ends once the form described in Bézout's identity is reached. $$\gcd(a, b) = ... = ua + vb$$
The new lecture notes instead describe a constructive process, based on the following property:
$$ au + bv = m \implies m = (qb + r)u + bv = ru + b(v+qu) $$
We then write a step of Euclid's algorithm as follows:
$$ \gcd(a = qb + r, b \mid u, v) \to \gcd(r, b \mid u, v + qu) \to \gcd (b, r \mid v + qu, u) $$
Until we get to $\gcd (m, 0 \mid l_1(u, v), l_2 (u, v))$ and solve the linear system:
$$ \begin{cases} l_1(u, v) = 1 \\ l_2(u, v) = 0 \end{cases} $$
What I don't understand is the connection between these two methods (or really the intuition of why this second method works), and why this second method should be "easier" (for humans, at least; I do get that recursively constructing a $2\times 2$ matrix and solving a tiny linear system is very simple for a computer, but the professor claimed this method is simply "easier").
We want to find the g.c.d. of two nonzero integers $a,b$ and we suppose that $b\geqslant1$. Let's define a finite sequence $(u_k)_k$ by induction as follows: $u_0=a$, $u_1=b$, and $\bbox[silver,8px]{\forall k\geqslant1\quad u_{k+1}=u_{k-1}-q_ku_k}$, where $q_k$ is the (integer!) quotient in the euclidian division of $u_{k-1}$ by $u_k$.
These are the coefficients of the usual euclidian algorithm. $$\left\{\begin{array}{rcl} \overset{\scriptscriptstyle a}{u_0}&=&q_1\overset{\scriptscriptstyle b}{u_1}+u_2,\\ u_1&=&q_2u_2+u_3,\\ &\vdots&\\ u_{n-1}&=&q_nu_n+\underset{\scriptscriptstyle\gcd(a,b)}{u_{n+1}}, \end{array}\right.$$ where $n+1$ is the first integer $h$ for which $u_h\neq0$, which implies that $u_{n+1}=\gcd(a,b)$.
Also let's define: $M_k=\begin{pmatrix}0&1\\1&-q_k\end{pmatrix},\ k\geqslant1$.
Now we easily check that $\begin{pmatrix}u_k\\u_{k+1}\end{pmatrix} =M_k\begin{pmatrix}u_{k-1}\\u_k\end{pmatrix} =\underbrace{M_kM_{k-1}\ldots M_1}_{P_k}\begin{pmatrix}u_0\\u_1\end{pmatrix}$.
In particular, putting $P_n=\begin{pmatrix}\alpha&\beta\\ \gamma&\delta\end{pmatrix}$, we have $\begin{pmatrix}u_n\\u_{n+1}\end{pmatrix} =P_n\begin{pmatrix}u_0\\u_1\end{pmatrix}$ and finally obtain $\gcd(a,b)=u_{n+1}=\gamma u_0+\delta u_1=\gamma a+\delta b$, which is the desired Bézout relation.
Hence if we write a program along these lines, the only things we have to calculate at step $k\geqslant1$ are $u_{k+1}$, the four coefficients of $P_k=M_kP_{k-1}$, and we can forget about the former values.
Example with $(a,b)=(29,17)$. $$\left\{\begin{array}{rcll} 29&=&1\times17+12,&\quad P_1=M_1=\left(\begin{smallmatrix}0&1\\1&-1\end{smallmatrix}\right)\\[4pt] 17&=&1\times12+5,&\quad P_2=\left(\begin{smallmatrix}1&-1\\-1&2\end{smallmatrix}\right)\\[4pt] 12&=&2\times5+2,&\quad P_3=\left(\begin{smallmatrix}-1&2\\3&5\end{smallmatrix}\right)\\[4pt] 5&=&2\times2+1,&\quad P_4=\left(\begin{smallmatrix}3&-5\\ \color{red}{-7}&\color{red}{12}\end{smallmatrix}\right). \end{array}\right.$$ Conclusion: $1=\gcd(29,17)=-7\times29+12\times17$.