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.
