Bézout's identity (or Bézout's lemma) is the following theorem in elementary number theory:
For nonzero integers and , let be the greatest common divisor . Then, there exist integers and such that
This simple-looking theorem can be used to prove a variety of basic results in number theory, like the existence of inverses modulo a prime number.
In particular, if and are relatively prime integers, we have and by Bézout's identity, there are integers and such that
For small numbers and , we can make a guess as what numbers work. For example, in solving , we see that . However, in solving , it is much harder to guess what the values are.
The algorithm of finding the values of and is as follows: We will illustrate this with the example of
1) Apply the Euclidean algorithm on and , to calculate
2) Work backwards and substitute the numbers that you see:
Find a pair of integers such that
It is somewhat hard to guess that would be a solution. Let's see how we can use the ideas above.
First, we perform the Euclidean algorithm to get
As such, this gives us
Given integers and , describe the set of all integers that can be expressed in the form for integers and .
Let . We show that any integer of the form , where is an integer, can be expressed as for integers and . We already know that this condition is a necessary condition, so to show that it is sufficient, Bézout's lemma tells us that there exists integers and such that . Therefore,
As this problem illustrates, every integer of the form is a multiple of .
Show that if and are integers such that and , then
By Bézout's identity, there are integers such that and integers such that . By taking the product of these equations, we have
Now, observe that divides the right hand side, implying must also divide the left hand side. Since is the only integer dividing the left hand side, this implies .
Similarly, Bézout's identity can be used to prove the following lemmas:
- If and are integers such that and , then .
- If and are integers such that , and , then
Show that if and are integers such that , then there exists an integer such that .
Since , Bézout's identity implies that there exists integers and such that . Then
In particular, this shows that for prime and any integer , there exists an integer such that .
The proof of Bézout's identity uses the property that for nonzero integers and , dividing by leaves a remainder of strictly less than and . Then by repeated applications of the Euclidean division algorithm, we have
where the is the last nonzero remainder in the division process. Now, as illustrated in the example above, we can use the second to last equation to solve for as a combination of and . Unfolding this, we can solve for as a combination of and , etc. until we eventually write as a linear combination of and . Since is the last nonzero remainder in the division process, it is the greatest common divisor of and , which proves Bézout's identity.