Page 77 - 'Blast_Into_Math

Blast into Math! The Euclidean algorithm: a computational recipe

Since S ++ , S −+ , S −− , and S +− are all the same set it follows that they all have the same largest

element which means

(a, b)= (−a, b)= (−a, −b)= (a, −b).

For each of a and b,

|a| = a if a ≥ 0, and |a| = −a if a< 0,

|b| = b if b ≥ 0, and |b| = −b if b< 0.

Therefore, since |a| is equal to a or −a , and |b| is equal to b or −b,

S = {d ∈ Z such that d||a| and d||b|}

is equal to one of S ++ , S −+ , S −− , S +− . But, these are all the same set. So they all have the same
largest element, which by definition of greatest common divisor means

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

Now let’s prove the pepper. Let’s start by showing that if d ∈ N such that

d|x, and d|y,

then d|z . We know that

x = yq + z,

so we can re-arrange this to

z = x − yq.

Do you also see a lot of letters? These letters are like actors…

Exercise: Re-read the Actor Lemma and think about how you could use it to prove that d|z . Then you

may turn the page.

77