NTIC The Euclidean Algorithm

Section 2.3 The Euclidean Algorithm

The Euclidean algorithm says that to find the gcd of

$a$ and

$b\text{,}$ one performs the division algorithm until zero is the remainder, each time replacing the previous divisor by the previous remainder, and the previous number to be divided (sometimes called dividend) by the previous divisor. The last non-zero remainder is the gcd.

🔗

We'll state and prove this momentarily (Algorithm 2.3.3). Let's try it with a reasonably sized problem.

🔗

Example 2.3.1.

Let $a=60$ and $b=42\text{.}$

$\begin{align*} 60&=42\cdot 1+18\\ 42&=18\cdot 2+6\\ 18&=6\cdot 3+0 \end{align*}$

So $\gcd(60,42)=6\text{.}$

🔗

This procedure is named after Euclid because of Proposition VII.2 in Euclid's Elements. There is an amazing complete Java interactive implementation of all the propositions, by David Joyce, whose version of this proposition includes some explanation of Euclid's background assumptions. In particular, Euclid basically assumes the Well-Ordering Principle, although of course he didn't think of it in such anachronistic terms.

🔗

Remark 2.3.2.

Euclid, a mathematician in Alexandria during the Hellenistic era, appears to have written the Elements as a compendium of rigorous mathematical knowledge. In addition to being the main geometry textbook in the Western and Islamic worlds for two millennia (as late a teacher as Charles Dodgson a.k.a. Lewis Carroll extolled its virtues in print in Euclid and His Modern Rivals), there are substantial number-theoretic portions as well. No one really knows how much of the Elements is original to Euclid, but the work as a whole is monumental and well-organized, despite some well-known criticisms (see e.g. the discussion in [C.5.5]).

🔗

Try the algorithm on your own by hand for the gcd of 280 and 126. Or, for even more practice, try it with

$\gcd(2013,1066)$ and then check your work with Sage.

xxxxxxxxxx
 
gcd(2013,1066)

🔗

Algorithm 2.3.3. Euclidean algorithm.

To get the greatest common divisor of $a$ and $b\text{,}$ perform the division algorithm until you hit a remainder of zero, as below.

$\begin{align*} a&=bq_1+r_1\\ b&=r_1q_2+r_2\\ r_1&=r_2q_3+r_3\\ \cdots\\ r_{n-3}&=r_{n-2}q_{n-1}+r_{n-1}\\ r_{n-2}&=r_{n-1}q_{n}+0 \end{align*}$

Then the previous remainder, $r_{n-1}\text{,}$ is the greatest common divisor.

🔗

Proof.

First let's see why this algorithm even terminates. The division algorithm says each $r_i$ is less than the previous one, yet they may not be less than zero. So let's apply the Well-Ordering Principle to the set of remainders. This set must have a least positive element, and will be the answer. Another way to think about it is that since $b$ is finite, there won't be an infinite number of steps.

Of course, that just gives a number, with no guarantee it has any connection to the gcd. So consider the set of common divisors $d\mid a$ and $d\mid b\text{.}$ All such $d$ also divide

\begin{equation*} a-q_1b=1\cdot a+(-q_1)\cdot b=r_1 \end{equation*}

So these $d$ also divide $r_2=b-q_2r_1\text{,}$ and indeed divide all the remainders, even $r_{n-1}=r_{n-3}-q_{n-1}r_{n-2}\text{.}$ So all common divisors of $a$ and $b$ are divisors of $r_{n-1}\text{.}$

On the other hand, if $d$ divides $r_{n-1}\text{,}$ it divides $r_{n-2}=r_{n-1}q_{n}\text{,}$ and thus divides $r_{n-3}=r_{n-2}q_{n-1}+r_{n-1}\text{,}$ and so forth. Hence $d$ divides $a$ and $b\text{.}$

So the set of common divisors of $a$ and $b$ are equal to the set of divisors of $r_{n-1}\text{,}$ so this algorithm really does give the gcd.

🔗

As you might expect, the proof makes more sense if you try it out with actual numbers; for the theoretical view, see Exercise 2.5.14. Especially if you can find

$a$ and

$b$ for which the algorithm takes four or five steps, you will gain some insight.