Home page for accesible maths 4 Number theory 4.3 The Euclidean algorithm 4.5 Lowest common multiples

Style control - access keys in brackets

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

4.4 Applications of Bézout’s Theorem

In this section we shall explore some of the theoretical consequences of Bézout’s Theorem.

Our first proposition combines several statements from Section 4.2 into a single result.

Proposition 4.4.1

Let $a,b\in\mathbb{Z}\setminus\{0\}$ , and let $d\in\mathbb{N}$ be a common factor of $a$ and $b$ . Then the following three conditions are equivalent:

(a)

$d$ is the highest common factor of $a$ and $b;$
(b)

$d$ is an integral linear combination of $a$ and $b;$
(c)

every common factor of $a$ and $b$ is a factor of $d$ .

Proof. Theorem 4.2.17 shows that (a) implies (b), while Lemma 4.2.13 ensures that (b) implies (c), and finally (c) implies (a) by Lemma 4.2.8. $\Box$

We shall next give an explicit description of all the integral linear combinations of a pair of non-zero integers.

Proposition 4.4.2

Let $a,b\in\mathbb{Z}\setminus\{0\}$ . Then the integral linear combinations of $a$ and $b$ are precisely the multiples of $\mathrm{hcf}(a,b)$ .

Example 4.4.3

If we take $a=18$ and $b=30$ , we know that $\mathrm{hcf}(a,b)=6=2a-b;$ since for instance $24=4\cdot 6$ we have $24=4(2a-b)=8a-4b=8\cdot 18-4\cdot 30.$

Proof. Let $d=\mathrm{hcf}(a,b)$ and $n\in\mathbb{Z}$ . We can then rewrite the statement as follows:

(\exists\,r,\,s\in\mathbb{Z})(n=ra+sb)\ \Leftrightarrow\ (d|n).

‘‘ $\Rightarrow$ ’’. Suppose that $n=ra+sb$ for some $r,\,s\in\mathbb{Z}$ . Then, as $d|a$ and $d|b,$ Lemma 4.2.13 implies that $d|n$ .

‘‘ $\Leftarrow$ ’’. Suppose that $d|n$ , say $n=md$ for some $m\in\mathbb{Z}$ . By Bézout’s Theorem, we can write $d=ua+vb$ for some $u,\,v\in\mathbb{Z}$ , and therefore we have

n=md=(mu)a+(mv)b=ra+sb

provided that we define $r=mu$ and $s=mv$ . $\Box$

Proposition 4.4.4

Let $a,b\in\mathbb{Z}\setminus\{0\}$ and $c\in\mathbb{N}$ . Then $\mathrm{hcf}(ca,cb)=c\cdot\mathrm{hcf}(a,b)$ .

Example 4.4.5

Since $\mathrm{hcf}(12,20)=4$ , we have $\mathrm{hcf}(120,200)=10\cdot 4=40.$

Proof. Let $d=\mathrm{hcf}(a,b)$ ; then $d|a$ and $d|b$ so $cd|ca$ and $cd|cb$ , so that $cd$ is a common factor of $ca$ and $cb$ . By Theorem 4.2.17 $d=ra+sb$ for some $r,s\in\mathbb{Z}$ , so $cd=r(ca)+s(cb)$ ; thus Corollary 4.2.15 implies that $\mathrm{hcf}(ca,cb)=cd.$ $\Box$

Corollary 4.4.6

Let $a,b\in\mathbb{Z}\setminus\{0\}$ with $d=\mathrm{hcf}(a,b)$ , and write $a=d\alpha$ and $b=d\beta$ , where $\alpha,\beta\in\mathbb{Z}$ . Then $\mathrm{hcf}(\alpha,\beta)=1$ .

Example 4.4.7

$\mathrm{hcf}(27,45)=9$ ; we have $27=9\cdot 3$ and $45=9\cdot 5$ , and $3$ and $5$ are coprime.

Proof. By Proposition 4.4.4 we have

d=\mathrm{hcf}(a,b)=\mathrm{hcf}(d\alpha,d\beta)=d\cdot\mathrm{hcf}(\alpha,% \beta),

so as $d\neq 0$ , $\mathrm{hcf}(\alpha,\beta)=1$ as required. $\Box$

Our final result is called Euclid’s Lemma; it will be important in our study of prime numbers in Section 4.6.

Theorem 4.4.8

Let $a,b,p\in\mathbb{Z}\setminus\{0\}$ , and suppose that $p|ab$ and that $a$ and $p$ are coprime. Then $p|b$ .

Example 4.4.9

$60=5\cdot 12$ ; as $6|60$ and $\mathrm{hcf}(6,5)=1$ , we have $6|12.$

Proof. Since $p|ab$ , we can take $q\in\mathbb{Z}$ with $pq=ab$ . As $\mathrm{hcf}(p,a)=1$ , Theorem 4.2.17 implies that there are $r,s\in\mathbb{Z}$ such that $rp+sa=1$ . Then

	$\displaystyle b$	$\displaystyle=b\cdot 1=b(rp+sa)=brp+sab$
		$\displaystyle=brp+spq=p(br+sq),$

and so $p|b$ as required. $\Box$