Euclid's Algorithm for finding greatest common divisor

The Euclidean algorithm is a very efficient method to find the greatest common divisor (GCD) for a pair of integers. The algorithm is based on the principle that the GCD for a pair does not change if the smaller number is subtracted from the bigger number.

Given interger $a$ and $b$ (assume $a\geq b$), the algorithm can be recursively define as:
$$gcd(a,0)=a$$
$$gcd(a,b)=gcd(b, a\: mod\: b)$$

Reference: Wiki page on Euclidean Algorithm.