Page 71 - 'Blast_Into_Math

Blast into Math! The Euclidean algorithm: a computational recipe

Next, a|r means there is some e ∈ Z such that

r = ea.

Now, we can substitute fa for t and ea for r in (ct + or),

ct + or = cfa + oea =(cf + oe)a.

Because c , f , o and e ∈ Z and Z is closed under addition and multiplication we know that
(cf + oe) ∈ Z . Therefore we have found

cf + oe ∈ Z and ct + or = a(cf + oe),

which means by the definition of divide that

a|(ct + or).

♥

4.1.1 Long division

In school, you learned how to use “long division” to take any two positive integers a and b and find
the quotient q and the remainder r of a divided by b . But, how do you know that there is not some
other way to divide, maybe some short division which will give a different quotient and remainder? We
will prove that there is only one way to divide, and that the answer is the same as what you get from the
long division you learned in school.

Theorem 4.1.8 (Long division Theorem: LDT). Let a, b ∈ N. Then there exist unique non-negative
integers q and r, such that

a = bq + r, and0 ≤ r< b.

Proof: The role q is so named because it comes from the quotient of a divided by b , and similarly r
is the remainder of a divided by b . We can re-arrange the equation a = bq + r to

a r
= q + .
b b

To prove the theorem, we will first find q . In long division, q is the largest integer you can multiply
with b so that the result is less than or equal to a . To prove that q exists, let’s define a set

S := {z ∈ Z such that bz ≤ a}.

71