Consider the problem of finding the Greatest Common Divisor (GCD) of 2 positive integers A and B.The algorithm presented here is a variation of Euclids which is based on the following theorem:

Theorem:If a and b are positive with a greater than b such that b is not a divisor of A,then GCD (A,B) and GCD (B,A mod B) is the heart of the recursive solution.It specifies 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 definition:

GCD(A,B)={B

{GCD (B,A mod B)

if (A mod B)=0 otherwise the following function implements this recursive algorithm:

int GCD (int A,int B)

{

if (A%B==0)// base case

return B;

else return GCD(B,A %B);

}

a)Prove the theorem

b)what will happen if B>A?

c)How is the problem smaller?(that is do you always approach a base case?)

d)why is this base case appropriate?