Euclidean Algorithm
Contents |
Algorithm
The Euclidean Algorithm (or Euclid's Algorithm / Euclidean Division 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 you are done and the GCD is $a$.
- $(2): \quad$ If $b \neq 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.
As Euclid defined it:
- 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 q_1 b + r_1\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle b\) | \(=\) | \(\displaystyle q_2 r_1 + r_2\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle r_1\) | \(=\) | \(\displaystyle q_3 r_2 + r_3\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \cdots\) | \(\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle r_{n-2}\) | \(=\) | \(\displaystyle q_n r_{n-1} + r_n\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle r_{n-1}\) | \(=\) | \(\displaystyle q_{n+1} r_n + 0\) | \(\displaystyle \) | \(\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 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 \) | \(\displaystyle \) |
... and so on. The algebra gets messier the further up the tree you go, and is not immediately enlightening.
(However, see Rational Numbers and SFCFs are Equivalent for an application of the Euclidean algorithm in a slightly different context.)
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 \backslash b \implies \gcd \left\{{a, b}\right\} = a$, from GCD of Integer and Divisor.
Historical Note
This is Proposition 2 of Book VII of Euclid's The Elements.
Source of Name
This entry was named for Euclid.
Sources
- Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (1968): $\S 1.1$: Algorithm $\text{E}$
- C.R.J. Clapham: Introduction to Abstract Algebra (1969)... (previous)... (next): $\S 3.11$
- George E. Andrews: Number Theory (1971): $\S 2.2$
- Allan Clark: Elements of Abstract Algebra (1971)... (previous)... (next): $\S 23 \zeta$
- Thomas A. Whitelaw: An Introduction to Abstract Algebra (1978)... (previous)... (next): $\S 12$
- John F. Humphreys: A Course in Group Theory (1996): $\text{A}.1$
