Page 74 - 'Blast_Into_Math

Blast into Math! The Euclidean algorithm: a computational recipe

On the right side we have r − y . Because r< b , and y ≥ 0,

r − y< b − 0= b.

Putting this all together means

b ≤ b(x − q)= r − y< b.

That’s rubbish! Following the inequalities means that b< b , which is nonsense! Therefore, the

assumption that there was some other “q ” and “r ” (whom we called x and y ) was false. So, our proof
by contradiction shows that there can be only one q and one r .

♥

Remark 4.1.9 In the proof, we assumed that x> q , because if not, we could just switch their names,
and call the old q , x , and call the old x , q . There is a famous quote [Sh]:

What’s in a name? That which we call a rose by any other name would smell as sweet.

We use names to represent people. This is exactly like using letters in mathematics to represent numbers.
What matters is not the name which represents the person, but who that person is, and what characteristics

that person has. In mathematics, what matters is not the letter which represents an unknown number,
but what properties or characteristics that number has. In the proof of the LDT, the x and q are the two
possible quotients, which we assume are different numbers. We assume x> q , which is like assigning
the name x to the larger of these two different numbers. We could just as well call it y or “Juliet,”
because the name doesn’t matter, only the meaning matters. In this case, the name x means: the larger
of two different integers.

4.2 Greatest common divisors

The Euclidean algorithm is a computational recipe for finding the greatest common divisor of two

numbers.

Definition 4.2.1. Let a, b ∈ Z , be non-zero integers. The largest integer that divides both a and b is
called the greatest common divisor of a and b and is written (a,b).

Why does (a, b) exist? This is an important question. Just like in the proof of the Long Division Theorem,
we can use a set of integers and the LUB Property to prove that (a, b) exists. We define the set

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

74