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$ .

May 4, 2007 - Posted by John Armstrong | Ring theory

3 Comments »

[…] 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
[…] 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
[…] 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

About this weblog

This is mainly an expository blath, with occasional high-level excursions, humorous observations, rants, and musings. The main-line exposition should be accessible to the “Generally Interested Lay Audience”, as long as you trace the links back towards the basics. Check the sidebar for specific topics (under “Categories”).

I’m in the process of tweaking some aspects of the site to make it easier to refer back to older topics, so try to make the best of it for now.

RSS Feeds

RSS - Posts
RSS - Comments
Feedback

Got something to say? Anonymous questions, comments, and suggestions at Formspring.me!
Subjects

Subjects
Archives

May 2007

M T W T F S S

1 2 3 4 5 6

7 8 9 10 11 12 13

14 15 16 17 18 19 20

21 22 23 24 25 26 27

28 29 30 31

« Apr Jun »
Search for:

The Unapologetic Mathematician

Mathematics for the interested outsider