The Unapologetic Mathematician

Mathematics for the interested outsider

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 (P,\leq) and a subset S\subseteq P we say that b is a lower bound of S if b\leq s for every element s\in S. Similarly, an upper bound b is one so that s\leq b for every s.

A given subset S may have many different lower bounds. For example, if b is a lower bound for S and b'\leq b, then the transitive property of \leq shows that b' is also a lower bound. If we’re lucky, we can find a greatest lower bound. This is a lower bound d so that for any other lower bound b we have b\leq d. Then the set of all lower bounds is just the set of all elements below d.

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 a and b we can find numbers q and r with r<b and a=qb+r. We start with a and make up all the natural numbers of the form a-kb with k a natural number. Since the natural numbers are well-ordered, there is a least element a-qb in this set. Notice that here we use the regular order on \mathbb{N}, not divisibility. Anyhow, I claim that a-qb is less than b, so it will be our r. Indeed if it’s greater than b we can subtract b from it to get a-(q+1)b: a lower natural number, which contradicts the fact that a-qb is the lowest. Thus we have found a=qb+r with r<b. Notice that b|a if and only if r=0.

Okay, now that we remember how to divide we’re ready for Euclid’s algorithm. We start with numbers a and b and divide b into a to find a=q_1b+r_1. If r_1=0 then b|a and b is a common divisor. It’s clearly the greatest since any common divisor divides it.

If r_1\neq 0 then I say that any common divisor of b and r_1 is also a common divisor of a and b. We see that if r_1=k_1d and b=kd then a=q_1kd+k_1d=(q_1k+k_1)d so d|a as well. Thus if we can find the greatest common divisor of b and r_1 it will also be the greatest common divisor of a and b.

To do this, just keep going. Divide r_1 into b to get b=q_2r_1+r_2. If r_2=0 then we’re done, otherwise keep going again. At each step r_{i+1}<r_i, so we must eventually hit zero and stop. If we didn’t, then we could collect all the r_i together to have a set of natural numbers with no lowest element, contradicting the well-ordered property of \mathbb{N}. At the end we’ll have the greatest common divisor of a and b.

In fact, if we watch closely we can do even better. We stop when r_{n-1}=q_{n+1}r_n with a remainder of zero, getting the greatest common divisor d=r_n. Now we look at the next-to-last step r_{n-2}=q_nr_{n-1}+r_n. We can rewrite this as d=r_{n-2}-q_nr_{n-1}. Then the step before this — r_{n-3}=q_{n-1}r_{n-2}+r_{n-1} — can be written as r_{n-3}-q_{n-1}r_{n-2}=r_{n-1}. This gives us d=r_{n-2}-q_n(r_{n-3}-q_{n-1}r_{n-2})=-q_nr_{n-3}+(1+q_nq_{n-1})r_{n-2}. We can keep doing this over and over, at each step writing d 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 d=ax+by for some integers x and y.

From here you should be able to see how to use Euclid’s algorithm to find the greatest common divisor of any finite set S of natural numbers, and further how to write it as an integral linear combination of the elements of S.

About these ads

May 4, 2007 - Posted by | Ring theory

3 Comments »

  1. [...] 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 | Reply

  2. [...] 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 | Reply

  3. [...] 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 | Reply


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 389 other followers

%d bloggers like this: