Page 78 - 'Blast_Into_Math

Blast into Math! The Euclidean algorithm: a computational recipe

We can use the Actor Lemma with d playing the role of “a ,” 1 playing the role of “c ,” x playing the

role of “t,” −y playing the role of “o ,” and q playing the role of “r ,” which says

d|(1)x +(−y)q)=⇒ d|z.

This means that every divisor of x and y also divides z , and so every divisor of x and y is also a
divisor of y and z . To complete the proof we can use the Actor Lemma again to prove that every divisor
of y and z is also a divisor of x . Since

x = yq + z,

if d|y and d|z , then by the Actor Lemma with d playing the role of “a ,” y playing the role of “c ,” q
playing the role of “t ,” 1 playing the role of “o ,” and z playing the role of “r ,”

d|(yq +(1)z)=⇒ d|x.

So we have proven that all the divisors of x and y also divide z , so every divisor of x and y is also a
divisor of y and z , and we have also proven that every divisor of y and z also divides x . This means that

{d ∈ N such that d|x and d|y} = {d ∈ N such that d|y and d|z}.

78