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 .
Since , at some point the above algorithm must terminate. Suppose that and is the smallest such integer.
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