Wikipedia:Today's featured article/June 18, 2009

The Euclidean algorithm is an efficient method for computing the greatest common divisor (GCD). 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. Euclid's algorithm was first described in Euclid's Elements (c. 300 BC), making it one of the oldest numerical algorithms still in common use. The original algorithm was described only for natural numbers and geometric lengths (real numbers), but the algorithm was generalized in the 19th century to other types of numbers, such as Gaussian integers and polynomials of one variable. This led to modern abstract algebraic notions such as Euclidean domains. The Euclidean algorithm has been generalized further to other mathematical structures, such as knots and multivariate polynomials. The Euclidean algorithm has many theoretical and practical applications. It is a key element of the RSA algorithm, a public-key encryption method widely used in electronic commerce. (more...)

Recently featured: Richmond Bridge, London – William D. Boyce – Michael Tritter