Theorem 8.3: Let a and b be two nonzero natural numbers. The greatest common factor of a and b is the smallest nonzero natural number that can be written as a sum or difference of multiples of a and b.

Proof: a + b is a non zero natural number which is sum of a and b, so

{0< x < a + b | x is a sum or difference of multiples of a and b }

is not empty. By Theorem 5.1, the Well Ordering Principle, there is a smallest element c in this set which will then be the smallest nonzero natural number that can be written as a sum or difference of multiples of a and b. The claim is that c is the greatest common factor of a and b.

To show that c is a common factor, we first show that c divides a. Use Theorem 8.1, the Division Algorithm, to find natural numbers q and r such that

a = qc + r

where r < c. Then

r = a - qc

by Theorem 7.3. Now since c is a sum or difference of multiples of a and b, so is qc by the Distributive Properties of Addition, Theorem 6.10, and Subtraction, Theorem 7.5. Then r = a - qc will be a sum or difference of multiples of a and b, by Theorem 7.5. But since c is the smallest nonzero natural number which is a difference of multiples of a and b, it follows that r must be 0 and

a = qc

so c divides a by Definition 8.1.

To show that c divides b, use Theorem 8.1, the Division Algorithm, to find natural numbers q and r such that

b = qc + r

where r < c. Then

b = a - qc

by Theorem 7.3. Now since c is a sum or difference of multiples of a and b, so is qc by the Distributive Properties of Addition and Subtraction, Theorem 6.10 and Theorem 7.5. Then

r = b - qc

will be a sum or difference of multiples of a and b. But since c is the smallest nonzero natural number which is a difference of multiples of a and b, it follows that r must be 0 and

b = qc

so c divides b.

To show that c is the greatest common factor, let d be any other common factor. Then d divides a and d divides b. By Theorem 6.8, Theorem 6.10 and Theorem 7.5, the Associative and Distributive Properties of Multiplication, d will divide any natural number which is a sum or difference or multiples of a and b including c. Thus by Definition 8.1, c = qd for some natural number q. Since c is not zero, neither is q and so by Theorem 7.8, d < c.