greatest common divisor (idea)

For two integers a and b, gcd(a,b) is the greatest natural number which is a divisor of both a and b. To compute the gcd, Euclid came up with an excellent algorithm, unsurprisingly known as Euclid's Algorithm.