next up previous
Next: What to turn in Up: Rational numbers Previous: Modifers and functions

Calculating GCDs

(This section is based on page 44 of Ableson and Sussman's Structure and Interpretation of Computer Programs.)

The following algorithm is known as Euclid's Algorithm because it appears in Euclid's Elements (Book 7, ca. 300 B.C.). It may be the oldest nontrivial algorithm.

The algorithm is based on the observation that, if r is the remainder when a is divided by b, then the common divisors of a and b are the same as the common divisors of b and r. Thus we can use the equation

    GCD(a, b) = GCD(b, r)

to successively reduce the problem of computing a GCD to the problem of computing the GCD of smaller and smaller pairs of integers. For example,

    GCD(36, 20) = GCD(20, 16) = GCD(16, 4) = GCD(4, 0) = 4

implies that the GCD of 36 and 20 is 4. It can be shown that for any two starting numbers, this repeated reduction eventually produces a pair where the second number is 0. Then the GCD is the other number in the pair.



Allen Downey
Thu Sep 7 11:50:06 EDT 2000