Thread: gcd algorithm

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?

Originally Posted by rizleya

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?

a) Assume .

Let be a common divisor of and . Then:

Also as for some .

But and implies that

Hence any common divisor of and is also a common divisor of and .

Now suppose is a common divisor of and . Now:



for some .

So and implies that .

Therefore any common divisor of and is also a common divisor of and .

Thus we have that any common divisor of and is a common divisor of and .
Also that any common divisor of and is a common divisor of and .

Hence .

ZB