The greatest common divisor (GCD) of two or more integers, when at least one of them is not zero, is the largest positive integer that divides the numbers without a remainder. For example, the GCD of 10 and 15 is 5. (Source – Wiki – http://en.wikipedia.org/wiki/Greatest_common_divisor).
Euclidean Algorithm : The greatest common divisor of two numbers remains the same if the larger number is replaced by its difference with the smaller number. If we keep repeat this process until one of the number becomes 0, then other number will be the GCD. We can solve this recursively.