The Euclidean algorithm is an efficient method for computing the greatest common divisor of two integers, without explicitly factoring the two integers.
It is used in countless applications, including computing the explicit expression in Bezout's identity, constructing continued fractions, reduction of fractions to their simple forms, and attacking the RSA cryptosystem. Furthermore, it can be extended to other rings that have a division algorithm, such as the ring of polynomials with rational coefficients.
The Euclidean algorithm solves the problem:
Given integers find
If the prime factorizations of and are known, finding the greatest common divisor is straightforward. Let and , where are positive prime integers and . Then
However, in general, factoring integers is a difficult problem from a computational perspective. The Euclidean algorithm provides a fast way to determine without knowing the prime factors of or Here is an outline of the steps:
- Given , use the division algorithm to write
- If stop and output this is the gcd of
- If replace by Go to step 2.
Apply the Euclidean algorithm:
The process stops since we reached and we obtain
The last line of the above example suggests a proof that the Euclidean algorithm computes the gcd. That is, it is enough to show that the gcd of each pair of numbers in the algorithm is the same, because the last pair is with , so which is what the Euclidean algorithm outputs for Here is a proof of this statement:
Suppose If then so But if then so So the GCDs are equal.
(IMO '59) Prove that is irreducible for every positive integer .
is irreducible if and only if the numerator and denominator have no common factor, i.e. their greatest common divisor is 1. Applying the Euclidean algorithm,
Hence, , which shows that the fraction is irreducible.
Bezout's identity says that the equation has solutions The Euclidean algorithm gives a method for finding one pair of solutions.
Find integers such that
Reverse the Euclidean algorithm:
Express as a linear combination of numbers moving up the line:
So is a solution.
See the Extended Euclidean Algorithm wiki for more details.
The Euclidean algorithm can be used in any ring with a division algorithm. Here are two examples:
Find the GCD of the polynomials and over
Use Euclidean algorithm:
So "the" GCD is See below for a comment on uniqueness.
In a ring with a division algorithm (sometimes called a Euclidean ring), the GCD is defined up to multiplication by a unit, i.e. an element of the ring with a multiplicative inverse. The units in the ring of integers are so this ambiguity is resolved by stipulating that the GCD is positive. In where is a field, the units are the nonzero constant polynomials. For instance, in the above example, divides every common divisor of the two polynomials, but so does or or any other constant multiple of This ambiguity can be resolved here by stipulating that the GCD should always be a monic polynomial—in this case
Find in the Gaussian integers
Use the Euclidean algorithm:
So "the" GCD is Note that the units in are so there are four equally valid answers:
Note that the division algorithm quotients above are obtained by dividing and rounding to the nearest Gaussian integer, e.g.
which is closest to