The Euclidean Algorithm is one of the first algorithms ever written down. It is a darling of computer science. The algorithm cleverly reveals the greatest common divisor of two natural numbers. Despite its ancient origins, it is still well-used today (and not just for teaching). It can determine when two numbers are relatively prime – ie, when their greatest common divisor is one – which has important modern applications in cryptography
Euclid’s Algorithm: An Analysis » Adam Klein’s Blog

Source: blog.adamdklein.com