Consider the problem of fi nding the greatest common divisor (gcd) of two positive integers a and b . The algorithm presented here is a variation of Euclid’s algorithm, which is based on the following theorem: 4 Theorem. If a and b are positive integers with a > b such that b is not a divisor of a , then gcd ( a , b ) = gcd ( b , a mod b ). This relationship between gcd ( a , b ) and gcd ( b , a mod b ) is the heart of the recursive solution. It specifi es how you can solve the problem of computing gcd ( a , b ) in terms of another problem of the same type. Also, if b does divide a , then b = gcd ( a , b ), so an appropriate choice for the base case is ( a mod b ) = 0.

This theorem leads to the following recursive defi nition:

The following function implements this recursive algorithm:

a. Prove the theorem.

b. What happens if b > a ?

c. How is the problem getting smaller? (That is, do you always approach a base case?) Why is the base case appropriate?