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].

**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 2007-09-03