# ENT - Euclidean Algorithm

## 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.