The Unapologetic Mathematician

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 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. 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}, 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 | Ring theory