Now that you have completed Research Question 1, you know that for a pair of integers

aandb, we havegcd( a,b) = gcd(b,r),where

ris the remainder whenais divided byb. (Sure, this gives away the conjecture for Research Question 1, but you already knew the conjecture anyway, right?) Thus, for example, ifa= 123456789 andb= 369 (as in the preceding section), thenr= 90, and we see thatgcd(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 andb= 90, then we may compute the new value ofrbelow.Thus we have gcd(369, 90) = gcd(90, 9). Repeating once again, we have

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

Copyright © 2001 by W. H. Freeman and Company