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, and it is worth doing some examples.

The previous exercises may have had one you solved, probably by trial and error. For instance, \[6=60\cdot (-2)+42\cdot 3\; .\]

The third characterization implies that doing this is always possible; \(gcd(a,b)=ax+by\) for some integers \(x\) and \(y\). Euclid backwards does 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 Bezout's 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.

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

Try to get the xgcd/Bezout for \(gcd(1492,1066)\). You should get \(2=-5\cdot 1492+7\cdot 1066\).

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? That will be answered soon.

As another example, what makes finding \(gcd(42000,60000)\) so easy? Let's discuss.

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? (Hint: here is where our original definition or the Bezout version could be useful.)

Now let's prove the final characterization of GCD - namely, the least positive integer which can be written \(au+bv\) for integers \(u,v\).

• Call \(c\) the smallest such \(au+bv\).
• Clearly, 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 by one of the facts above, \(d\leq c\).
• On the other hand, we know from the backward 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\).
• The only way to avoid a contradiction is for \(d=c\)!

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 greatest common divisor 1? From this point of view, it is precisely when you can write \(ax+by=1\) for some integers \(x\) and \(y\). That means, in fact, 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. We call these relatively prime numbers or coprime numbers.

Here are two interesting facts about coprime integers \(a\) and \(b\):

• If \(a|c\) and \(b|c\), then \(ab|c\).
• If \(a|bc\), then \(a|c\).

• Remember that \(ax+by=1\) by definition.
• So \(c=cax+cby\).
• Now write \(c=kb\) and \(c=\ell a\), and substitute them in the opposite parts of the previous line.
• This gives \(c=(kb)ax+(\ell a)by\), and \(ab\) definitely divides both parts of this, so it divides the whole thing by our earlier proposition about divisibility.

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