Euclidean Algorithm

From ProofWiki
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 $\text{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$.

Euclid-VII-2.png

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 a\) \(=\) \(\displaystyle q_1 b + r_1\)                    
\(\displaystyle b\) \(=\) \(\displaystyle q_2 r_1 + r_2\)                    
\(\displaystyle r_1\) \(=\) \(\displaystyle q_3 r_2 + r_3\)                    
\(\displaystyle \cdots\) \(\) \(\displaystyle \)                    
\(\displaystyle r_{n-2}\) \(=\) \(\displaystyle q_n r_{n-1} + r_n\)                    
\(\displaystyle r_{n-1}\) \(=\) \(\displaystyle q_{n+1} r_n + 0\)                    


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 \gcd \left\{ {a, b}\right\}\) \(=\) \(\displaystyle r_n\)                    
\(\displaystyle \) \(=\) \(\displaystyle r_{n-2} - q_n r_{n-1}\)                    
\(\displaystyle \) \(=\) \(\displaystyle r_{n-2} - q_n \left({r_{n-3} - q_{n-1} r_{n-2} }\right)\)                    
\(\displaystyle \) \(=\) \(\displaystyle \left({1 + q_n q_{n-1} }\right) r_{n-2} - q_n r_{n-3}\)                    
\(\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}\)                    


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


Also see


Historical Note

This theorem is Proposition $2$ of Book $\text{VII}$ of Euclid's The Elements.



Source of Name

This entry was named for Euclid.


Sources