Given two integers, a and b, returns their greatest common divisor, gcd(a,b). It is perhaps the first known algorithm, dating back well over two millenia! Commonly attributed to Euclid.
if a>b
swap(a,b)
while a>0 {
x = b mod a
b = a
a = x
}
return b
(Strictly speaking, this is only for natural numbers; you should first take the absolute value of a and b...)
Obviously this algorithm terminates, since at every pass through the loop a is assigned the result of a "mod a" operation, which necessarily decreases it. a is always non-negative, so only a finite number of passes may occur.
The way it works is simple. At the beginning of every pass, the gcd of the values of a and b is the same as the gcd of the original inputs. To show this, we note that b mod a is b minus a multiple of a; therefore, any common divisor of a and b is a common divisor of a and b mod a, and vice versa, so the gcds must be identical. At the last step, it returns b, which is just right! (gcd(0,b)=b, since any natural number divides 0 -- it's not just a quibble: consider the last step, which starts with b a multiple of a)
Note that this algorithm will work in any ring, not just the integers.