<s>[INST] Algorithm to find the coefficient of GCD linear combination? One of the properties of the GCD of two integers is that it can be written as the linear combination of the two, is there an algorithm that can be used to find the coefficients of this linear combination?
 [/INST] The answer of @LonelyMathematician is perfect, but I confess that I have always found this way of describing the action just too confusing. Let’s step back a bit and look at what’s going on. In each step, you start with (dividend, divisor) and get a new pair, (newdividend, newdivisor), where the new dividend is the old divisor, and the new divisor is the remainder, equal to dividend - quotient times divisor. You see that this is a linear relationship expressible by a matrix equation:
\begin{align}
\begin{pmatrix}\text{newdividend}\\ \text{newdivisor}\end{pmatrix}
=
\begin{pmatrix}
0&1\\1&-\text{quotient}
\end{pmatrix}
\begin{pmatrix}\text{dividend}\\ \text{divisor}\end{pmatrix}\,.
\end{align}
Too wordy! Let’s do exactly the same computation as @LonelyMathematician, finding the greatest common divisor of $805$ and $154$. The first step is to say that
\begin{align}
\begin{pmatrix}154\\33\end{pmatrix}
=
\begin{pmatrix}0&1\\1&-5\end{pmatrix}
\begin{pmatrix}803\\154\end{pmatrix}\,.
\end{align}
We didn’t even need to write that out, except maybe to set our doubts to rest. The four matrices have the lower-right entries of $-5, -4, -1, -2$, these are the quotients of the divisions, but the matrices have to be written in the right order, and multiplied out.
\begin{align}
\begin{pmatrix}0&1\\1&-2\end{pmatrix}\begin{pmatrix}0&1\\1&-1\end{pmatrix}
\begin{pmatrix}0&1\\1&-4\end{pmatrix}\begin{pmatrix}0&1\\1&-5\end{pmatrix}=\begin{pmatrix}5&-26\\-14&73\end{pmatrix}\,,
\end{align}
and if we call this two-by-two matrix $A$, we see that
\begin{align}
\begin{pmatrix}11\\0\end{pmatrix}=A\begin{pmatrix}803\\154\end{pmatrix}\,,
\end{align}
in other words, the proper coefficients are found on the top row of $A$, namely $5$ and $-26$.
I think that you’ll agree that this method is very easily programmed.
</s>