Next: Applications of the Euclidean Up: The integers Previous: The Euclidean Division   Contents

## The Euclidean algorithm

Suppose we want to find . We use lemmas and to obtain:

So . In general, to find :

 with with with with with

This process must terminate as . Using Lemma (2.21), . So is the last non-zero remainder in this process. We now wish to find and with . We can do this by backsubstitution.

This works in general but can be confusing and wasteful. These numbers can be calculated at the same time as if we know we shall need them. We introduce and . We put and . We iteratively define

Now consider .

Lemma 6.2.22

Proof. We shall do this using strong induction. We can easily see that (2.22) holds for and . Now assume we are at and we have already checked that and . Now

 , using the definition of and .

Proof. This is done by backsubstitution and using the definition of and .

An immediate corollary of this is that .

Lemma 6.2.24

Proof. (2.22) For gives . Therefore . Now and are coprime. and are coprime and thus this lemma is therefore an immediate consequence of the following theorem.

Theorem 6.2.25   If and then .

Proof. Since we can write for some , . Then and .

Definition 6.2.26   The least common multiple (lcm) of and (written ) is the integer such that
1. and ,
2. if and then .

It is easy to show that .

Next: Applications of the Euclidean Up: The integers Previous: The Euclidean Division   Contents
root 2002-06-10