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

. (1)

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.

. (2)

Now let’s try the same thing again: we divide 33 by 11.

. (3)

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

### Further reading

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.

August 11, 2009 at 12:38 pm

Thanks for a very nice article. The following related questions sprang to my mind when reading it, and I thought others might like to think about them as well.

Suppose you have two types of coin available to you: one worth 3p and

one worth 5p. What amounts of money could you then obtain? Which

amounts would it not be possible to obtain? What if the coins were

worth 4p and 6p instead? Can you use Bezout’s theorem to show that,

given coins worth coprime amounts h and k, one can make any amount

except for a finite number of exceptions?

August 11, 2009 at 1:41 pm

There was a point a while back when first class stamps cost 28p, and second class 21p. I think that the Royal Mail had failed to consider what prices it would be possible to make with such stamps!

October 13, 2009 at 9:29 pm

[…] as a combination of s and s — geometrically it does not correspond to a straight line). In Bezout’s equation (which is linear), if we have one solution then we can symmetrically tweak the two variables to […]

October 21, 2009 at 6:12 pm

[…] of a proof. Take a non-zero remainder (mod ), say . Then and are coprime (why?), so Bézout’s theorem says that there are integers and so that . Now is an inverse of (mod ) (why?). There a full […]

November 21, 2009 at 10:35 pm

[…] going to stick with that definition and show you how to prove the lemma. I’m going to use Bézout’s theorem, so if you don’t know that result you might like to read about it now (and then come back […]

December 28, 2009 at 8:37 am

I like this article.

When I was reading the part about how Euclid’s algorithm could help giving a solution to 31m + 14n = 1, I was thinking whether it would be possible to find all solutions. That could be done by finding one solution to 31m + 14n = 1, and all integer solutions to 31x + 14y = 0. To find all integer solutions to ax=by, where a & b are known integers, simplify the coefficients until they are coprime, and take multiples of the coefficient on the other side for values of x and y.

The smallest possible +ve value of a1x1+a2x2+…+anxn=(a1,…, an). By using Euclid’s algorithm several times at least one way of choosing the x1, x2, … xn values can be found. ∴a1x1+a2x2+…+anxn must be and can always be expressed as a multiple of (a1,…, an). Now that I can find all integer solutions to 31m + 14n = 1, it might also be possible to find all integer solutions to a1x1+a2x2+…+anxn=k, where k can be any multiple of (a1,…, an),a1,..an are known integers and x1,…,xn are unknowns.

Euclid’s algorithm can always give a solution to a1x1+a2x2+…+anxn=k, so the key step in finding all solutions is to find all solutions to a1x1+a2x2+…+anxn=0. If I want to solve, say 3x+7y+28z=0, 7y+28z must be a multiple of and can be any multiple of (7,28) so it becomes 3x+7w=0. I can solve this for all integer solutions and can solve 7w=7y+28z for all integer solutions. The way to solve 3x+7y+28z=0 is easily generalised so I have found the way to solve a1x1+a2x2+…+anxn=k for n=3 and this is built on the way to solve it when n=2. And with a similar argument it can be solved for all integer solutions for n=4 by assuming that it can be solved for n=3. In general, if it can be solved for n=k, it can be shown that it can be solved for n=k+1. Therefore it is proved by induction that a1x1+a2x2+…+anxn=k, (where k can be any multiple of (a1,…, an)) can be solved for all integer values. I have in principle found the all possible ways

to “make up” all possible integers with known integers.

The initial thinking was how to find all integer values for 31m + 14n = 1, but I have carried a long way and arrived at a conclusion which seems irrelevent to Bézout’s Theorem. Are my reasoning and my conclusion correct?

In principle I can solve a1x1+a2x2+…+anxn=k, (where k can be any multiple of (a1,…, an)) for all integer values, but it is laborious and tedious and the solutions, I think, would be expressed as very complex expressions. Is there a more efficient way? Thanks.

December 30, 2009 at 10:25 pm

Your strategy for finding all integer solutions to is fine, although I don’t think that you’ve justified it in your post. (I realise that might have just been you saving yourself some typing!) The relevance of Bézout’s theorem is that it gives you a way to find some solution to , from which you can build all other solutions.

Sure, you can do this with more variables, but I don’t think that it’s conceptually very interesting (in the sense that it doesn’t really use any more ideas than the strategy for two variables).

April 18, 2010 at 10:46 pm

[…] of the week to make it quite easy. Since 11 and 13 are coprime (have highest common factor 1), Bézout’s theorem tells us that there are some integers and so that . Now can we see a number that’s one […]

July 12, 2010 at 7:55 am

[…] is to use Bézout’s theorem. That tells us that since and are coprime, there are integers and such that . Interpreting […]

August 18, 2010 at 7:57 am

[…] certainly not obvious that the condition is sufficient). I wrote about this phenomenon in Theorem 1 on this blog (for example). I think it’s pretty interesting that the condition is indeed […]

September 8, 2010 at 8:13 pm

[…] you stare at it for a bit, you might realise that this process has a lot in common with Euclid’s algorithm, and in fact it really is the same thing in disguise. The proof that Euclid’s algorithm […]

October 7, 2011 at 12:50 pm

[…] Proposition 3: Euclid’s algorithm for finding the highest common factor of two natural numbers, including why it finds the hcf and why it always terminates. (You might like to look back at that picture at the end of the post from Lecture 0. How much can you extract from that one picture?) […]

August 16, 2012 at 11:47 am

[…] the first lecture, we talked about Euclid‘s algorithm and Bézout‘s lemma. In the second, we mentioned the Fundamental Theorem of Arithmetic, and we learned about modular […]

August 15, 2013 at 9:11 am

[…] the first lecture, we talked about Euclid‘s algorithm and Bézout‘s lemma. In the second, we mentioned the Fundamental Theorem of Arithmetic, and we learned about modular […]

October 11, 2013 at 11:18 am

[…] Theorem 4 (Bézout): Let , and be natural numbers. There are integers and such that if and only if . The easy direction is easy. The harder direction follows from running Euclid’s algorithm and working backwards. […]

May 23, 2014 at 6:22 am

Strictly speaking this is not Bézout’s Theorem. It’s called Bézout’s Lemma or Bézout’s Identity. Bézout’s Theorem is quite different.

March 6, 2015 at 11:06 am

[…] written about Bézout’s lemma (or theorem or whatever) before on this blog. I’ve also written about the Chinese Remainder […]

March 3, 2016 at 10:09 am

[…] written about Bézout’s lemma (or theorem or whatever) before on this blog. I’ve also written about the Chinese Remainder […]