Tuesday, 7 July 2009

The Euclidean algorithm

The Euclidean algorithm is an efficient method for computing the greatest common divisor. It is named for the ancient Greek mathematician Euclid, who first described it.

The GCD of two numbers is the largest number that divides both of them without leaving a remainder.

The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the smaller number is subtracted from the larger number.

See <http://en.wikipedia.org/wiki/Euclidean_algorithm>

No comments: