Section 2.2: The Euclidean Algorithm 1

2.2 The Euclidean Algorithm 1

Now that you have completed Research Question 1, you know that for a pair of integers a and b, we have
gcd(a, b) = gcd(b, r),
where r is the remainder when a is divided by b. (Sure, this gives away the conjecture for Research Question 1, but you already knew the conjecture anyway, right?) Thus, for example, if a = 123456789 and b = 369 (as in the preceding section), then r = 90, and we see that
gcd(123456789, 369) = gcd(369, 90).
It's clear that computing gcd(369, 90) will be easier than computing gcd(123456789, 369). (This will be true using any of the methods discussed in the previous chapter.) But rather than trying to compute gcd(369, 90), why don't we make the problem even easier by repeating what we did above? If now we think of a = 369 and b = 90, then we may compute the new value of r below.
Your browser does not support java.
Thus we have gcd(369, 90) = gcd(90, 9). Repeating once again, we have
Your browser does not support java.
It shouldn't be surprising that the remainder in this case is equal to 0. After all, it's easy to see that 90/9 = 10. Thus 9 is a divisor of 90, so that we have gcd(90, 9) = 9. Finally, we just string all of this together to arrive at
gcd(123456789, 369) = gcd(369, 90) = gcd(90, 9) = 9.
The process illustrated is called the Euclidean Algorithm, and it is very efficient for computing gcds. In fact, this is the method that this web page uses for computing greatest common divisors.

Exercise 1
Repeat the above procedure to compute gcd(7920, 4536).

Section 2.1 | Section 2.2 | Section 2.3 | Section 2.4 | Section 2.5
Chapter 2 | DNT Table of Contents