Euclidean algorithm

:This article is not about Euclidean geometry.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The Euclidean algorithm (also called Euclid's algorithm) is an algorithm to determine the greatest common divisor (gcd) of two integers. It is one of the oldest algorithms known, since it appeared in Euclid's Elements around 300 BC. However, the algorithm probably was not discovered by Euclid and it may have been known up to 200 years earlier. It was almost certainly known by Eudoxus of Cnidus (about 375 BC); and Aristotle (about 330 BC) hinted at it in his Topics, 158b, 29-35. The algorithm does not require factoring the two integers.

Related Topics:
Algorithm - Greatest common divisor - Integer - Euclid's ''Elements'' - 300 BC - Eudoxus of Cnidus - Aristotle - Factoring

~ ~ ~ ~ ~ ~ ~ ~ ~ ~