Page 81 - 'Blast_Into_Math
P. 81
Blast into Math! The Euclidean algorithm: a computational recipe
6. We continue steps 2 and 3 until we end up with remainder zero. Eventually, the remainder
must be zero because each time we divide, the remainder decreases by at least one by the
LDT. So, this means that the algorithm always STOPS, because the total number of times we
can use the LDT is at most |b| times. Exercise: Prove this!
7. By the SPL, the last non-zero remainder is the greatest common divisor.
♥
The wonderful thing about the Euclidean Algorithm is that it is based on the LDT and SPL, which we
have proven. That means they are always true. So, the Euclidean Algorithm will always give the correct
answer (the greatest common divisor). If we program a computer to perform the Euclidean Algorithm,
it will always follow the recipe, and based on the tasty ingredients the computer will always produce a
tasty (and correct) greatest common divisor!
4.4 Greatest common divisors in disguise
Based on the Euclidean Algorithm, we can express the greatest common divisor (a, b) as the sum of
integer multiples of a and b . This can be incredibly useful.
Theorem 4.4.1. (Incredibly Useful Theorem) Let a, b ∈ Z be non-zero. Then there exists r, s ∈ Z such
that (a, b)= ar + bs.
81
