Home page for accesible maths 4 Number theory 4.1 Divisibility 4.3 The Euclidean algorithm

Style control - access keys in brackets

Font (2 3) - + Letter spacing (4 5) - + Word spacing (6 7) - + Line spacing (8 9) - +

4.2 Highest common factors and linear combinations

The first definition in this section concerns numbers which divide two given numbers.

Definition 4.2.1

Let $a,b,c\in\mathbb{Z}$ . We say that $c$ is a common factor (or a common divisor) of $a$ and $b$ if $c$ divides both $a$ and $b$ .

In other words, the set of common factors of $a$ and $b$ is the intersection of the sets of factors of $a$ and $b$ .

Example 4.2.2

The sets of factors of $18$ and $30$ are

\{\pm 1,\pm 2,\pm 3,\pm 6,\pm 9,\pm 18\}\ \hbox{and}\ \{\pm 1,\pm 2,\pm 3,\pm 5% ,\pm 6,\pm 10,\pm 15,\pm 30\};

thus the set of common factors of $18$ and $30$ is $\{\pm 1,\pm 2,\pm 3,\pm 6\}.$

If $a$ and $b$ are not both zero, the set of common factors of $a$ and $b$ is clearly non-empty (as it contains $1$ ) and bounded above (by $|a|$ if $a\neq 0$ , and by $|b|$ otherwise), so it has a largest element. We may therefore make the following definition.

Definition 4.2.3

Given $a,b\in\mathbb{Z}$ , not both zero, the largest element of the set of common factors of $a$ and $b$ is called their highest common factor (or greatest common divisor), abbreviated hcf; we denote it by $\mathrm{hcf}(a,b)$ .

Example 4.2.4

From the set of common factors of $18$ and $30$ above, we have

\mathrm{hcf}(18,30)=6.

Remark 4.2.5

There are several things to note about this definition:

(i)

$\mathrm{hcf}(0,0)$ is not defined, since we stipulate that $a$ and $b$ are not both zero;
(ii)

$\mathrm{hcf}(a,b)=\mathrm{hcf}(-a,b)$ , because $a$ and $-a$ have the same factors (see Remark 4.1.3(i));
(iii)

$\mathrm{hcf}(a,b)=\mathrm{hcf}(b,a)$ ;
(iv)

if $b|a$ then $\mathrm{hcf}(a,b)=|b|$ .

Definition 4.2.6

If $\mathrm{hcf}(a,b)=1$ , then we say that $a$ and $b$ are coprime.

Example 4.2.7

The set of factors of $35$ is $\{\pm 1,\pm 5,\pm 7,\pm 35\}$ . From above we see that the only common factors of $18$ and $35$ are $\pm 1$ ; thus $\mathrm{hcf}(18,35)=1$ , and $18$ and $35$ are coprime.

Lemma 4.2.8

Let $a,b\in\mathbb{Z}\setminus\{0\}$ , and suppose that $d\in\mathbb{N}$ is a common factor of $a$ and $b$ such that every other common factor of $a$ and $b$ is a factor of $d$ . Then $d$ is the highest common factor of $a$ and $b$ .

Example 4.2.9

We saw in Example 4.2.2 that $6$ is a common factor of $18$ and $30$ , and each of their common factors $\pm 1,\pm 2,\pm 3,\pm 6$ divides $6$ . Hence $6$ is the highest common factor of $18$ and $30$ (as we have already observed in Example 4.2.4).

Proof. By the assumptions, $d$ is a common factor of $a$ and $b$ , and for any other common factor $c$ of $a$ and $b$ , we have $c|d$ , so that $c\leqslant|d|=d$ . Hence $d=\mathrm{hcf}(a,b)$ . $\Box$

We next give an important definition.

Definition 4.2.10

An (integral) linear combination of two integers $a$ and $b$ is an integer $c$ which can be written in the form $c=ra+sb$ for some $r,s\in\mathbb{Z}$ .

Example 4.2.11

The number $114$ is an integral linear combination of $18$ and $30$ because

114=3\cdot 18+2\cdot 30.

Note that there is no uniqueness about the coefficients $r$ and $s$ in this definition; it is quite possible for different choices of $r$ and $s$ to give the same integer $c=ra+sb$ . Indeed,

c=ra+sb=ra+ba+sb-ab=(r+b)a+(s-a)b,

so setting $t=r+b$ and $u=s-a$ , we also have $c=ta+ub$ .

Example 4.2.12

We have $114=3\cdot 18+2\cdot 30$ , but we can also write

114=(3+30)18+(2-18)30=33\cdot 18+(-16)\cdot 30.

It is easy to see how divisibility relates to integral linear combinations.

