Greatest Common Divisor (Eucledian)

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₀ = a and r₁ = 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 :)