Page 80 - 'Blast_Into_Math

Blast into Math! The Euclidean algorithm: a computational recipe

By the LDT again,

9= 3(3) +0.

Now we can STOP because the remainder is ZERO. What does that mean? If a = bq +0, it means that
a is divisible by b. So, in this case, we see that 9 is divisible by 3. (You already knew that.) We have now
proven using the LDT and the SPL that

(54, −21) =(54, 21) =(21, 12) =(12, 9) =(9, 3) =3.

With this example in mind, we will prove the Euclidean Algorithm.

1. Let a and b be two non-zero integers. Then, by the SPL

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

By possibly changing their names, we may assume

|b|≤ |a|.

2. By the LDT, we can divide the bigger number by the smaller number, and the remainder is
unique. If the remainder is zero, then we STOP because it means that the smaller number
divides the bigger number. Since a positive number is not divisible by any numbers which
are greater than it, if the smaller number divides the bigger number, then the smaller

number is the greatest common divisor. So, if we started with a and b with |b|≤ |a| ,
then (a, b)= |b| .
3. If the remainder is not zero we call it r 1 . By the SPL,

(|a|, |b|)= (|b|,r 1 ), 0 <r 1 < |b|.

4. Next, we divide |b| by r 1 . If the remainder is zero, then we STOP because it means that

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

Otherwise, the new remainder r 2

0 <r 2 <r 1 < |b|.

5. By the SPL,
(|a|, |b|)= (|b|,r 1 )= (r 1 ,r 2 ), 0 <r 2 <r 1 < |b|.

80