Page 76 - 'Blast_Into_Math

Blast into Math! The Euclidean algorithm: a computational recipe

So the divisors of a are less than or equal to |a| . This means that every d ∈ S satisfies

d ≤|a|.

Therefore |a| is an upper bound for S . By the LUB Property, S contains a largest positive integer.
This is (a, b).

4.2.1 Ingredients in the proof of the Euclidean algorithm

An algorithm is a computational recipe: it is a set of instructions which a person or a computer can follow

to perform a specific task. We have already collected the main ingredients for the proof of the Euclidean
algorithm. In cooking, the very last ingredients in many recipes are “salt and pepper to taste.” So, since
the following lemma contains the last two ingredients we need to prove the Euclidean algorithm, we’ll
call it the Salt and Pepper Lemma.

Lemma 4.2.2 (SPL) Salt: If a, b ∈ Z are non-zero, then (a, b)= (|a|, |b|). Pepper: If x and y are
natural numbers with x ≥ y , and q and z are non-negative integers with x = yq + z , and z> 0,
then (x, y)= (y, z).

Proof: Let’s start with the salt. First, we’ll prove that any number which divides an integer x must also
divide −x . Let d be an integer which divides x . By the definition of divide, there exists z ∈ Z so that

x = zd.

Since −1 ∈ Z , and Z is closed under multiplication, −z ∈ Z and

−x =(−z)d,

so by definition of divide, d|(−x). This means that

S ++ = {d ∈ Z such that d|a and d|b} = S −+ = {d ∈ Z such that d|(−a)and d|b}

= S −− = {d ∈ Z such that d|(−a)and d|(−b)} = S +− = {d ∈ Z such that d|a and d|(−b)}.

By the definition of greatest common divisor,

is (a, b);
• the largest element of S ++
• the largest element of S −+ is (−a, b);
• the largest element of S −− is (−a, −b);
• the largest element of S +− is (a, −b).

76