Page 69 - 'Blast_Into_Math

Blast into Math! The Euclidean algorithm: a computational recipe

Proof: By the definition of divide, there exists e ∈ Z such that b = ae , and there exists f ∈ Z such

that c = bf . Putting these facts together:

c = bf =(ae)f = a(ef).

The integers are closed under multiplication, and e and f are both integers, so ef ∈ Z . Then,
c =(ef)a fits perfectly into the definition of division for

a|c.

♥
Although examples do not prove theorems or propositions (or lemmas), they can help us understand
them. We can think of the variables in the proposition as roles in a play and numbers in examples as
actors who can play these roles if they pass the audition. For example, we could have 2 play the role of
a , 4 play the role of b and 20 play the role of c . We should always “audition” our actors by checking
that they satisfy the hypotheses: we need to check that a|b and b|c are both true. These actors pass
the audition because b =2a and c =5b , so by the definition of divide, a|b and b|c . Following the

“script” of the proof, we have e =2 and f =5. The next line in the proof tells us that we should have
c =(ef)a , and when we substitute our “actors” into their roles, this becomes

20 =2 ∗ 5 ∗ 2.

69