Page 84 - 'Blast_Into_Math

Blast into Math! The Euclidean algorithm: a computational recipe

We have now shown that r k+1 is equal to an integer times a plus an integer times b. This proves the last

step of induction, setting the mathemagical induction escalator into motion and proving that we can
find integers such that each remainder is equal to an integer times a plus an(other) integer times b.

Finally, we know by the EA that eventually, the remainder is ZERO. Since the remainder just before is
equal to (a, b), we have shown that this remainder is equal to an integer (this is “r ”) times a plus an
integer (this is “s ”) times b .

♥
The IUT is particularly useful when we apply it to relatively prime numbers.

Definition 13 If a, b ∈ Z , a =0, and b =0, then we say that a and b are relatively prime if

(a,b) = 1

If a and b ∈ Z are relatively prime, then the IUT tells us that there exist integers r and s such that

1= ra + bs.

In the case of relatively prime numbers, the IUT gives 1 the special costume

ra + bs.

84