Conveniently computing Bézout Coefficients
If you had any courses in mathematics you will probably have encountered the following at some point:
Any introductory course on algebra or number theory usually includes a section about modular arithmetic, where the identity pops up as a straightforward way to determine the multiplicative inverse of any element
for which then clearly
While this shows the usefulness of the Bézout coefficients, it is usually a bit tedious to actually compute them. In lectures you are usually first thaught how to compute the gcd of two numbers by using the Euclidean algorithm, which turns out to be quite simple. But to then compute the Bézout coefficients this algorithm gets extended in a way that forces us to keep track of all intermediary results and to reversely substitute them later. This is known as the extended Euclidean algorithm. Maybe an example is in order to illustrate this; so let’s compute the gcd of
We stop once we reach a remainder of
Now we eliminate
Now eliminate
And finally, eliminate
Thus we can read off the Bézout coefficients
A Better Way
Here is a more convenient and direct way to compute the Bézout coefficients (known as Blankinship’s algorithm [1]). We start with an augmented matrix, similar to what we would do when computing the inverse of a matrix
The left side is initialized as the identity matrix, and the right most column contains the numbers for which we want to compute the gcd. Next, we will focus on executing elementary row operations which have to the effect that they execute the reduction steps of the Euclidean algorithm. Crucially however, we apply these row operations to the whole augmented matrix! If we let
And repeating this until one of the entries in the last column is
You might have spotted that the previously computed Bézout coefficients
Which is simply matrix notation summarising the following two equations:
the last of which is our desired Bézout identity. Note that we did not have to do any tedious reverse substitutions or similar things! The coefficients were simply computed along the way.
Why it works
The above works no matter which numbers we put into the last column of the augmented matrix: At the end of the computation for the gcd, one of the rows on the left of the augmented matrix will always contain the Bézout coefficients. But why does it actually work? In order to justify this, we will prove the following result:
Theorem. For any
Proof. We will do a proof by induction on the product
So assume
So by strong induction there is an invertible matrix
But now note that
Where we put
As a product of invertible matrices,
The above proof implicitly contains an algorithm to compute the matrix
Oh eh… you are still wondering why this is guaranteed to give us the Bézout coefficients? Well let’s write out the matrix equation as:
The first row corresponds to the equation
which shows exactly what we wanted!
Sources
I came across this algorithm here, which in turn cites [1] as the earliest know source. Quite surprisingly this algorithm is not mentioned at all in the wikipedia article on the Bézout identity and at most implicitly alluded to in the one on the extended Euclidean algorithm.
Exercises
- Show that if there is an invertible integer matrix
with , then we must have . - Use 1. to show that if
is invertible, then .
[1] Blankinship, W. A. “A New Version of the Euclidean Algorithm.” Amer. Math. Monthly 70, 742-745, 1963.
Found This Interesing?
Here are some more posts you might like to read next: