Proof of the Euclidean Algorithm

Welcome back. In our previous lesson, we established a formal understanding of divisibility and proved its fundamental properties, especially linearity, which states that if an integer divides $b$ and $c$ , it must also divide any linear combination $mb + n c$ . This property is not just a theoretical curiosity; it is the very engine that drives one of the oldest and most fundamental algorithms in all of mathematics.

Today, we will explore this algorithm: the Euclidean Algorithm. While you may be familiar with it as a procedure to compute the Greatest Common Divisor (GCD), our goal is to move beyond computation and address a deeper question: why does it work? We will prove its correctness, connecting the algebraic steps back to the properties of divisibility we just learned. By the end of this lesson, you will be able to explain with rigor why this ancient sequence of divisions reliably produces the greatest common divisor of any two integers.

1. From Geometry to Algorithm

The question of finding a common measure for two quantities is ancient. Imagine you have two line segments of integer lengths, say $a$ and $b$ , and you want to find the longest possible segment, of length $d$ , that can be used to measure both $a$ and $b$ perfectly. This $d$ is precisely the greatest common divisor.

Euclid's original approach was geometric. It involved starting with a rectangle of sides $a$ and $b$ and tiling it with squares.

This image illustrates the core idea of the Euclidean Algorithm. A large rectangle (34x20) is successively tiled by the largest possible squares. The side length of the final square that perfectly tiles the remaining area (in this case, a 2x2 square) is the GCD of the original side lengths. The algebraic steps on the right are a direct translation of this geometric process.

The process is as follows:

Take the larger dimension, say 34, and the smaller, 20. Fit as many 20x20 squares as you can into the 34x20 rectangle. You can fit one, leaving a 14x20 rectangle.
Now, repeat the process on this new, smaller rectangle. You can fit one 14x14 square into the 14x20 rectangle, leaving a 6x14 rectangle.
Repeat again: you can fit two 6x6 squares into the 6x14 rectangle, leaving a 2x6 rectangle.
Finally, you can fit three 2x2 squares perfectly into the 2x6 rectangle, with no remainder.

The side length of the last square you used, 2, is the GCD of 34 and 20. This process of "subtracting" the smaller dimension from the larger is the essence of the algorithm.

A wonderful video from the channel Proof of Concept provides a dynamic and intuitive explanation of this process. It starts with a simple "piles of stones" analogy and then reveals the secret behind why it works.

The Euclidean Algorithm: How and Why, Visually

This video provides an excellent visual and intuitive foundation for understanding the Euclidean Algorithm.

First, watch the demonstration using piles of stones. This illustrates the process of repeatedly subtracting the smaller number from the larger. Next, watch the visual explanation of why this process works from this section. Pay close attention to the "triangles" analogy. This is a brilliant visual representation of the linearity property we studied. Any common divisor of the two original numbers is preserved at every step of the subtraction. Finally, watch the segment explaining how the inefficient process of repeated subtraction is sped up by using the Division Algorithm. This connects the intuitive idea to the modern, efficient form of the algorithm.

The key insight from the video is that if a number $d$ divides both $a$ and $b$ , it must also divide their difference, $a - b$ . By repeatedly applying this, we see that any common divisor of the original pair $(a, b)$ must also be a common divisor of the pair at every subsequent step. This means the set of common divisors—and therefore the greatest common divisor—remains unchanged throughout the process.

2. The Core Lemma and Its Proof

The visual intuition can be formalized into a single, powerful lemma which is the heart of the algorithm's correctness.

The GCD Remainder Lemma: For any integers $a, b, q, r$ such that $a = q b + r$ , we have $gcd (a, b) = gcd (b, r)$ .

The Euclidean algorithm is simply the repeated application of this lemma. We start with $gcd (a, b)$ , replace it with the "simpler" problem $gcd (b, r_{1})$ , then $gcd (r_{1}, r_{2})$ , and so on, until we arrive at a remainder of 0.

gcd (a, b) = gcd (b, r_{1}) = gcd (r_{1}, r_{2}) = \dots = gcd (r_{n - 1}, r_{n}) = gcd (r_{n}, 0) = r_{n}

The sequence of remainders $b > r_{1} > r_{2} > \dots \geq 0$ is a strictly decreasing sequence of non-negative integers. Therefore, by the Well-Ordering Principle (which states any non-empty set of non-negative integers has a least element), this process must terminate by reaching a remainder of 0.

Let's rigorously prove the lemma itself. The proof is a classic example of showing two numbers are equal by proving they divide each other.

Proof of $gcd (a, b) = gcd (b, r)$ :
Let $d = gcd (a, b)$ and $c = gcd (b, r)$ . We want to show $d = c$ .

