Greatest Common Divisor

To become a good coder, knowledge of concepts of maths are essential. GCD or Greatest Common Divisor of two or more integers, when at least one of them is not zero, is the largest positive integer that divides both the numbers completely without leaving a remainder.
    For example GCD of 8 and 12 is '4'. Wondering Y?? Lemme Xplain :P

Let us assume two integers 'a' and 'b'. Let 'x' be the largest integer that can divide both 'a' and 'b' completely without leaving a remainder. Any guess about , What can be the range of 'x'??

1<='x'<=minimum(a,b)

Y so?? Let us consider the example above shown:- gcd(12,8)=4 . let me write the possible values of x for 'a'=12 and 'b'=8 x={1,2,3,4,5,6,7,8}; if we consider an integer greater than 8 then then the value of (b/x) is 0 because the denominator in such a case becomes greater than the numerator so the ratio is less than 1. Now, From all the values of set 'x' the numbers that divide 'a' and 'b' completely are [1,2,4], but among these three values the largest number that divides both 'a' and 'b' completely is '4'. Hence gcd(12,8)=4.

Now how to compute gcd very fast... A serious issue :D

Before that lemme show some of the properties of divisibility that we will need in future. Theorem 1 : let 'a' be an integer and 'b' be a positive integer, then there are unique integers q and r, with 0<=r<b such that a=(b*q)+r : Rule of divisibility. That is if we divide 'a' by 'b' then 'q' denotes the quotient and 'r' denotes the remainder and we can write them as a=(b*q)+r. for example a=9 and b=2. So when 9 is divided by 2 we get 4 as our quotient and 1 as the remainder. So 9=(4*2)+1. And the remainder is always 0<=r<b.

Theorem 2. If 'a' is divisible by 'x' and 'b' is also divisible by 'x', then (a+b) is also divisible by 'x' as well as (a-b) is also divisible x. Reason :- If 'a' is divisible by x we can write it as a=q*x+0

for some quotient q and remainder r=0

      Similarly , if 'b' is divisible by 'x then
                     b=k*x+0

     for some quotient k and remainder r=0

     Now, a=q*x            :-equation 1
          b=k*x            :-equation 2
     So =>a+b
        from equation 1 and equation 2
        =>( q*x ) + ( k*x )
        taking x common we get
        =>x*( q+k )
     So we get,
         => ( a+b ) = x*( q+k )
         => ( a+b ) = x*( q+k ) + 0          :-equation 3
         let u=( a+b ) and  v = ( q+k )
         =>    u    = x*v + 0
     So, u is divisible by x , as the equation states because the remainder part is zero.
     Thus, as u=(a+b) , so, (a+b) is divisible by x . 
     Hence Proved

Similarly we can show that (a-b) is divisible by x. You can check this by yourself :) Just start with (a-b) instead of (a+b) and follow the steps above.

Now back to GCD .. Hell yeah. Let 'a' and 'b' be two integers and let 'g' be their greatest common divisor. So, gcd(a,b)=g;

So 'g' is an integer that divides both 'a' and 'b' completely without leaving any remainder,So we can write them as :

'a' is divisible by 'g'. So, => a=p*g+0 :equation 4 'b' is divisible by 'g'. So, => b=q*g+0 :equation 5

here p and q are the quotients when a and b are divided by g respectively.

Now, By rule of divisbility if we divide a by b , we can write the equation as: a=t*b+rem here t is the quotient and rem is the remainder. Now, =>a-t*b=rem Substituting the values of a and b from equation 4 and 5 we get: =>(p*g) — t*(q*g) = rem Taking g as common we get: =>g*( p — (t*q) ) = rem This equation can be rewritten as : =>[g*{ p — (t*q) }] + 0 = rem Sounds similar right. This means that 'rem' is divisible by 'g', as the remainder of the equation is zero. So, 'g' not only divides 'a' and 'b' completely but also divides the remainder obtained when a is divided by b.
Thus we can say that: gcd(a,b)=gcd(b,remainder when a is divided by b) we derived it right and this even reduces our computations now So, gcd(a,b)=gcd(b,r) where r is the remainder when a is divided by b. Now, terminating condition because we cant forever go on computing the remainder and never stop. We need to stop right.

Remember i told u that the set of values 'x' for gcd(a,b) is actually 1<=x<=minimum(a,b). Assume a>=b. Now what if 'b' divides 'a' completely without leaving a remainder in such a case the largest integer dividing both 'a' and 'b' is 'b' itself , So the set of x contains 'b' as a possible value for our gcd computation and also 'b' is the largest value in our range of set 'x' hence gcd is 'b' itself. Example gcd(12,4)=4 itself. Baaammmmmm. Now we got our trick to end computing.

Lets start coding:

C Code:

include<stdio.h>

int gcd(int a,int b) { if(a%b==0) return b; else return gcd(b,a%b); } int main() { int a,b; printf("Enter the numbers\n"); scanf("%d %d",&a,&b); int x=gcd(a,b); printf("GCD of %d and %d is %d\n" ,a,b,x); return 0; }

ideone link :-

Java Code

import java.io.*; import java.util.*; class GCD { public static void main(String args[])throws IOException { Scanner sc=new Scanner(System.in); System.out.println("Enter the numbers"); int a=sc.nextInt(); int b=sc.nextInt(); System.out.println("GCD of a and b is "+gcd(a,b)); } static int gcd(int a,int b) { if(a%b==0) return b; else return gcd(b,a%b); }

}

ideone link :-

Happy Coding. Pardon tying Errors :D

Related Questions:

1. CodeForces Problem
2. CodeChef Problem
3. Spoj Problem