Page 72 - 'Blast_Into_Math

Blast into Math! The Euclidean algorithm: a computational recipe

This means “S is the set of integers so that when multiplied with b the result is less than or equal to
a .” The largest integer in S will be q . But first, we must check that there are some integers in S : we

must make sure that S = ∅ . Because if S = ∅ , then there is no largest integer in S. Can you think
of an integer in S ? We know that a ∈ N which means that a ≥ 1. What is an integer, which we can
multiply together with b and always end up with something smaller than 1? That’s right,

0b =0 < 1 ≤ a,

so, 0 ∈ S , and S is not empty. In order to find the largest integer in S , we’ll use the LUB Property.

To do this, we must show that S is bounded above. What do we know about b ? b ∈ N which means
b ≥ 1. So,

ab ≥ a ∗ 1= a, andif c> a, then cb ≥ c ∗ 1= c> a.

Therefore, if c > a, then c does not fit the definition of S , and this means that all integers in S are less
than or equal to a . That means that S is bounded above, and a is an upper bound for S . By the LUB
Property S contains a unique largest element, which we’ll call q . Let

r = a − bq.

Then r ≥ 0 because bq ≤ a.

72