Show $d$ is a common divisor of $b$ and $r$ :
- By definition of $d$ , we know $d ∣ a$ and $d ∣ b$ .
- The equation for the division algorithm can be rearranged as $r = a - q b$ .
- Since $d ∣ a$ and $d ∣ b$ , the linearity property tells us that $d$ must divide the linear combination $a - q b$ .
- Therefore, $d ∣ r$ .
- Since we already know $d ∣ b$ , $d$ is a common divisor of $b$ and $r$ .
Show $c$ is a common divisor of $a$ and $b$ :
- By definition of $c$ , we know $c ∣ b$ and $c ∣ r$ .
- From the equation $a = q b + r$ , we can see that $a$ is a linear combination of $b$ and $r$ .
- Since $c ∣ b$ and $c ∣ r$ , the linearity property tells us that $c$ must divide $q b + r$ .
- Therefore, $c ∣ a$ .
- Since we already know $c ∣ b$ , $c$ is a common divisor of $a$ and $b$ .
Combine the results:
- From (1), we know $d$ is a common divisor of $b$ and $r$ . But $c$ is the greatest common divisor of $b$ and $r$ , so we must have $d \leq c$ .
- From (2), we know $c$ is a common divisor of $a$ and $b$ . But $d$ is the greatest common divisor of $a$ and $b$ , so we must have $c \leq d$ .
- The only way for $d \leq c$ and $c \leq d$ to both be true is if $c = d$ .

This completes the proof. Each step of the Euclidean Algorithm replaces a GCD problem with an easier one that is guaranteed to have the same answer.

3. The Formal Proof Structure

While the lemma provides the core logic, a complete proof of the algorithm's correctness requires a more structured, two-part argument. We need to show that the final non-zero remainder, let's call it $r_{n}$ , is indeed the greatest common divisor of the original numbers, $a$ and $b$ .

The proof proceeds in two stages:

Show that $r_{n}$ is a common divisor of $a$ and $b$ .
Show that $r_{n}$ is the greatest of all common divisors.

The following video by Michael Penn provides a clear and concise walkthrough of this two-part proof.

To solidify this formal argument, let's examine it through the lens of Euclid's original work, translated into modern notation. The following resource contains a project based on Euclid's Elements. Exercise 3.12 guides you through the exact two-part proof we just saw.

[PDF] Euclid's Algorithm for the Greatest Common Divisor

This document provides historical context and a formal, modern algebraic breakdown of the proof of the Euclidean Algorithm.

Navigate to the section titled Exercise 3.12 on page 13. This exercise lays out the entire algorithm as a sequence of equations: a₁ = q₁a₂ + a₃ a₂ = q₂a₃ + a₄ ... aₙ = qₙaₙ₊₁ Your task is to work through the logic presented in this exercise. It formalizes the two arguments you just saw in the video: Part (c) asks you to use backward induction to show that aₙ₊₁ (the last non-zero remainder) divides all previous terms, including a₁ and a₂. This is the "common divisor" part of the proof. Part (e) asks you to use forward induction to show that if any number G divides a₁ and a₂, it must also divide aₙ₊₁. This establishes aₙ₊₁ as the "greatest" common divisor.

By working through this exercise, you are reconstructing the full, rigorous justification for the algorithm's correctness from first principles, just as Euclid did over two millennia ago.

Conclusion

In this lesson, we have dissected the Euclidean Algorithm to understand not just how it works, but why it is guaranteed to be correct.

Key Takeaways:

The algorithm works by repeatedly applying the GCD Remainder Lemma: $gcd (a, b) = gcd (b, a (mod b))$ . This keeps the GCD invariant while reducing the size of the numbers.
The process must terminate because the sequence of remainders is strictly decreasing and bounded below by 0.
The formal proof of correctness involves a two-part argument:
1. The last non-zero remainder, $r_{n}$ , is a common divisor of $a$ and $b$ . (Proven by working up the chain of division steps).
2. Any other common divisor $d$ must divide $r_{n}$ , which makes $r_{n}$ the greatest common divisor. (Proven by working down the chain of division steps).

Understanding this proof is a significant step in your journey. It demonstrates how a simple, elegant procedure can be underpinned by deep and powerful mathematical properties.

In our next lesson, we will see that the Euclidean Algorithm gives us more than just the GCD. By running the algorithm's steps in reverse, we can express the GCD as an integer linear combination of the original two numbers. This result, known as Bézout's Identity, is a cornerstone of number theory and will be our next major topic of study.

Recommended resources

1. From Geometry to Algorithm

2. The Core Lemma and Its Proof

3. The Formal Proof Structure

Conclusion