Euclidean Gcd Algorithm

Given two integers a and b, find their Greatest Common Divisor (GCD) using the Euclidean Algorithm. Also compute the Least Common Multiple (LCM) using $\text{LCM}(a, b) = \frac{a \times b}{\gcd(a, b)}$.

The Euclidean Algorithm is based on the identity $\gcd(a, b) = \gcd(b, a \bmod b)$. Repeatedly replacing the larger number with the remainder shrinks the problem rapidly ($O(\log \min(a, b))$ steps) compared to the naive approach of checking every divisor from 1 to $\min(a, b)$ ($O(N)$ steps).

1. While b != 0, compute a, b = b, a % b.
2. When b == 0, a holds the GCD.
3. Compute LCM as a * b // gcd(a, b) using the formula $\text{LCM}(a, b) = \frac{a \times b}{\gcd(a, b)}$.
4. Use // (integer division) to avoid floating-point issues.

• Dividing after multiplying can cause integer overflow in languages with fixed-size integers; in Python this isn't an issue
• Forgetting that gcd(0, n) = n — the Euclidean stopping condition handles this correctly
• Using a / b (float division) instead of a // b in the LCM formula

The Euclidean Algorithm is one of the oldest algorithms in existence (~300 BCE). Its $O(\log N)$ performance comes from the Fibonacci numbers being the worst case — consecutive Fibonacci numbers require the maximum number of steps for any pair of that size.