Greatest Lower Bounds and Euclid’s Algorithm
One interesting question for any partial order is that of lower or upper bounds. Given a partial order and a subset we say that is a lower bound of if for every element . Similarly, an upper bound is one so that for every .
A given subset may have many different lower bounds. For example, if is a lower bound for and , then the transitive property of shows that is also a lower bound. If we’re lucky, we can find a greatest lower bound. This is a lower bound so that for any other lower bound we have . Then the set of all lower bounds is just the set of all elements below .
As an explicit example, let’s consider the partial order we get from the divisibility relation on integers. In this case, a greatest lower bound is better known as a greatest common divisor, and for any pair of natural numbers we can find a greatest common divisor. The method we use actually goes all the way back to Euclid’s Elements, proposition VII.2. Because of this, it’s known as Euclid’s algorithm.
First we need remember how we divide numbers from back in arithmetic. Given two numbers and we can find numbers and with and . We start with and make up all the natural numbers of the form with a natural number. Since the natural numbers are well-ordered, there is a least element in this set. Notice that here we use the regular order on , not divisibility. Anyhow, I claim that is less than , so it will be our . Indeed if it’s greater than we can subtract from it to get : a lower natural number, which contradicts the fact that is the lowest. Thus we have found with . Notice that if and only if .
Okay, now that we remember how to divide we’re ready for Euclid’s algorithm. We start with numbers and and divide into to find . If then and is a common divisor. It’s clearly the greatest since any common divisor divides it.
If then I say that any common divisor of and is also a common divisor of and . We see that if and then so as well. Thus if we can find the greatest common divisor of and it will also be the greatest common divisor of and .
To do this, just keep going. Divide into to get . If then we’re done, otherwise keep going again. At each step , so we must eventually hit zero and stop. If we didn’t, then we could collect all the together to have a set of natural numbers with no lowest element, contradicting the well-ordered property of . At the end we’ll have the greatest common divisor of and .
In fact, if we watch closely we can do even better. We stop when with a remainder of zero, getting the greatest common divisor . Now we look at the next-to-last step . We can rewrite this as . Then the step before this — — can be written as . This gives us . We can keep doing this over and over, at each step writing as a linear combination of the two remainders that we started a given step with. Taking this all the way back to the beginning of the algorithm, we get for some integers and .
From here you should be able to see how to use Euclid’s algorithm to find the greatest common divisor of any finite set of natural numbers, and further how to write it as an integral linear combination of the elements of .
[…] so what’s wrong with the rational numbers now? In any partial order we can consider least upper or greatest lower bounds. That is, given a set of rational numbers the least upper bound or “supremum” is a […]
Pingback by Dedekind Completion « The Unapologetic Mathematician | December 5, 2007 |
[…] of the index set consisting of all indices above a given index . We then ask what the least upper bound of the net is on this tail: . Alternately, we consider the greatest lower bound on the tail: […]
Pingback by Limits Superior and Inferior « The Unapologetic Mathematician | May 2, 2008 |
[…] for integers, as it should. Specifically, it’s got all the features we need for the setup of Euclid’s Algorithm, and we have an analogue […]
Pingback by Euclid’s Algorithm for Polynomials « The Unapologetic Mathematician | August 5, 2008 |