Greatest Common Divisor (GCD for short) is the largest positive integer that divides two numbers. In other words, the greatest common divisor of

*a* and

*b* is, as its name suggests, the largest positive integer

*d* such that

*d* |

*a* and

*d* |

*b*. In this post, we will see how we can calculate GCD efficiently using an algorithm that is known as

**Eucledian Algorithm**.

The key thing in this algorithm is

*division with remainder*, which is simply the method of "long division" that you learned in elementary school. Thus if

*a* and

*b* are positive integers and if you attempt to divide

*a* by

*b*, you will get a quotient

*q* and a reminder

*r*.

Below is the theorem used for this algorithm:

Let *a* and *b* be positive integers with a >= b. The following algorithm computes gcd(a,b) in a finite number of steps.

(1) Let r_{0} = a and r_{1} = b

(2) Set i = 1

(3) Divide r_{i-1} by r_{i} to get a quotient q_{i} and remainder r_{i+1}, r_{i-1} = r_{i}.q_{i} + r_{i+1} with 0 <= r_{i+1} <= r_{i}

(4) If the remainder r_{i+1} = 0, then r_{i}=gcd(a,b) and the algorithm terminates.

(5) Otherwise, r_{i+1} > 0, so set i = i + 1 and go to Step 3.

Below is the sample source code on how it is implemented using the C programming language

int gcd ( int number1 , int number2 )
{
if ( number2 == 0 )
return number1 ;
else
return gcd ( number2 , number1 % number2 ) ;
}

Hope it helps anyone who needs it. Happy Programming :)