Bezout's Identity

Before making a blog post on Smith Normal Form, I want to step back and look at an identity that many of you probably know or think is obvious. This is, as the title suggests, Bezout's Identity. Additionally, I am trying to figure out a way to put LaTeX in these entries and I haven't quite gotten it yet, so this gives me something to write about without trying to format matrices in text format.

Bezout's Identity states that for any two integers, a and b, if g is their greatest common divisor then there exist integers x and y such that ax + by = g. A consequence of this fact is that the set of possible values for ax + by for any integers x and y is simply the set of multiples of g, since g clearly divides ax + by and Bezout's identity guarantees a construction for any multiple (just multiply x and y by the same number). Let us quickly prove this identity.

Let us induct on pairs (a,b) by the magnitude of b. If |b| = 0, then g = a, x = 1, and y = 0, so our base case is done. Now suppose we know Bezout's identity is true for all pairs with |b| < k. We will establish the identity for a pair (a,b) with |b| = k. Write a = qb + r with 0 <= r < |b| = k. Then notice that gcd(a,b) = gcd(b,r). Thus by the inductive hypothesis there are integers x' and y' with bx' + ry' = g, but bx' + ry' = bx' + (a - qb)y' = b(x'- qy') + ay' = g, establishing the identity for a pair (a,b) with b = |k| and completing our induction.

This proof has the added benefit of providing us with an algorithm to compute these coefficients. Let us consider the example of a=73, b=17. We start by writing out the division algorithm repeatedly as we would to compute the gcd:

73 = 4*17 + 5
17 = 3*5 + 2
5 = 2*2 + 1

Now we start from the bottom and write them in the following way:

1 = 5 - 2*2
= 5 - 2*(17 - 3*5) = 7*5 - 2*17
= 7 * (73 - 4*17) - 2*17 = 7* 73 - 30*17

So our coefficients are 7 and -30. This algorithm is also very nice for computing modular inverses. Notice at the end that if we take our entire equation modulo 73, we immediately have that the inverse of 17 is -30, or 43. However, this algorithm, being recursive, is not optimal for a computational method due to the need to remember each step. Because of this, I want to show you another algorithm to compute these coefficients.

We will begin exactly the same as before, using the division algorithm repeatedly until we reach the gcd.

73 = 4*17 + 5
17 = 3*5 + 2
5 = 2*2 + 1

But now, instead of working our way up from 1, we're going to work our way down toward 1, writing the equations as follows:

5 = 73 - 4*17
2 = 17 - 3*5 = 17 - 3*(73 - 4*17) = 13*17 - 3*73
1 = 5 - 2*2 = (73 - 4*17) - 2*(13*17 - 3*73) = 7*73 - 30*17

Notice that we arrived at the exact same answer as before, with coefficients of 7 and -30. In general, when working down only the last two results are necessary, similar to how when you compute Fibonacci numbers you only need to keep the last two in order to compute the next one. This trick means that to compute these coefficients only a constant amount of memory is necessary, although possibly a logarithmic amount of time.

Hopefully the example of 17 and 73 is illustrative enough, I don't feel like writing out a formal algorithm right now, but as an exerpt from my code, here is the function to compute the gcd of two numbers and the coefficients for Bezout's Identity.

int gcd(int a, int b, int& x, int& y) {
 int ax=1, ay=0, bx=0, by=1;
 while(b != 0) {
  int q = a/b, r = a%b;
  int tx = ax - q*bx, ty = ay-q*by;
  a = b;
  b = r;
  ax = bx;
  ay = by;
  bx = tx;
  by = ty;
 }
 x = ax;
 y = ay;
 if(a < 0) {
  a = -a;
  x = -x;
  y = -y;
 }
 return a;
}

You can see all the code that I've written so far at http://github.com/bhamrick/csl.