Skip to main content
🔗

Section 2.4 The Bezout Identity

🔗

Subsection 2.4.1 Backwards with Euclid

🔗
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.

🔗
Definition 2.4.1. Bezout identity.

A representation of the gcd d of a and b as a linear combination ax+by=d of the original numbers is called an instance of the Bezout identity. (This representation is not unique.)

🔗
It is worth doing some examples 1 . Perhaps you already have gotten one, probably by trial and error. For instance,

6=−2⋅60+3⋅42.
For convenience, all examples will be in the form \(d=xa+yb\text{,}\) putting the coefficients first, even though we state this in the other order. The habit of using the letters \(a,b,d\) and alphabetical order is too hard to break.

🔗
The third characterization in Theorem 2.2.4 implies that doing this is always possible; gcd(a,b)=ax+by for some integers x and y. Doing the Euclidean algorithm backwards is one way to obtain this.

🔗
Example 2.4.2.

Sometimes it helps visually when starting to write the Euclidean algorithm down one side of a table, and then go 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.

8=1⋅5+3 1⋅8−1⋅5=3 1=2⋅3−1⋅5=2⋅(8−1⋅5)−1⋅5=2⋅8−3⋅5
5=1⋅3+2 1⋅5−1⋅3=2 1=1⋅3−1⋅2=1⋅3−1⋅(5−1⋅3)=2⋅3−1⋅5
3=1⋅2+1 1⋅3−1⋅2=1 1=1⋅3−1⋅2
2=2⋅1+0 Go up this column...

So 1=2⋅8−3⋅5, or 2⋅8+(−3)⋅5.

🔗
Example 2.4.3.

Usually students need a couple of examples of this to get the way this works, so here is another one. Let's do it with the gcd of 60 and 42.

60=1⋅42+18 1⋅60−1⋅42=18 6=1⋅42−2⋅18=1⋅42−2⋅(60−1⋅42)
42=2⋅18+6 1⋅42−2⋅18=6 6=1⋅42−2⋅18
18=3⋅6+0 Go up this column...

Simplifying 1⋅42−2⋅(60−1⋅42) (the top line on the right), we get 6=3⋅42+(−2)⋅60 again.

🔗
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⋅60+3⋅42, once again.

🔗
Example 2.4.4.

Try to get the xgcd/Bezout identity for gcd(135,50) using this algorithm. You should get 5=3⋅135+(−8)⋅50. Can you get another one a different way?

Try the following Sage cell to check that it works.

🔗
Sage note 2.4.5. Remind how to get list elements.

Do you remember what the [1] means? What do you think the [2] means in this context?

🔗
Example 2.4.6.

Try to get the xgcd/Bezout identity for gcd(1415,1735) using this algorithm. Hopefully you get 5=103⋅1415+(−84)⋅1735, though it may take a while! The previous example might help you on your way.

🔗
Historical remark 2.4.7. Bezout and friends.

While Étienne Bézout did indeed prove a version of the Bezout identity for polynomials, the basics of using the extended Euclidean algorithm to solve such equations was known in Europe to Bachet de Méziriac (see Historical remark 3.5.2) about four hundred years ago. However, the Indian mathematician Aryabhata about 1500 years ago in his method later called the Kuttaka used essentially the same algorithm, in fact in a manner more amenable to swift and accurate usage than the one we (and most Western texts) use, with a view toward questions such as Theorem 3.1.2.

🔗

Subsection 2.4.2 Proving the final characterization

🔗
The final characterization of the greatest common divisor (Theorem 2.2.4) is that it is the least positive integer which can be written ax+by for integers x,y. Let's prove that now.

🔗
First, we know there are some positive integers which can be written ax+by (just use positive x,y, or negative ones if a or b are negative). So, by the Well-Ordering Principle, we know there is a smallest such positive integer, which we will call c=au+bv. Let's also designate the gcd of a and b to be d.

🔗
By Proposition 1.2.8, any integer which divides a and b divides any ax+by, so it divides au+bv=c. In particular, since d is a divisor of both a and b, it must also divide c. So d≤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≤d. Thus we conclude that d=c.

🔗

Subsection 2.4.3 Other gcd questions

🔗
We mentioned earlier there are many such linear combinations for any given pair a,b. How might we find more than one such representation?

🔗
Example 2.4.8. Using Bezout to get another Bezout.

We used the backwards Euclidean algorithm to see that 6=−2⋅60+3⋅42. Let's use that to get another.

  • Since 6 is itself a divisor of both 60 and 42, let's pick one (the smaller one!), 42, and write it as 42=7⋅6.

  • Then we can really write

    42=7⋅6=7⋅(−2⋅60+3⋅42),

    since after all we just saw that was a way to represent 6!

  • Now we plug this back into the original equation:

    6=−2⋅60+3⋅42=−2⋅60+3⋅(7⋅6)
    =−2⋅60+3⋅(7⋅(−2⋅60+3⋅42))

If we simplify it out, that means 6=−44⋅60+63⋅42, which is indeed correct!

🔗
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.)

🔗

Subsection 2.4.4 Relatively prime

🔗
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.

🔗
Consider the smallest possible greatest common divisor, which is one. Under what circumstances would a and b have gcd(a,b)=1? By our characterization, it is precisely when you can write ax+by=1 for some integers x and y.

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

🔗
Definition 2.4.9. Relatively Prime.

If the greatest common divisor of two numbers is one, we call them relatively prime numbers or coprime numbers.

Later, we will need to have a term for the situation where, in a collection of several integers, all possible pairs are relatively prime. We will call this mutually coprime, coprime in pairs, or an analogous term.

The first is not too hard to prove, if you think in terms of Bezout. It does need a little cleverness.

  • Remember that \(1=ax+by\) for some \(x,y\text{,}\) by definition of being coprime.

  • So \(c=cax+cby\text{.}\)

  • Now write \(c=kb\) and \(c=\ell a\text{,}\) and substitute them in the opposite parts of the previous line.

  • This gives \(c=(kb)ax+(\ell a)by\text{,}\) and \(ab\) definitely divides both parts of this, so it divides the whole thing by our earlier proposition about divisibility.

We leave the second as an exercise (Exercise 2.5.19).

🔗
It's also useful to try to find counterexamples! Can you find an example where gcd(a,b)≠1, a∣c and b∣c, but ab does not divide c? (See Exercise 2.5.20.)