Hello guys, in this article I will take you deeper in the most recognized algorithm of number theory.

Euclid algorithm is the most popular and efficient method to find out GCD (greatest common divisor). So, first what is GCD ? people who didn’t know that, The divisor of 12 and 30 are,

12 = 1,2,3,4,6 and 12
30 = 1,2,3,5,6,10,15 and 30

The common divisor of two number are 1,2,3 and 6 and the largest common divisor is 6, So 6 is the Greatest common Divisor of 12 and 30.

It can be done with this simple implementation.

We start loop from 1 to smallest of the two number until we find a number that divides into both of them.

    int gcd(int a,int b){
int ans=1;

for(int i;i<=min(a,b);i++){

if (a % i == 0 && b % i == 0)

      ans = i;

    }
  }

But Euclid’s method is faster than this naive method, So let’s we follow the Euclidean method to find out the GCD of 4598 and 3211.

We represent the two number to the following way, Dividend should be the large number and Divisor is other number.we will repeat process until the remainder is equal to zero.

Dividend = Divisor * Quotient + Remainder

4598 = 3211 * 1 + 1387

3211= 1387 * 2 + 437

1387 = 437 * 3 + 76

437 = 76 * 5 + 57

76= 57 * 1 + 19

57 = 19 * 3 + 0

At the point remainder is 0 and we get the GCD 19.

Notice that every step dividend and devisor are exchanged and remainder and divisor exchanged. When we remainder is 0 that mean the remaining divisor our GCD.

Here is the implementation in C of the algorithm above.

#include<stdio.h>

int GCD(int a,int b);

int main()
{
      int a,b,gcd;

            scanf("%d %d",&a,&b);
            gcd=GCD(a,b);
            printf("%d\n",gcd);

        return 0;
}

int GCD(int a,int b)
{
      int temp;
      if(a<b){
      temp=b;
      b=a;
      a=temp;
      }
            while(a%b!=0){
              temp=a;
              a=b;
              b=temp%b; 
            }
            return b;
}

There is a recurrence relation of the function that is expressing below,

gcd(4598, 3211) = gcd(3211, 1387) = gcd(1387, 437) = gcd(437, 76) = gcd(76, 57) = gcd(57, 19) = gcd(19, 0) = 19.

So following the relation the function can be represented in the recursive way,

GCD(a,b) = GCD(b,a%b) and the base case is GCD(a,0) = a;

It can written as,

int gcd(int a, int b) { 
  if(b == 0) 
    return a;
  else 
    return gcd(b, a % b);
}

We can easily find out the GCD of more than two number using this formula,

GCD( a, b, c, d ) = GCD( a, GCD( b , GCD( c, d ) ) ).

After finding GCD we can easily calculate LCM ( Latest Common Multiple) of any numbers, the relation between GCD and LCM is,

LCM(a,b) = |a*b|/ GCD(b,a mod b)

Here is a simple function to find out LCM,

int lcm(int a, int b) {
  return a * b / gcd(a, b);
}

It can be overflow that’s why we can optimize the method as follow,

int lcm(int a, int b) {
  return (a / gcd(a, b)) * b;
}

So thats all, I hope I made you understand the method. If you have any question please let me know.

Practice problem : uva -- 11417,11827,11388,1642