Page 73 - 'Blast_Into_Math

Blast into Math! The Euclidean algorithm: a computational recipe

Exercise: Why is this true? Hint: Look at the definition of q ∈ S .

To show that r = a − bq <b , remember that q is the largest integer in S . This means that q +1 /∈ S ,
because q +1 ∈ Z , and q +1 >q . So, since q +1 ∈ Z, the only way that q +1 fails to be in S is if

b(q +1) >a.

We can rearrange

b(q +1) >a,

to

bq + b> a,

and if we subtract bq from both sides, we see

b> a − bq = r.

So we have found the q and the r for the Lemma. They are non-negative integers which satisfy,

a = bq + r, 0 ≤ r< b.

But why are q and r unique? First of all, for any “q ,” there is only one possibility for r because
r = a − bq . So, if there is some other “q ” for the lemma, then there is some other “r ” also. By
contradiction, let’s prove that there can only be one q and one r . So, for a proof by contradiction, we

assume there is some other “q ” and some other “r .” To avoid confusion, let’s call them x and y . Since
x = q, either x> q or x< q . By possibly switching their names, we can assume x> q . Then, a ,
b , q , x , r and y satisfy

a = bq + r = bx + y.

Re-arranging,

b(x − q)= r − y.

Let’s think about this. On the left we have b multiplied by x − q . x and q are integers with x> q ,
so x − q ≥ 1. Therefore, the left side is greater than or equal to b:

b ≤ b(x − q).

73