Bezout's Identity

Bézout's identity (or Bézout's lemma) is the following theorem in elementary number theory:

For nonzero integers $a$ and $b$, let $d$ be the greatest common divisor $d = \gcd(a,b)$. Then, there exist integers $x$ and $y$ such that

$$ax + by = d.$$

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 $a$ and $b$ are relatively prime integers, we have $\gcd(a,b) = 1$ and by Bézout's identity, there are integers $x$ and $y$ such that

$$ax + by = 1.$$

For small numbers $a$ and $b$, we can make a guess as what numbers work. For example, in solving $3 x + 8 y = 1$, we see that $3 \times 3 + 8 \times (-1) = 1$. However, in solving $2014 x + 4021 y = 1$, it is much harder to guess what the values are.

The algorithm of finding the values of $x$ and $y$ is as follows: $($We will illustrate this with the example of $a = 102, b = 38.)$

1) Apply the Euclidean algorithm on $a$ and $b$, to calculate $\gcd (a,b):$

$$\begin{array} { r l l } 102 & = 2 \times 38 & + 26 \\ 38 & = 1 \times 26 & + 12 \\ 26 & = 2 \times 12 & + 2 \\ 12 & = 6 \times 2 & + 0. \end{array}$$

2) Work backwards and substitute the numbers that you see:

$$\begin{array} { r l l } 2 & = 26 - 2 \times 12 \\ & = 26 - 2 \times ( 38 - 1 \times 26 )\\ & = 3 \times 26 - 2 \times 38 \\ & = 3 \times (102 - 2 \times 38 ) - 2 \times 38 \\ & = 3 \times 102 - 8 \times 38. \end{array}$$

Find a pair of integers $(x,y)$ such that

$$2014 x + 4021 y = 1.$$

---

It is somewhat hard to guess that $x = -1723, y = 863$ would be a solution. Let's see how we can use the ideas above.

First, we perform the Euclidean algorithm to get

$$\begin{array} { r l l} 4021 & = 2014 \times 1 & + 2007 \\ 2014 & = 2007 \times 1 & + 7 \\ 2007 & = 7 \times 286 & + 5 \\ 7 & = 5 \times 1 & + 2 \\ 5 &= 2 \times 2 & + 1.\end{array}$$

As such, this gives us

$$\begin{array} { r l l } 1 & = 5 - 2 \times 2 \\ & = 5 - ( 7 - 5 \times 1 ) \times 2 & = 5 \times 3 - 7 \times 2 \\ & = ( 2007 - 7 \times 286 ) \times 3 - 7 \times 2 & = 2007 \times 3 - 7 \times 860 \\ & = 2007 \times 3 - ( 2014 - 2007 ) \times 860 & = 2007 \times 863 - 2014 \times 860 \\ & = (4021 - 2014 ) \times 863 - 2014 \times 860 & = 4021 \times 863 - 2014 \times 1723. \ _\square \end{array}$$

Given integers $a$ and $b$, describe the set of all integers $N$ that can be expressed in the form $N=ax+by$ for integers $x$ and $y$.

---

Let $d = \gcd(a,b)$. We show that any integer of the form $kd$, where $k$ is an integer, can be expressed as $ax+by$ for integers $x$ and $y$. 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 $x'$ and $y'$ such that $d = ax' + by'$. Therefore,

$$kd = (ak) x' + (bk) y'.$$

As this problem illustrates, every integer of the form $ax + by$ is a multiple of $d$. $_\square$

Show that if $a, b$ and $c$ are integers such that $\gcd(a, c) = 1$ and $\gcd (b, c) = 1$, then $\gcd (ab, c) = 1.$

---

By Bézout's identity, there are integers $x,y$ such that $ax + cy = 1$ and integers $w,z$ such that $bw + cz = 1$. By taking the product of these equations, we have

$$1 = ( ax + cy )( bw + cz ) = ab ( xw ) + c ( axz + bw y + cyz ) .$$

Now, observe that $\gcd(ab,c)$ divides the right hand side, implying $\gcd(ab,c)$ must also divide the left hand side. Since $1$ is the only integer dividing the left hand side, this implies $\gcd(ab, c) = 1$. $_\square$

Similarly, Bézout's identity can be used to prove the following lemmas:

1. If $a, b$ and $c$ are integers such that $a | bc$ and $\gcd (a, b) = 1$, then $a | c$.
2. If $a, b$ and $c$ are integers such that $a | c$, $b | c$ and $\gcd (a, b ) = 1$, then $ab | c.$

Modulo Arithmetic Multiplicative Inverses

Show that if $a$ and $n$ are integers such that $\gcd(a,n)=1$, then there exists an integer $x$ such that $ax \equiv 1 \pmod{n}$.

---

Since $\gcd(a,n)=1$, Bézout's identity implies that there exists integers $x$ and $y$ such that $ax + n y = \gcd (a,n) = 1$. Then

$$1 \equiv ax+ny \equiv ax \pmod{n} .$$

In particular, this shows that for $p$ prime and any integer $1 \leq a \leq p-1$, there exists an integer $x$ such that $ax \equiv 1 \pmod{n}$. $_\square$

The proof of Bézout's identity uses the property that for nonzero integers $a$ and $b$, dividing $a$ by $b$ leaves a remainder of $r_1$ strictly less than $\lvert b \rvert$ and $\gcd(a,b) = \gcd(r_1,b)$. Then by repeated applications of the Euclidean division algorithm, we have

$$\begin{aligned} a &= b x_1 + r_1, && 0 < r_1 < \lvert b \rvert \\ b &= r_1 x_2 + r_2, && 0 < r_2 < r_1\\ & \vdots &&\\ r_{n-1} &= r_{n} x_{n+1} + r_{n+1}, && 0 < r_{n+1} < r_{n}\\ r_n &= r_{n+1}x_{n+2}, && \end{aligned}$$

where the $r_{n+1}$ 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 $r_{n+1}$ as a combination of $r_n$ and $r_{n-1}$. Unfolding this, we can solve for $r_n$ as a combination of $r_{n-1}$ and $r_{n-2}$, etc. until we eventually write $r_{n+1}$ as a linear combination of $a$ and $b$. Since $r_{n+1}$ is the last nonzero remainder in the division process, it is the greatest common divisor of $a$ and $b$, which proves Bézout's identity. $_\square$

• Extended Euclidean Algorithm
• Division