Have you come across those problems about measuring out some amount of water using limited equipment? Here’s an example.
I have two buckets. One, when full, contains 3 litres, the other 5 litres. I have a large quantity of water in the water butt in my garden, and I wish to end up with exactly 17 litres of this water in my pond. Is this possible, just using these two buckets to transfer water? (No part-filled buckets allowed!)
It doesn’t take very long to see that it’s possible. I fill the 3-litre bucket four times, and the 5-litre bucket once: .
What if I only wanted 1 litre in my pond?
That’s slightly trickier, but not too hard. I use the 3-litre bucket twice, then take out 5 litres. In an equation, .
What would happen if I started with a 3-litre bucket and a 6-litre bucket and still wanted to get 1 litre in my pond?
After a bit of experimentation, we might notice that the quantities we can make all seem to be multiples of 3. In fact, we can justify that mathematically. If we add 3-litre buckets and 6-litre buckets (where and are allowed to be negative — we can take water out of the pond), then we get litres in the pond, and that’s certainly a multiple of 3. The problem was that the highest common factor of the capacities was 3, and that doesn’t divide our target amount (1).
What happens if I start with other buckets? It might be that there’s a fairly obvious reason why we can’t make 1 litre: if the highest common factor of the capacities of the two measuring buckets is bigger than 1. But if I give you two buckets where the highest common factor is 1, will you necessarily be able to get 1 litre from them?
Let’s translate what we’d like to do into mathematics. We are given two positive whole numbers, and , say. Those are the capacities of the two buckets. We are told that the highest common factor of and is 1. Then we’d like to know that there are integers and so that . The equation tells us to transfer -buckets and -buckets of water into the pond. Of course, a negative number of buckets translates into removing water from the pond, so we may have to be careful about the order in which we do things (we need water in the pond before we can start removing water!). I’ll let you convince yourself that if we can solve the equation (find and ) then it’s possible.
It turns out that the answer is that it is possible to solve the equation — that’s what Bézout‘s Theorem tells us. Better still, we can give a constructive proof. That is, the proof actually gives us a way to find a water-moving strategy that will give 1 litre.
Finding highest common factors — Euclid’s algorithm
Before we get to the proof, let’s think about how we can find the highest common factor of two numbers. One way would be to find and compare the prime factorisations of the two numbers. That’s fine, but finding prime factorisations can be extremely time-consuming if you’re dealing with large numbers. Fortunately, there is another way: use Euclid‘s algorithm. Let’s see how it works by looking at an example.
Say that we want to find the highest common factor of 121 and 44. (OK, I know, that’s easy, because they’re small numbers. So please temporarily forget that it’s easy, and bear with me. It wouldn’t be as easy if I were using larger numbers!) It seems to me to be quite natural to try to divide 121 by 44. We get
So 121 isn’t divisible by 44. But if I take a number that divides 121 and 44, then it must also divide the remainder 33 (because , if you like). So any common factor of 121 and 44 is also a common factor of 44 and 33, and those are smaller numbers. So let’s play the same game again: divide 44 by 33.
Now let’s try the same thing again: we divide 33 by 11.
We’d like to use these three equations to show that the highest common factor of 121 and 44 is 11. Let’s do this in two stages. First we’ll show that 11 really is a common factor of 121 and 44, and then we’ll show that any common factor of 121 and 44 must divide 11 — that is, 11 is the highest common factor. (Of course, this is all very easy with such small numbers, where we could just check directly, but let’s see how these equations do the work for us.)
Equation (3) tells us that 11 is a factor of 33. Then from equation (2) we see that, since 11 divides the right-hand side, 11 must also divide the left-hand side, 44. Now 11 divides 33 and 44, so 11 divides the right-hand side of equation (1), so 11 also divides the left-hand side, namely 121. We’ve argued that 11 divides both 121 and 44 — it’s a common factor. That’s the first stage done.
Now let’s take any common factor of 121 and 44; we want to show that is a factor of 11. Equation (1) tells us that is a factor of 33. Then equation (2) shows that is a factor of 11. And that’s exactly what we wanted.
By working through the equations twice, once from last to first and once from first to second-last, we showed that the highest common factor of 121 and 44 is 11.
Let’s do another simple example. We’ll find the highest common factor of 31 and 14, using this same algorithm.
Using just the same argument as before (working through the equations twice, once from the last to the first and once from the first to the second-last), we see that the highest common factor is 1. I’ll let you think about the details.
Solving our equation
How does that help us find whole numbers and so that ?
Well, the third equation tells us that . We’ve successfully written 1 as a combination of some integers — but not the right integers!
The second equation gives . Substituting this in gives . That looks slightly more promising: we’ve written 1 as a combination of 3 and 14, and 14 is one of the numbers we’re aiming for. Let’s get rid of the 3.
The first equation gives . Substituting this in gives . Aha! So we can take and , for example. (There are lots of other solutions too, this is just one example. But our aim was only to show that there is a solution, not to find them all.)
Let’s state Bézout’s Theorem formally.
Theorem (Bézout) Let and be integers. Then there are integers and satisfying the equation
if and only if the highest common factor of and is 1 (they are coprime).
How does one prove this?
The “only if” direction was the easy one: we noticed earlier that if there’s a solution to the equation then the highest common factor of and must be 1.
And for the “if” direction one uses Euclid’s algorithm, exactly as we did for the particular example just now. You run Euclid’s algorithm to find the highest common factor of and (which we know is 1), and then use the resulting equations to express 1 in terms of and .
You might like to try this for some pairs of numbers of your own. Try some fairly large numbers — Euclid’s algorithm is very efficient, and doesn’t take very many steps.
I am a fan of Harold Davenport’s The Higher Arithmetic, which has a very readable discussion of Euclid’s algorithm (and various things that can be deduced from it) in Chapter 1. Euclid’s algorithm and Bézout’s theorem are discussed in many introductory number theory books, that just happens to be a personal favourite.
There’s a short series of nice articles about Euclid’s algorithm and its uses on the NRICH website, starting with Euclid’s Algorithm I.