Page 79 - 'Blast_Into_Math

Blast into Math! The Euclidean algorithm: a computational recipe

Therefore the largest elements of these two sets, which are respectively (x, y) and (y, z), must be equal
because the sets are equal. So we have proven the pepper:

(x, y)= (y, z).

♥

4.3 Proof of the Euclidean Algorithm

Before we prove the Euclidean Algorithm, let’s do an example: let’s find (54, −21) using the LDT and
SPL. The salt part of the SPL tells us that we can always first take absolute values because

(54, −21) =(|54|, |− 21|)= (54, 21).

Next, by the LDT we can write the larger number uniquely as

54 = 21(2) +12,

where here, 2 is playing the role of q , and 12 is playing the role of r. Now it’s time for some pepper:

(54, 21) =(21, 12).

In the pepper part of the SPL, 54 plays the role of x, 21 plays the role of y , 2 plays the role of q and
12 plays the role of z .

Exercise: Audition these “actors” for their roles in the SPL by checking that the numbers fit the hypotheses
and run the script with these actors.

We now have reduced the original problem to the same problem but with smaller numbers. By the LDT,

21 = 12(1) +9,

so a little more pepper tells us by the SPL

(21, 12) =(12, 9).

We use the LDT again to write

12 =9(1)+ 3,

and again (more pepper! ) we know that

(12, 9) =(9, 3).

79