Algorithm to find the coefficient of GCD linear combination?

Question

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?

Answer 1

Once you have found the GCD of two numbers using the Euclidean Algorithm, you can work backwards and find the coefficients. I'll illustrate it with an example.

Find the GCD of 803 and 154, and then express it as a linear combination of 803 and 154. $803 = 5 \centerdot 154 + 33$ call this line (1)

$154 = 4 \centerdot 33 + 22$ call this line (2)

$33 = 1 \centerdot 22 + 11$ call this line (3)

$22 = 2 \centerdot 11 + 0 $

and so the GCD is 11 (the most recent remainder in line (3)). Now we can express 11 as a linear combination of 803 and 154:

$(803, 154) = 11 = 33 - 1 \centerdot 22$ by (3)

$ = 33 - (154 - 4\centerdot 33)$ by (2)

$= 5\centerdot 33 - 154$

$= 5\centerdot (803 - 5 \centerdot 154) - 154$ by (1)

$= 5 \centerdot 803 - 26 \centerdot 154$

$= 5 \centerdot 803 + (-26) \centerdot 154$

and so we have found our coefficients.

Answer 2

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.