Today we will learn a very beautiful result in number theory, the Bézout's lemma, it is stated as follows.
Bézout's Lemma. Let $a$ and $b$ be two integers and $d$ their greatest common divisor. Then there exist two integers $x$ and $y$ such that $$d = a x + b y.$$
To determine the values of $x$ and $y$ in the above Bézout's equation, we can use the Euclidean algorithm. We will learn about this algorithm in our next post.
First, let us look at some examples.
- $a = 5$, $b = 7$, $d=\gcd(5, 7)=1$, we have the following Bézout's equation $${\bf 1} = {\bf 5} \times 3 + {\bf 7} \times (-2).$$
- $a = 16$, $b = 30$, $d=\gcd(16, 30)=2$, $${\bf 2} = {\bf 16} \times 2 + {\bf 30} \times (-1).$$
- $a = 45$, $b = 155$, $d=\gcd(45, 155)=5$, $${\bf 5} = {\bf 45} \times 7 + {\bf 155} \times (-2).$$
Proving Bézout's Lemma
Let $a$ and $b$ be two integers and $d$ their greatest common divisor. Then there exist two integers $x$ and $y$ such that $$d = a x + b y.$$
If $a=0$ then $d=b$, and the lemma is obviously correct. So we only need to prove for the case $a \neq 0$ and $b \neq 0$.
Let $S$ be the set of all integers of the form $ax+by$ $$S = \{ ax + by : x \in Z, ~y \in Z \}.$$
We make the following observations.
Observation 1. The numbers $0$, $a$, $b$ belong to the set $S$.
From observation 1, $S$ contains non-zero integers. So we can choose from the set $S$ a non-zero integer $s$ such that the value of $|s|$ is minimum.
Since $s$ is a member of the set $S$, we can write $s$ in the form $$s = a ~x_s + b ~y_s.$$
Observation 2. $s$ divides any number in the set $S$.
Indeed, if we take any member $u = a x_u + b y_u$ of the set $S$, and divide it by $s$, let $q$ be the quotient and $r$ the remainder. We will prove that $r=0$.
The remainder $r$ satisfies the condition $$0 \leq |r| < |s|.$$
We have $$u = sq + r,$$ and thus, $$r = u - sq = (a x_u + b y_u) - (a x_s + b y_s)q = (x_u - x_s q)a + (y_u - y_s q)b.$$
So $r$ is a member of the set $S$. But $0 \leq |r| < |s|$, and $s$ is a non-zero number chosen from $S$ so that the value of $|s|$ is minimum, therefore, $r=0$. This shows that $u$ is divisible by $s$.
Observation 3. $s$ is a divisor of $d$.
Indeed, by observation 2, $s$ divides any member of the set $S$, so in particular, $s$ divides $a$ and $b$. But $d$ is the greatest common divisor of $a$, $b$, therefore, $s$ must be a divisor of $d$.
Observation 4. $d$ is a divisor of $s$.
Indeed, since $d$ divides $a$ and $b$, so $d$ must divide any number of the form $a x + b y$. In particular, $d$ divides $s$.
From the last two observations, it follows that $d = \pm s$, so $d$ is of the form $a x + b y$, and the lemma is proved.
Some applications of Bézout's lemma
Problem. Find all integers $a$ and $b$ such that $5~a + 7~b = 1$
Solution. The equation $5~a + 7~b = 1$ looks like the Bézout's equation for two numbers $5$ and $7$.
Since the greatest common divisor of $5$ and $7$ is $1$, by Bézout's lemma, there exist two integers $x$ and $y$ such that $$1 = 5 ~x + 7 ~y$$
Trying a few values, we see that $x=3$, $y=-2$ satisfy the equation. So we can write $$1 = 5 \times 3 + 7 \times (-2)$$
Subtract the equation $5~a + 7~b = 1$ to the above equation side by side, we obtain $$5(a-3) + 7 (b+2) = 0$$
That is $$7(b+2) = 5(3-a)$$
Since $7(b+2)$ is divisible by $5$, $b+2$ is also divisible by $5$. Let $$b+2 = 5s,$$ we have $$b = 5s -2$$ and $$5(3-a) = 7(b+2) = 35s$$
It follows that $$3-a = 7s$$ and thus, $$a = 3-7s$$
In summary, the solution is $a = 3-7s$, $b=5s-2$.
Problem. There are two bottles, one has volume of exactly 500 milliliter and the other one 700 milliliter. Using these two bottles, show how to measure out exactly 100 milliliter of water.
Solution. This problem is of the same spirit as that of the previous one. The main point is to recognize the identity $$1 = 5 \times 3 - 7 \times 2.$$
What we need is to make the 500ml bottle full three times, and pour them out to the 700ml bottle. After pouring out two bottle full of 700ml we will get exactly 100 ml left.
The solution is illustrated in the following figure.
 |
| Getting 100ml by making full three times the 500ml bottle and pouring out to the 700ml, making it two times full |
Let us stop here for now. We will continue our story about Bézout's lemma and Euclidean algorithm in the next post. Hope to see you there.
Homework.
1. Let $a$ and $b$ be two co-prime integers. Prove that there exists an integer $c$ such that $$ac = 1 \pmod{b}.$$
$c$ is called the inverse of $a$ modulo $b$.
2. Find all integer $n$ such that $1000 n - 1$ is divisible by $2013$.
3. Let $a$, $b$, and $c$ be three integers and $d$ their greatest common divisor. Prove that there exist three integers $x$, $y$, $z$ such that $$d = a ~x + b ~y + c ~z .$$