1. 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?

2. 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 $\displaystyle A>B,\ A,B>0$.

Let $\displaystyle r$ be a common divisor of $\displaystyle A$ and $\displaystyle B$. Then:

Also as $\displaystyle A>B,\ A=\lambda B+\rho, \ 0 \le \rho<B$ for some $\displaystyle \lambda, \rho \ge 0$.

But $\displaystyle r|A$ and $\displaystyle r|B$ implies that $\displaystyle r|\rho$

Hence any common divisor of $\displaystyle A$ and $\displaystyle B$ is also a common divisor of $\displaystyle B$ and $\displaystyle \rho=A \mod B$.

Now suppose $\displaystyle s$ is a common divisor of $\displaystyle B$ and $\displaystyle C=A \mod B$. Now:

$\displaystyle A=\kappa B+C$

for some $\displaystyle \kappa \in \mathbb{N}$.

So $\displaystyle s|B$ and $\displaystyle s|C$ implies that $\displaystyle s|A$.

Therefore any common divisor of $\displaystyle B$ and $\displaystyle C=A \mod B$ is also a common divisor of $\displaystyle A$ and $\displaystyle B$.

Thus we have that any common divisor of $\displaystyle A$ and $\displaystyle B$ is a common divisor of $\displaystyle B$ and $\displaystyle A \mod B$.
Also that any common divisor of $\displaystyle B$ and $\displaystyle A \mod B$ is a common divisor of $\displaystyle A$ and $\displaystyle B$.

Hence $\displaystyle \gcd(A,B)=\gcd(B, A \mod B)$.

ZB