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,
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\text{.}\) 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\cdot 5+3\) | \(1\cdot 8-1\cdot 5=3\) | \(1=2\cdot 3-1\cdot 5=2\cdot (8-1\cdot 5)-1\cdot 5=2\cdot 8-3\cdot 5\) |
| \(5= 1\cdot 3+2\) | \(1\cdot 5- 1\cdot 3=2\) | \(1=1\cdot 3-1\cdot 2=1\cdot 3-1\cdot(5-1\cdot 3)=2\cdot 3-1\cdot 5\) |
| \(3=1\cdot 2+1\) | \(1\cdot 3-1\cdot 2=1\) | \(1=1\cdot 3-1\cdot 2\) |
| \(2=2\cdot 1+0\) | Go up this column... |
So \(1=2\cdot 8-3\cdot 5\text{,}\) or \(2\cdot 8+(-3)\cdot 5\text{.}\)
Example 2.4.3.
Usually students need a couple example 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\cdot 42+18\) | \(1\cdot 60-1\cdot 42=18\) | \(6=1\cdot 42- 2\cdot 18=1\cdot 42- 2\cdot (60-1\cdot 42)\) |
| \(42= 2\cdot 18+6\) | \(1\cdot 42- 2\cdot 18=6\) | \(6=1\cdot 42- 2\cdot 18\) |
| \(18=3\cdot 6+0\) | Go up this column... |
Simplifying \(1\cdot 42- 2\cdot (60-1\cdot 42)\) (the top line on the right), we get \(6=3\cdot 42+(-2)\cdot 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\cdot 60+3\cdot 42\text{,}\) 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\cdot 135+(-8)\cdot 50\text{.}\) 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\cdot 1415+(-84)\cdot 1735\text{,}\) 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\text{.}\) Let's prove that now.
First, we know there are some positive integers which can be written \(ax+by\) (just use positive \(x,y\)). So we know there is a smallest such positive integer, which we will call \(c=au+bv\text{.}\) Let's also designate the gcd of \(a\) and \(b\) to be \(d\text{.}\)
By Proposition 1.2.8, any integer which divides \(a\) and \(b\) divides any \(ax+by\text{,}\) so it divides \(au+bv=c\text{.}\) In particular, since \(d\) is a divisor of both \(a\) and \(b\text{,}\) it must also divide \(c\text{.}\) So \(d\leq c\text{.}\)
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'\text{.}\) Since \(c\) is the smallest such (positive) integer, \(c\leq d\text{.}\) Thus we conclude that \(d=c\text{.}\)
Subsection 2.4.3 Other gcd questions
We mentioned earlier there are many such linear combinations for any given pair \(a,b\text{.}\) 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\cdot 60+3\cdot 42\text{.}\) 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\cdot 6\text{.}\)
-
Then we can really write
\begin{equation*} 42=7\cdot 6=7\cdot (-2\cdot 60+3\cdot 42)\text{,} \end{equation*}since after all we just saw that was a way to represent \(6\text{!}\)
-
Now we plug this back into the original equation:
\begin{equation*} 6=-2\cdot 60+3\cdot 42=-2\cdot 60+3\cdot (7\cdot 6) \end{equation*}\begin{equation*} =-2\cdot 60+3\cdot (7\cdot (-2\cdot 60+3\cdot 42)) \end{equation*}
If we simplify it out, that means \(6=-44\cdot 60+63\cdot 42\text{,}\) 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\text{,}\) 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\text{?}\) By our characterization, it is precisely when you can write \(ax+by=1\) for some integers \(x\) and \(y\text{.}\)
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\text{!}\) 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.
Proposition 2.4.10.
Here are two interesting facts about coprime integers \(a\) and \(b\text{:}\)
If \(a\mid c\) and \(b\mid c\text{,}\) then \(ab\mid c\text{.}\)
If \(a\mid bc\text{,}\) then \(a\mid c\text{.}\)
Proof.
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)\neq 1\text{,}\) \(a\mid c\) and \(b\mid c\text{,}\) but \(ab\) does not divide \(c\text{?}\) (See Exercise 2.5.20.)