ENT - Euclidean Algorithm

3-minute read

Introduction

We will go over the Euclidean Algorithm in this document. The Euclidean algorithm is an algorithm for finding the greatest common divisor.

Algorithm

Goal: We want to find the Greatest Common Divisor(GCD) of $a$ and $b$.

First remember that due to the division algorithm, we can write $a$ and $b$ in the following form: $a = b \times q_0 + r_0$.

This is the first step of the division algorithm. Now take $b$ and $r_0$ and apply the division algorithm again. You should get $b = r_0 \times q_1 + r_1$. We then repeat again but this time we take $r_0$ and $r_1$. We keep doing this until we get a remainder of zero.

To re-iterate, lets write out all of the steps:

$a = b \times q_0 + r_0$

$b = r_0 \times q_1 + r_1$

$r_0 = r_1 \times q_2 + r_2$

$r_1 = r_2 \times q_3 + r_3$

…

…

$r_{n-2} = r_{n-1} \times q_n + r_n$

  • Observe that due to the division algorithm stating that the remainder is bounded. Each successive application of the division algorithm decreases the remainder. ie $r_0 > r_1 > r_2 > r_3$.

  • Also note that if we apply the division algorithm correctly, the remainder cannot be negative. Therefore, this sequence will eventually reach zero. This is not a proof that Euclid’s algorithm produces the GCD, just a mere observation.

Finding a common divisor

Now suppose that line 4 gives a remainder of zero: $r_1 = r_2 \times q_3 + r_3$ ie $r_3 = 0$.

Then :

$r_1 = r_2 \times q_3$ .

From this we can infer that $r_2 | r_1$.

Now lets look at the line above:

$r_0 = r_1 \times q_2 + r_2$

Since $r_2$ is a factor of $r_1$ then $r_2$ is a factor of $r_0$. This can be seen since $r_0 = r_2 (y * q_2 + 1)$ where $r_2 * y = r_1$

We now know that $r_2 | r_0$ and $r_2 | r_1$.

Now lets look at the line above: $b = r_0 \times q_1 + r_1$ Since $r_2$ is a factor of $r_1$ and $r_0$, then it is a factor of $b$. We now know that $r_2 | r_0$ and $r_2 | r_1$ and $r_2 | b$.

Now lets looks at the first line:

$a = b \times q_0 + r_0$.

Since $r_2$ is a factor of $r_0$ and $b$, it is a factor of a.

So what have we just found? We have found a common factor of a and b. It is $r_2$! Euclid’s algorithm proves that this is actually the greatest common factor.

This proof has been omitted, but is widely available.

Summary

The Euclidean algorithm repeatedly applies the Division algorithm until we get a remainder of zero. The GCD/GCF is then the previous non-zero remainder.