Extended Euclidean Algorithm and Bézout's Identity

In our last lesson, we rigorously proved that the Euclidean Algorithm correctly identifies the greatest common divisor of two integers. We saw that the algorithm's power lies in the fact that $gcd (a, b) = gcd (b, a (mod b))$ , an identity that preserves the GCD while reducing the problem's complexity. Today, we will discover that the steps of this ancient algorithm hold a deeper secret. By tracing them backward, we can uncover a fundamental relationship between two numbers and their GCD.

This relationship is known as Bézout's Identity. It states that for any two integers $a$ and $b$ , their greatest common divisor can always be expressed as an integer linear combination of $a$ and $b$ . That is, there always exist integers $x$ and $y$ such that:

a x + b y = gcd (a, b)

This lesson will focus on both proving this remarkable identity and mastering the constructive method, the Extended Euclidean Algorithm, used to find the coefficients $x$ and $y$ .

1. The Existence of a Solution: A Proof from First Principles

Before we learn how to find the integers $x$ and $y$ , let's first prove that they must always exist. A direct constructive proof by "running the algorithm backward" is possible, but there is a more elegant, non-constructive proof that reveals the deep structure of the integers. This style of argument, which you'll frequently encounter in higher mathematics, uses the Well-Ordering Principle.

Given your interest in first-principles thinking, this proof should be particularly satisfying. It defines a special set and shows that its smallest element must be the GCD.

This proof is powerful because it establishes existence without needing to compute anything. It tells us that the set of all integer linear combinations of $a$ and $b$ is precisely the set of all integer multiples of their GCD. A direct and important consequence is this:

Corollary: If $gcd (a, b) = d$ , then the equation $a x + b y = c$ has integer solutions for $x$ and $y$ if and only if $d$ divides $c$ .

2. Finding the Solution: The Extended Euclidean Algorithm

Now that we are certain a solution exists, how do we find it? The answer lies in the very sequence of divisions we performed in the standard Euclidean Algorithm.

Method 1: Back Substitution

The most direct method is to work backward from the last step of the Euclidean algorithm. You start by writing the GCD (the last non-zero remainder) in terms of the two preceding remainders, and then substitute your way back up the chain until the GCD is expressed in terms of the original numbers.

Let's walk through an example from the resource you just read.

While intuitive, back-substitution can be tedious and prone to algebraic errors with larger numbers. A more systematic approach is needed.

Method 2: The Tabular (Iterative) Method

The Extended Euclidean Algorithm is a more structured method that calculates the coefficients $x$ and $y$ alongside the remainders in the forward direction, eliminating the need for back-substitution.

The core idea is to maintain, at each step $i$ , an identity of the form $r_{i} = s_{i} a + t_{i} b$ , where $a$ and $b$ are the original numbers. The Dartmouth CS notes provide a brilliant explanation of the underlying recursive logic that powers this method.

The recursive logic shown in the Dartmouth PDF can be implemented efficiently using a simple table. The following video demonstrates this popular tabular method. It keeps track of the remainders and the corresponding coefficients at each stage.

GCD, Bezout, and Modular Inverses | The Extended Euclidean Algorithm

This video provides a clear, step-by-step walkthrough of the tabular method.

Watch the segment from this timestamp. The presenter computes 77x + 30y = \text{gcd}(77, 30). Focus on how each new row in the table is calculated from the two preceding rows. Specifically, notice the relationship: r_i = r_{i-2} - q_{i-1} r_{i-1} s_i = s_{i-2} - q_{i-1} s_{i-1} t_i = t_{i-2} - q_{i-1} t_{i-1} These recurrence relations are the core of the iterative algorithm. The video also briefly touches on these general formulas toward the end of the segment.

The entire iterative process can be visualized as a flowchart. Each pass through the loop updates the remainders and the Bézout coefficients until the remainder becomes zero.

This flowchart illustrates the iterative version of the Extended Euclidean Algorithm. Starting with initial coefficients, the algorithm repeatedly calculates the quotient `q` and remainder `r`, and then updates the Bézout coefficients `x` and `y` and the numbers `a` and `b` for the next iteration. The process stops when `b` reaches 0, at which point `a` is the GCD and `x` and `y` are the desired coefficients.

3. A First Application: The Proof of Euclid's Lemma

Bézout's Identity is not just a numerical curiosity; it is a foundational tool for proving other major theorems in number theory. Its most immediate and important application is in proving Euclid's Lemma, which will be the focus of our next lesson.

Euclid's Lemma: If a prime $p$ divides the product $ab$ , then $p$ must divide $a$ or $p$ must divide $b$ .

The proof is a beautiful and concise demonstration of the power of Bézout's Identity.

This is a perfect example of the kind of non-obvious, structural argument that is common in Olympiad-level number theory.

Conclusion

In this lesson, we have moved from simply calculating the GCD to understanding its deep connection to the numbers themselves.

Key Takeaways:

Bézout's Identity states that for any integers $a, b$ , there exist integers $x, y$ such that $a x + b y = gcd (a, b)$ .
The existence of this linear combination can be proven elegantly using the Well-Ordering Principle on the set of all positive linear combinations of $a$ and $b$ .
The Extended Euclidean Algorithm provides a constructive method to find the coefficients $x$ and $y$ . We explored both the intuitive back-substitution method and the more systematic tabular method.
Bézout's Identity is a powerful theoretical tool, enabling simple proofs of other important results, like Euclid's Lemma.

You now possess one of the most fundamental tools in number theory. In the next lesson, we will formally dive into Euclid's Lemma. We will explore its proof in more detail and see how it becomes the keystone in the proof of the Fundamental Theorem of Arithmetic—the unique prime factorization of integers.