Euclid’s algorithm
Euclid’s algorithm describes a procedure for finding the greatest common divisor of two integers.
Suppose , and without loss of generality, , because if , then , and if , then . Put .
By the division algorithm for integers, we may find integers and such that where .
Notice that , because and , so and if and had a common divisor larger than , then would also be a common divisor of and , contradicting ’s maximality. Thus, .
So we may repeat the division, this time with and . Proceeding recursively, we obtain
Thus we obtain a decreasing sequence of nonnegative integers , which must eventually reach zero, that is to say, for some , and the algorithm terminates. We may easily generalize the previous argument to show that for , where . Therefore,
More colloquially, the greatest common divisor is the last nonzero remainder in the algorithm.
The algorithm provides a bit more than this. It also yields a way to express the as a linear combination of and , a fact obscurely known as Bezout’s lemma. For we have that
so substituting each remainder into the next equation we obtain
Sometimes, especially for manual computations, it is preferable to write all the algorithm in a tabular format. As an example, let us apply the algorithm to and . The following table details the procedure. The variables at the top of each column (without subscripts) have the same meaning as above. That is to say, is used for the sequence of remainders and for the corresponding sequence of quotients. The entries in the and columns are obtained by multiplying the current values for and by the in this row, and subtracting the results from the and in the previous row.
Thus, and .
Euclid’s algorithm was first described in his classic work Elements (see propositions VII 1 and VII 2), which also contained procedures for geometrical constructions. These are the first known formally described algorithms. Prior to this, informally defined algorithms were in common use to perform various computations, but Elements contained the first attempt to rigorously describe a procedure and explain why its results are admissible. Euclid’s algorithm for greatest common divisor is still commonly used today; since Elements was published in the fourth century BC, this algorithm has been in use for nearly 2400 years!
Title | Euclid’s algorithm |
---|---|
Canonical name | EuclidsAlgorithm |
Date of creation | 2013-03-22 12:00:04 |
Last modified on | 2013-03-22 12:00:04 |
Owner | rmilson (146) |
Last modified by | rmilson (146) |
Numerical id | 21 |
Author | rmilson (146) |
Entry type | Algorithm |
Classification | msc 11A05 |
Synonym | Euclidean algorithm |
Related topic | BezoutsLemma |
Related topic | EuclideanRing |