Page 75 - 'Blast_Into_Math

Blast into Math! The Euclidean algorithm: a computational recipe

If we can show that the set S is not empty and is bounded above, then the LUB Property guarantees

that S contains a largest integer. By the definition of greatest common divisor, the largest integer in S
is (a, b). First, we need to check whether or not S is empty. If a set is empty, then it has no largest or
smallest element, because it has nothing!

Exercise: Which natural number divides all integers?

This natural number is an element of S , so S = ∅ . Next we must show that S is bounded above. If
d|a and d ≥ 1, then there is f ∈ Z such that

a = df.

Then it is also true that

|a| = d|f|.

Since a =0, f =0, so |f|≥ 1. Therefore

|a|
d = ≤|a|.
|f|

75