Page 83 - 'Blast_Into_Math

Blast into Math! The Euclidean algorithm: a computational recipe

which we can re-arrange to

r 2 = |b|− q 2 r 1 = |b|− q 2 (|a|− q|b|)= −q 2 |a| +(1 − q 2 q)|b|.

This might look complicated, but the important thing is that they are all integers. This means that: r 2 is
equal to an integer multiplied by |a| plus an(other) integer multiplied by |b| . Since |a| = a or −a

depending on whether or not a is positive, and |b| = b or −b depending on whether or not b is
positive, we can either change signs of these integers (or not) and r 2 is equal to an integer multiplied
by a plus an(other) integer multiplied by b .

Next, let’s show that we can find integers such that each remainder is equal to an integer times a plus
an(other) integer times b Since we have already proven this is true for the first two remainders, it makes
sense to use induction. We have proven the base case, so we have already taken the first step on the
mathemagical induction escalator. Next, we hold onto the handrail by making the induction assumption:
we assume that we have found x, y ∈ Z such that

r k = xa + yb,

and that we’ve also found w, v ∈ Z such that

r k−1 = wa + vb.

Since have shown the base case because we have shown that we can do this for r 1 and r 2 , we assume
k ≥ 3. If r k =0, then we are done, because that means

(a, b)= r k−1 = wa + vb, w,v ∈ Z,

so the “r ” and “s ” in the theorem are w and v . Otherwise, if r k =0, then we use the LDT to divide
r k−1 by r k ,

r k−1 = cr k + r k+1 ,

which we can re-arrange to

r k+1 = r k−1 − cr k .

Now we can use the induction assumption and substitute the equations for r k and r k−1 ,

r k+1 = wa + vb − c(xa + yb)= (w − cx)a +(v − cy)b, and w, c, x, v, and y ∈ Z.

Since Z is closed under addition, subtraction and multiplication,

(w − cx) ∈ Z and(v − cy) ∈ Z.

83