Theorem 1: Bézout’s Theorem

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: 17 = 4\times 3 + 5.

 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, 1 = 2 \times 3 - 5.

 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 m 3-litre buckets and n 6-litre buckets (where m and n are allowed to be negative — we can take water out of the pond), then we get 3m+6n=3(m+2n) 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, h and k, say.  Those are the capacities of the two buckets.  We are told that the highest common factor of h and k is 1.  Then we’d like to know that there are integers m and n so that hm+kn=1.   The equation tells us to transfer m h-buckets and n k-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 m and n) 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

121 = 2\times 44 + 33.          (1)

So 121 isn’t divisible by 44.  But if I take a number d that divides 121 and 44, then it must also divide the remainder 33 (because 33 = 121 - 2\times 44, 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.

44 = 33 + 11.          (2)

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

33 = 3\times 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 d of 121 and 44; we want to show that d is a factor of 11.  Equation (1) tells us that d is a factor of 33.  Then equation (2) shows that d 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.

31 = 2\times 14 + 3

14 = 4\times 3 + 2

3 = 2+1

2=2\times 1

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 m and n so that 31m + 14n = 1?

Well, the third equation tells us that 1 = 3- 2.  We’ve successfully written 1 as a combination of some integers — but not the right integers!

The second equation gives 2 = 14 - 4\times 3.  Substituting this in gives 1 = 3-(14-4\times 3) = 5\times 3 - 14.  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 3=31-2\times 14.  Substituting this in gives 1=5(31-2\times 14)-14=5\times 31-11\times 14.  Aha!  So we can take m=5 and n=-11, 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 h and k be integers.  Then there are integers m and n satisfying the equation

hm+kn=1

if and only if the highest common factor of h and k 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 h and k 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 h and k (which we know is 1), and then use the resulting equations to express 1 in terms of h and k.

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.

Advertisements

18 Responses to “Theorem 1: Bézout’s Theorem”

  1. Olof Says:

    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?

  2. theoremoftheweek Says:

    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!

  3. Theorem 9: Bachet’s duplication formula « Theorem of the week Says:

    […] 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 […]

  4. Theorem 10: Lagrange’s theorem in group theory « Theorem of the week Says:

    […] 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 […]

  5. Theorem 13: the fundamental theorem of arithmetic « Theorem of the week Says:

    […] 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 […]

  6. Chuwei Zhang Says:

    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.

  7. theoremoftheweek Says:

    Your strategy for finding all integer solutions to 31m + 14n = 1 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 31m + 14n = 1, 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).

  8. Theorem 24: the Chinese remainder theorem « Theorem of the week Says:

    […] 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 […]

  9. Theorem 31: the non-zero integers (mod p) form a group under multiplication « Theorem of the week Says:

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

  10. Theorem 34: Hall’s marriage theorem « Theorem of the week Says:

    […] 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 […]

  11. Theorem 35: the best rational approximations come from continued fractions « Theorem of the week Says:

    […] 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 […]

  12. Number Theory: Lecture 1 « Theorem of the week Says:

    […] 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?) […]

  13. Sutton Trust summer school 2012 « Theorem of the week Says:

    […] 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 […]

  14. Sutton Trust summer school 2013 | Theorem of the week Says:

    […] 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 […]

  15. Number Theory: Lecture 1 | Theorem of the week Says:

    […] 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. […]

  16. Mark Says:

    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.

  17. Groups and Group Actions: Lecture 6 | Theorem of the week Says:

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

  18. Groups and Group Actions: Lecture 6 | Theorem of the week Says:

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: