# Euclidean Algorithm

Jump to: navigation, search

## Algorithm

The Euclidean algorithm is a method for finding the greatest common divisor (GCD) of two integers $a$ and $b$.

Let $a, b \in \Z$ and $a \ne 0 \lor b \ne 0$.

The steps are:

$(1): \quad$ Start with $\left({a, b}\right)$ such that $\left|{a}\right| \ge \left|{b}\right|$. If $b = 0$ then the task is complete and the GCD is $a$.
$(2): \quad$ If $b \ne 0$ then you take the remainder $r$ of $\dfrac a b$.
$(3): \quad$ Set $a \gets b, b \gets r$ (and thus $\left|{a}\right| \ge \left|{b}\right|$ again).
$(4): \quad$ Repeat these steps until $b=0$.

Thus the GCD of $a$ and $b$ is the value of the variable $a$ at the end of the algorithm.

It can be seen from the definition that the Euclidean algorithm is indeed an algorithm in the strict mathematical sense.

In the words of Euclid:

Given two (natural) numbers not prime to one another, to find their greatest common measure.

(The Elements: Book VII: Proposition $2$)

## Proof

Suppose $a, b \in \Z$ and $a \lor b \ne 0$.

From the Division Theorem, $a = q b + r$ where $0 \le r < \left|{b}\right|$.

From GCD with Remainder, the GCD of $a$ and $b$ is also the GCD of $b$ and $r$.

Therefore, we may search instead for $\gcd \left\{{b, r}\right\}$.

Since $|r| < |b|$ and $b \in \Z$, we will reach $r=0$ after finitely many steps.

At this point, $\gcd \left\{{r, 0}\right\} = r$ from GCD with Zero.

$\blacksquare$

## Euclid's Proof

Let $AB, CD$ be the two given (natural) numbers which are not coprime.

We need to find the greatest common divisor of $AB$ and $CD$.

Suppose WLOG that $CD \le AB$.

We have that $CD$ is a divisor of itself.

If $CD$ is a divisor of $AB$ then $CD$ is a common divisor of $CD$ and $AB$.

It is clearly the greatest, because no number greater than $CD$ can be a divisor of $CD$.

Now, suppose $CD$ does not divide $AB$.

Then the less of the numbers $AB, CD$ being continually subtracted from the greater, some number will be left which will be a divisor of the one before it.

From Coprimality Criterion, this number will not be a unit, otherwise $AB$ and $CD$ will be coprime.

So some number will be left which is a divisor of the one before it.

Now let $CD$, dividing $BE$, leave $EA$ less than itself.

Let $EA$, dividing $DF$, leave $FC$ less than itself.

Let $CF$ divide $AE$.

Since then $CF$ divides $AE$, and $AE$ divides $DF$, then $CF$ will also divide $DF$.

But it also divides itself.

Therefore it will also divide the whole $CD$.

But $CD$ divides $BE$, therefore $CF$ divides $BE$.

But it also divides $EA$, therefore it will also divide the whole $BA$.

So $CF$ is a common divisor of $CD$ and $AB$.

Suppose $CF$ is not the greatest common divisor of $CD$ and $AB$.

Let $G > CF$ also be a common divisor of $CD$ and $AB$.

Since $G$ divides $CD$, while $CD$ divides $BE$, it follows that $G$ divides $BE$.

But $G$ also divides the whole $BA$, and so it also divides the remainder $AE$.

But $AE$ divides $DF$.

Therefore $G$ divides $DF$.

But $G$ also divides the whole $DC$.

Therefore it will also divide the remainder $CF$.

But $G$ is greater than $CF$, which is impossible.

Therefore no number greater than $CF$ divides the numbers $AB$ and $CD$.

Therefore $CF$ is the greatest common divisor of $AB$ and $CD$.

$\blacksquare$

## Demonstration

We can investigate in more detail what happens when we apply the Division Theorem repeatedly to $a$ and $b$.

 $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle a$$ $$=$$ $$\displaystyle$$ $$\displaystyle q_1 b + r_1$$ $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle b$$ $$=$$ $$\displaystyle$$ $$\displaystyle q_2 r_1 + r_2$$ $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle r_1$$ $$=$$ $$\displaystyle$$ $$\displaystyle q_3 r_2 + r_3$$ $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle \cdots$$  $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle r_{n-2}$$ $$=$$ $$\displaystyle$$ $$\displaystyle q_n r_{n-1} + r_n$$ $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle r_{n-1}$$ $$=$$ $$\displaystyle$$ $$\displaystyle q_{n+1} r_n + 0$$ $$\displaystyle$$ $$\displaystyle$$

From the Division Theorem, we know that the remainder is always strictly less than the divisor.

That is, in $a = q b + r, 0 \le r < \left|{b}\right|$.

So we know that: $b > r_1 > r_2 > \ldots > r_{n-2} > r_{n-1} > r_n > 0$

So the algorithm has to terminate.

$\blacksquare$

## Algorithmic Nature

• Finiteness: As has been seen, the algorithm always terminates after a finite number of steps.
• Definiteness: Each of the steps is precisely defined.
• The inputs are $a$ and $b$.
• The output is $\gcd \left\{{a, b}\right\}$.
• Effectiveness: Each operation is finite in extent and can be effectively performed.

## Constructing an Integer Combination

Having done this, we are now in a position to find a solution to $\gcd \left\{{a, b}\right\} = x a + y b$ for $x$ and $y$.

By Bézout's Identity it is always possible to find such an $x, y \in \Z$.

Working back through the equations above, we get:

 $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle \gcd \left\{ {a, b}\right\}$$ $$=$$ $$\displaystyle$$ $$\displaystyle r_n$$ $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle$$ $$=$$ $$\displaystyle$$ $$\displaystyle r_{n-2} - q_n r_{n-1}$$ $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle$$ $$=$$ $$\displaystyle$$ $$\displaystyle r_{n-2} - q_n \left({r_{n-3} - q_{n-1} r_{n-2} }\right)$$ $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle$$ $$=$$ $$\displaystyle$$ $$\displaystyle \left({1 + q_n q_{n-1} }\right) r_{n-2} - q_n r_{n-3}$$ $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle$$ $$\displaystyle$$ $$=$$ $$\displaystyle$$ $$\displaystyle \left({1 + q_n q_{n-1} }\right) \left({r_{n-4} - q_{n-2} r_{n-3} }\right) - q_n r_{n-3}$$ $$\displaystyle$$ $$\displaystyle$$

... and so on. The algebra gets messier the further up the tree you go, and is not immediately enlightening.

Thus eventually we arrive at $\gcd \left\{{a, b}\right\} = x a + y b$ where $x$ and $y$ are numbers made up from some algebraic cocktail of the coefficients of the terms involving the remainders from the various applications of the Division Theorem.

Note that $a \mathop \backslash b \implies \gcd \left\{{a, b}\right\} = a$, from GCD of Integer and Divisor.

## Also known as

The Euclidean algorithm is also known as Euclid's algorithm or the Euclidean division algorithm.

## Historical Note

This is Proposition 2 of Book VII of Euclid's The Elements.

## Source of Name

This entry was named for Euclid.