Lemma 4.2.13

Let $a,b,c\in\mathbb{Z}$ , and suppose that $c$ is a common factor of $a$ and $b$ . Then $c$ is a factor of every integral linear combination of $a$ and $b$ .

Example 4.2.14

We have $3|18$ and $3|30$ ; so by the previous example we should have $3|114$ (which is true as $114=38\cdot 3$ ).

Proof. Suppose that $a=pc$ and $b=qc$ for some $p,q\in\mathbb{Z}$ , and let $n\in\mathbb{Z}$ be an integral linear combination of $a$ and $b$ , so that $n=ra+sb$ for some $r,s\in\mathbb{Z}$ . Then we have

n=ra+sb=r(pc)+s(qc)=(rp+sq)c,

and the result follows. $\Box$

Corollary 4.2.15

Let $a,b\in\mathbb{Z}\setminus\{0\}$ , and suppose that $d\in\mathbb{N}$ is a common factor of $a$ and $b$ which is also an integral linear combination of $a$ and $b$ . Then $d=\mathrm{hcf}(a,b)$ .

Example 4.2.16

Since $5|25$ and $5|35$ , and $3\cdot 25-2\cdot 35=5$ , we must have $\mathrm{hcf}(25,35)=5$ (which is clear from the set of factors of $35$ already given, as $7\!\!\!\!\;\not\!\!\!\;|\!\;25$ and $35\!\!\!\!\;\not\!\!\!\;|\!\;25$ ).

Proof. Since $d$ is an integral linear combination of $a$ and $b$ , Lemma 4.2.13 implies that every common factor of $a$ and $b$ is a factor of $d$ . Hence $d=\mathrm{hcf}(a,b)$ by Lemma 4.2.8. $\Box$

Our next result, called Bézout’s Theorem, will have a number of important consequences. In its proof we shall make use of the elementary fact that any non-empty set of natural numbers contains a smallest element. (This is obvious; we may simply count upwards from $1$ until an element of the set is reached.)

Theorem 4.2.17

Let $a,b\in\mathbb{Z}\setminus\{0\}$ . Then $\mathrm{hcf}(a,b)$ is the smallest natural number which is an integral linear combination of $a$ and $b$ .

Example 4.2.18

We have $\mathrm{hcf}(18,30)=6$ , and we may write $6=2\cdot 18+(-1)\cdot 30$ . The numbers $\{1,2,3,4,5\}$ cannot be written as integral linear combinations of $18$ and $30$ .

Proof. Let $S$ be the set of natural numbers which are integral linear combinations of $a$ and $b$ ; that is,

S=\{n\in\mathbb{N}:n=ra+sb\ \text{for some}\ r,s\in\mathbb{Z}\}.

We see that $S$ is non-empty because it contains $|a|=(\pm 1)\cdot a+0\cdot b$ , so it has a smallest element $d$ . Thus we have $d=ra+sb$ for some $r,s\in\mathbb{Z}$ . We shall prove that $d=\mathrm{hcf}(a,b)$ , which will give the result.

To see that $d|a$ , we use Theorem 4.1.8 to write $a=qd+t$ with $q,t\in\mathbb{Z}$ and $0\leqslant t<d$ . Then

t=a-qd=a-q(ra+sb)=a-qra-qsb=(1-qr)a+(-qs)b,

so if $t>0$ we would have $t\in S$ , contrary to the minimality of $d$ . Hence we must have $t=0$ , and therefore $a=qd$ , i.e., $d|a$ .

A similar argument shows that $d|b$ , and so $d$ is a common factor of $a$ and $b$ .

We already know that $d$ is an integral linear combination of $a$ and $b$ , and hence Corollary 4.2.15 shows that $d=\mathrm{hcf}(a,b)$ . $\Box$

Corollary 4.2.19

Let $a,b\in\mathbb{Z}\setminus\{0\}$ . Then $a$ and $b$ are coprime if and only if there exist $r,s\in\mathbb{Z}$ such that $ra+sb=1$ .

Example 4.2.20

As $1=2\cdot 18+(-1)\cdot 35$ , the numbers $18$ and $35$ must be coprime (as we have seen).

Proof. ‘‘ $\Rightarrow$ ’’. Suppose that $\mathrm{hcf}(a,b)=1$ . Then $1$ is an integral linear combination of $a$ and $b$ by Theorem 4.2.17.

‘‘ $\Leftarrow$ ’’. Suppose that $1$ is an integral linear combination of $a$ and $b$ . Since no natural number is smaller than $1$ , Theorem 4.2.17 implies that $\mathrm{hcf}(a,b)=1$ . $\Box$