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)$
No comments:
Post a Comment