## The Euclidean algorithm

The following result has been known for thousands of years. The method is named for the Greek mathematician Euclid who decribed it in book 7 of this Elements'', written about 2300 years ago. For more details on his life, see the award-winning web site [MacOR].

Theorem 1.4.3 (Euclidean algorithm'')   Let and be integers. Then

Furthermore, there are integers such that .

proof 1: We first show that there are integers such that .

Let be the set of all positive integers of the form , where and are integers. Since is not empty, it has a smallest element by the well-ordering principle. Let be the smallest element of . The division algorithm (theorem 1.2.7) tells us that there are integers and satisfying and . But is in , contradicting our choice of as the smallest element of . Therefore, and is divisible by . Similarly, , and so it is a common divisor of and . If is another common divisor of and , then , so and this implies .

For the proof of the first statement of the theorem, see the proof below.

proof 2: We can (and do) assume without loss of generality that . First we show that there are integers such that . The proof of this is constructive and follows an algorithm called the Euclidean algorithm.

Let and . Let .

(1)
Use the division algorithm (theorem 1.2.7) to compute integers and such that

(2)
If then increment and go to step 1. If then stop.

Since , at some point the above algorithm must terminate. Suppose that and is the smallest such integer.

Claim: .

To see that, we first show that for some integers . Indeed, we claim that every ( ) is a integral linear combination of . This may be proven by mathematical induction. (The details are left to the reader as an exercise. The cases follow from , .) Thus . The fact implies .

Next, to finish the proof of the above claim, we show that and . Indeed, we claim that divides every ( ) (The details are left to the reader as an exercise. The cases follow from , .) The fact implies .

The claim follows.

It remains to prove

The previous paragraphs of this proof show that

For any integers we note , so

This implies the equality above, and completes the proof of the theorem.

david joyner 2008-04-20