Page 85 - 'Blast_Into_Math

Blast into Math! The Euclidean algorithm: a computational recipe

This disguise can be very useful! For example, if a and b are relatively prime, then for any integer q
we can write

q = qra + qbs,

because

1= ra + bs =⇒ q = q(ra + bs).

This is one reason the theorem is called “Incredibly Useful.” Another reason is because we can use the
IUT to prove the following corollary. What is a corollary? A common sales promotion is “buy one get
one half-off.” A corollary is like a second theorem which we get half-off after proving the first theorem.
After doing the work to prove the first theorem, which is like buying the theorem at full price, proving
the corollary is much less work, so it’s like getting the corollary for half the price! Sometimes the proof
of a corollary is so easy, it’s like “buy one get one free.”

Corollary 4.4.3 Any common divisor of a and b also divides (a, b).

Proof: If n ∈ N divides both a and b , then by the Actor Lemma for any r, s ∈ Z ,

n|(ra + sb).

If we choose r and s using the IUT so that

(a, b)= ra + sb,

then this means that

n|(a, b).

♥

4.5 Exercises

1. Use the Euclidean Algorithm to find (103, 12).
2. Use the Euclidean Algorithm and the proof of the IUT to find integers r and s such that

27r +12s =1.

3. Find integers r and s such that 922r + 2163s =7.

85