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{align} 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{align}\]

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