Euclidean algorithm matrix proof

Question

Suppose that $a$ and $b$ are positive integers with $a\geq b$. Let $q_i$ and $r_i$ be the quotients and remainders in the steps of the Euclidean algorithm for $i=1, 2, ..., n$, where $r_n$ is the last nonzero remainder.

Let $Q_i = \begin{bmatrix} q_i & 1 \\ 1 & 0\end{bmatrix}$ and $Q=\prod_{i=0}^{n} Q_i$. Show that $\begin{bmatrix}a \\ b\end{bmatrix} = Q\begin{bmatrix}r_n \\ 0\end{bmatrix}$

I really have no idea how to tackle this. A relevant theorem may be Bezout's Theorem:

gcd$(a, b)$ is the smallest linear combination of $a, b$, that is, $gcd(a,b) = $ min$(sa+tb)$

Answer 1

Note that$$\begin{bmatrix}a\\b\end{bmatrix}=\begin{bmatrix}bq_1+r_1\\b\end{bmatrix}=\begin{bmatrix}q_1&1\\1&0\end{bmatrix}.\begin{bmatrix}b\\r_1\end{bmatrix},$$that$$\begin{bmatrix}b\\r_1\end{bmatrix}=\begin{bmatrix}r_1q_1+r_2\\r_1\end{bmatrix}=\begin{bmatrix}q_2&1\\1&0\end{bmatrix}.\begin{bmatrix}r_1\\r_2\end{bmatrix},$$and so on…

Answer 2

Use induction on the number of steps: if the algorithm starts with \begin{align} a&=q_1b+r_1& \dots&\dots\\ b&=q_2r_1+r_2 & r_{n-2}&=q_n r_{n-1}+r_n\\ &\dots\dots& r_{n-1}&=q_{n+1}r_n \end{align} by the induction hypothesis, we have $$\begin{bmatrix}b\\r_1\end{bmatrix}=\prod_{i=2}^n Q_i, \quad\text{and }\quad\begin{bmatrix}a\\b\end{bmatrix}=Q_1\begin{bmatrix}b\\r_1\end{bmatrix}.$$