Euclidean algorithm
From Algorithmist
The Euclidean algorithm is an algorithm for finding the greatest common divisor of two integers.
[edit] Pseudocode
function gcd( a,b : Integer ) returns Integer
{
if ( b != 0 )
return gcd( b, a mod b )
return abs(a)
}
[edit] Explanation
Why does this work?
The fact we need is that gcd(a,b) = gcd(b,a - kb) for any integer k. To see why this is true, let g be any common divisor of a and b. Then g divides a and kb (as it divides b), so it divides their difference a - kb. Conversely, let h be any common divisor of b and a - kb. Then h divides kb (as it divides b) and it divides a - kb, so it divides their sum a. Thus, the set of common divisors of a and b is the same as the set of common divisors of b and a - kb. In particular, their greatest common divisor is the same.
As 
is indeed a number of the form a - kb for some k, our algorithm is justified.
The point of the algorithm is to continue this procedure until one number is 0, because gcd(x,0) = abs(x), which we can then return as our answer.
