Finding the GCD and LCM (the Euclidean algorithm)

This lesson covers finding the greatest common divisor and least common multiple using the Euclidean algorithm, giving you a taste of recursive functions along the way. It's written for anyone searching "Python GCD calculation" or "Python math.gcd".

The Euclidean algorithm is an ancient, efficient technique for finding the greatest common divisor (GCD) of two numbers. Python also provides a built-in function, math.gcd(), so you can use it perfectly well in real work without knowing the underlying mechanism.

The sample code finds the GCD with math.gcd(12, 18), and uses that result inside the lcm function to compute the least common multiple. The least common multiple can be computed with the formula (a * b) // math.gcd(a, b) — a classic technique built on top of the GCD.

A common beginner mistake is not understanding why that formula produces the least common multiple. Knowing the mathematical relationship — dividing the product of two numbers by their GCD gives their LCM — lets you implement this with genuine understanding rather than rote memorization. Notice also that // performs integer division.

As a practice topic for learning recursive thinking, it's a well-known algorithm that packs in fundamentals from both math and programming. The least common multiple, easily derived from the GCD, is a calculation worth remembering as a pair.