The greatest common divisor (GCD) of two integers *a* and
*b* is defined to be the largest integer that divides both
*a* and *b* with no remainder. For example, the GCD of
16 and 28 is 4. In chapter 2, when we investigate how to implement
rational-number arithmetic, we will need to be able to compute GCDs in
order to reduce rational numbers to lowest terms. (To reduce a
rational number to lowest terms, we must divide both the numerator and
the denominator by their GCD. For example, 16/28 reduces to 4/7.)
One way to find the GCD of two integers is to factor them and search
for common factors, but there is a famous algorithm that is much more
efficient.

The idea of 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 precisely
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(206,40) = GCD(40,6) = GCD(6,4) = GCD(4,2) = GCD(2,0) = 2reduces GCD(206,40) to GCD(2,0), which is 2. It is possible to show that starting with any two positive integers and performing repeated reductions will always eventually produce a pair where the second number is 0. Then the GCD is the other number in the pair. This method for computing the GCD is known as

It is easy to express Euclid's Algorithm as a procedure:

This generates an iterative process, whose number of steps grows as the logarithm of the numbers involved.(define (gcd a b) (if (= b 0) a (gcd b (remainder a b))))

The fact that the number of steps required by Euclid's Algorithm has logarithmic growth bears an interesting relation to the Fibonacci numbers:

** Lamé's Theorem:** If Euclid's Algorithm requires *k*
steps to compute the GCD of some pair, then the smaller number in the
pair must be greater than or equal to the *k*th Fibonacci
number. ^{43}

We can use this theorem to get an order-of-growth estimate for
Euclid's Algorithm. Let *n* be the smaller of the two inputs
to the procedure. If the process takes *k* steps, then we must
have _{}. Therefore the number of steps
*k* grows as the logarithm (to the base _{}) of *n*. Hence, the order of growth is
_{}.

**Exercise 1.20**

The process that a procedure generates is of course dependent on the
rules used by the interpreter. As an example, consider the iterative
`gcd` procedure given above. Suppose we were to interpret this
procedure using normal-order evaluation, as discussed in section
1.1.5. (The normal-order-evaluation rule for `if` is described
in exercise 1.5.) Using the substitution method (for normal order),
illustrate the process generated in evaluating `(gcd 206 40)`
and indicate the `remainder` operations that are actually
performed. How many `remainder` operations are actually
performed in the normal-order evaluation of `(gcd 206 40)`? In
the applicative-order evaluation?