Now, before we get to the third characterization of the gcd, we need to be able to do the Euclidean algorithm backwards. This is sometimes known as the Bezout identity.

It is worth doing some examples. Perhaps you already have gotten one, probably by trial and error. For instance, \begin{equation*}6=60\cdot (-2)+42\cdot 3\; .\end{equation*}

The third characterization in Theorem 2.2.2 implies that doing this is always possible; \(\gcd(a,b)=ax+by\) for some integers \(x\) and \(y\). Doing the Euclidean algorithm backwards gets this.

Sometimes it's good to write the Euclidean algorithm down one side of a table, and then go backwards up the other side of the table to obtain an instance of the Bezout identity. Here's an example with the gcd of 8 and 5; follow it from top left to the bottom and then back up the right side. The middle column provides the necessary rewriting.

This question of the Bezout identity is implemented in Sage as xgcd(a,b), because this is also known as the eXtended Euclidean algorithm.

Or, \(6=-2\cdot 60+3\cdot 42\), as we saw above.

The final characterization of the greatest common divisor (Theorem 2.2.2) is that it is the least positive integer which can be written \(au+bv\) for integers \(u,v\). Let's prove that now.

• Call \(c\) the smallest such \(au+bv\).

• By Proposition 1.2.6, any integer which divides \(a\) and \(b\) divides any such \(au+bv\), so it divides the smallest such \(au+bv=c\). In particular, the gcd of \(a\) and \(b\) (which we'll call \(d\)) divides \(c\). So \(d\leq c\).

• On the other hand, we know from the backward/extended Euclidean algorithm/Bezout identity that \(d\) can be written \(d=ax+by\) for some integers \(x\) and \(y\). Since \(c\) is the smallest such (positive) integer, \(c\leq d\).

• Concluding that \(d=c\) is the only way to avoid a contradiction!

You might also want to do more than one linear combination, for variety. How might we get another such representation?

So, substituting a Bezout identity into itself yields more and more such identities. How many such identities are there? Is there a general form?

Another interesting question is that some gcds of large numbers are very easy to compute. What makes finding \(\gcd(42000,60000)\) so easy? If you're in a classroom, this is a perfect time to discuss.

On a related note, if \(\gcd(a,b)=d\), could you make a guess as to a formula for \(\gcd(ka,kb)\) (for \(k>0\))? Can you prove it in Exercise 2.5.16? (Hint: here is where our original definition or the Bezout version could be useful.)

There is one final thing that the linear combination version of the gcd can give us. It is something you may think is familiar, but which can arise very naturally from the Bezout identity.

When do \(a\) and \(b\) have as greatest common divisor the smallest possible, \(\gcd(a,b)=1\)? From this point of view, it is precisely when you can write \(ax+by=1\) for some integers \(x\) and \(y\).

Think about this, though; it means that you can write any integer as a (linear) combination of \(a\) and \(b\) if their gcd is 1! This is a property I think people would have come up with no matter how the development of mathematics had gone; the pairs of integers such that you can write any number as a combination of them.

It's also useful to try to find counterexamples! Can you find place where \(\gcd(a,b)\neq 1\), \(a\mid c\) and \(b\mid c\), but \(ab\) does not divide \(c\)? (See Exercise 2.5.20.)