Results 1 to 2 of 2

Math Help - gcd algorithm

  1. #1
    Newbie
    Joined
    Dec 2007
    Posts
    1

    Thumbs up 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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    May 2006
    Posts
    244
    Quote Originally Posted by rizleya View Post
    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 A>B,\ A,B>0.

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

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

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

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

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

    A=\kappa B+C

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

    So s|B and s|C implies that s|A.

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

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

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

    ZB
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. algorithm
    Posted in the Advanced Applied Math Forum
    Replies: 3
    Last Post: January 19th 2010, 02:46 AM
  2. Algorithm
    Posted in the Advanced Math Topics Forum
    Replies: 7
    Last Post: November 22nd 2009, 07:11 AM
  3. Algorithm help
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: November 12th 2009, 04:10 AM
  4. algorithm
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: July 16th 2008, 01:29 PM
  5. Algorithm
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 27th 2008, 01:02 PM

Search Tags


/mathhelpforum @mathhelpforum