4.3 The Euclidean algorithm

In this section we shall develop an efficient method to calculate $\mathrm{hcf}(a,b)$ for $a,b\in\mathbb{Z}\setminus\{0\}$ which does not depend on finding all the factors of $a$ and $b$ themselves. Moreover, this method will give us an explicit way of determining $r,s\in\mathbb{Z}$ such that $\mathrm{hcf}(a,b)=ra+sb$.

We begin by noting the effect of ‘‘division with remainder’’ on highest common factors.

Proof. Let $d\in\mathbb{Z}$ be a factor of $b$. We begin by showing that $d$ divides $a$ if and only if $d$ divides $r$. Indeed, by Lemma 4.2.13, if $d$ divides $a$, then $d$ divides $a-qb=r$, and conversely, if $d$ divides $r$, then $d$ divides $qb+r=a$. Thus $d$ is a common factor of $a$ and $b$ if and only if $d$ is a common factor of $b$ and $r$, and therefore $\mathrm{hcf}(a,b)=\mathrm{hcf}(b,r)$. $\Box$

Now suppose that $|a|>|b|$ (otherwise we interchange them, as Remark 4.2.5(iii) allows us to). Then we can use ‘‘division with remainder’’ to replace the pair of numbers $a$ and $b$ with the pair $b$ and $r$, without changing the highest common factor. Since the new pair is ‘‘smaller’’ than the old one, we have simplified the problem. This suggests that we can use this technique repeatedly, making each old divisor the new number to be divided, and each old remainder the new divisor, continuing until the divison leaves no remainder:

This process is called the Euclidean algorithm; it must terminate since the remainders $r_{j}$ form a strictly decreasing sequence of natural numbers: $r_{1}>r_{2}>\cdots>0$. By repeated use of Proposition 4.3.1, we see that the last divisor $r_{n-1}$ is the highest common factor, because

We may then reverse the steps to obtain the highest common factor as an integral linear combination of $a$ and $b$.

Some examples will clarify how this works in practice.

Solution.

Solution.