Euclidean Algorithm for GCD

1. The Principle Behind the Algorithm

Before we learn the steps of the algorithm, let's understand why it works. The entire process is built on a single, powerful property.

The key insight is that if $a=bq+r$, then the greatest common divisor of $a$ and $b$ is the same as the greatest common divisor of $b$ and $r$. In other words:
$\text{gcd}(a,b)=\text{gcd}(b,r)$
where $r$ is the remainder when $a$ is divided by $b$.

To understand the reasoning behind this crucial fact, let's watch a short video that provides an accessible proof. Since you have a background in writing mathematical proofs, you should find the logic here straightforward.

The proof demonstrates that:

1. Any common divisor of $a$ and $b$ must also divide the remainder $r=a-bq$.
2. Any common divisor of $b$ and $r$ must also divide $a=bq+r$.

This means the set of common divisors of $(a,b)$ is identical to the set of common divisors of $(b,r)$. Consequently, their greatest common divisors must also be identical.

The Euclidean algorithm exploits this by repeatedly replacing a pair of numbers with a smaller pair that has the same GCD, until the problem becomes trivial to solve.

2. The Euclidean Algorithm in Practice

Now that we know the principle, let's see the computational procedure. We will repeatedly apply the division algorithm, where the divisor and remainder from one step become the new dividend and divisor in the next step. This process continues until we get a remainder of 0. The last non-zero remainder is our GCD.

The following video demonstrates a very clear, tabular method for organizing this process.

Let's summarize the steps of the tabular method for finding $\text{gcd}(a,b)$, assuming $a>b$:

1. Set up a table with columns for the quotient ($q$), the two numbers (let's call them $A$ and $B$), and the remainder ($r$).
2. In the first row, set $A=a$ and $B=b$.
3. Calculate $A=Bq+r$ using the Division Algorithm to find $q$ and $r$. Fill these into the table.
4. For the next row, the value of $B$ moves to the $A$ column, and the value of $r$ moves to the $B$ column.
5. Repeat steps 3 and 4 until you get a remainder $r=0$.
6. The GCD is the value in the $A$ column of the final row (or, equivalently, the last non-zero remainder).

Let's look at a visual summary of this process.

Now, try one yourself.

3. A Look Ahead: The Extended Euclidean Algorithm and Code

The Euclidean algorithm is powerful in its own right, but a slight modification, known as the Extended Euclidean Algorithm, makes it even more useful. This extended version not only finds the GCD, $d$, but also finds two integers, $s$ and $t$, such that:

$d=sa+tb$

This ability to express the GCD as a linear combination of the original two numbers is fundamental. We will use this exact technique later in the course to find multiplicative inverses in ${\mathbb{Z}}_n$.

You don't need to master the extended algorithm today, but it's valuable to see that it exists and how it relates to our current topic. Since you have an interest in coding, looking at a practical implementation can be a great way to solidify your understanding of the standard algorithm as well.

The C code provides a concrete example of how this seemingly abstract process is implemented algorithmically, reducing it to a series of simple arithmetic operations and comparisons.

Conclusion

In this lesson, we demystified one of the oldest and most important algorithms in mathematics.

Key Takeaways:

• The Euclidean algorithm is an efficient method for computing the greatest common divisor (GCD) of two integers.
• It relies on the principle that $\text{gcd}(a,b)=\text{gcd}(b,a(\mathrm{mod}b))$.
• The algorithm works by repeatedly applying the Division Algorithm until a remainder of 0 is reached. The GCD is the last non-zero remainder.
• The Extended Euclidean Algorithm can express the GCD as a linear combination $d=sa+tb$, a fact that will be crucial later on.

Preview of the Next Lesson:
We will now move from divisibility to the related concept of modular congruence. We will define what it means for two numbers to be "congruent modulo n" and start performing arithmetic with these congruences. This is our first step into a new algebraic system, ${\mathbb{Z}}_n$, where the ideas of remainders and GCDs will play a central role.