Page 82 - 'Blast_Into_Math

Blast into Math! The Euclidean algorithm: a computational recipe

Proof: By the SPL,

(a, b)= (|a|, |b|).

We may assume |b|≤ |a| , because otherwise we can switch the names of a and b . The first step of
the EA is to use the LDL

|a| = q|b| + r 1 , 0 ≤ q, 0 ≤ r 1 < |b|.

If b> 0, then

(a, b)= b = a(0)+ b(1),

so the “r ” in the IUT is 0, and the “s ” is 1. If b< 0, then

(a, b)= −b = a(0)+ b(−1),

so “r =0” and “s = −1.” Otherwise, there is some remainder r 1 . Thinking ahead, we know that the

last non-zero remainder is the greatest common divisor. We have the equation

|a| = q|b| + r 1 .

Re-arranging,

r 1 = |a|− q|b|.

If the next remainder in the EA, r 2 =0, then we have finished the theorem because in that case,
(a, b)= r 1 , so we can use the equation r 1 = |a|− q|b| to find the “r ” and “s ” for the theorem.

Exercise: Find the r and s in this case.

Otherwise, if r 2 =0, notice that

r 1 = |a|− q|b|,

which means that r 1 is equal to |a| plus −q|b|. Since q ∈ Z, −q ∈ Z. This means that r 1 is equal
to an integer times |a| plus an integer times |b|. Please take a moment to think about this. (The integer
“times |a| ” is just the integer 1, and the integer “times |b| ” is the integer −q .)

Now, let’s show that we can also find integers such that r 2 is equal to an integer times |a| plus an integer
times |b| . By definition of r 2 as the remainder of |b| divided by r 1 , and by the LDT,

|b| = q 2 r 1 + r 2 ,

82