MDC (Algoritmo de Euclides)

Euclidean algorithm for the greatest common divisor

The Euclidean algorithm finds gcd(a, b) by applying the identity gcd(a, b) = gcd(b, a mod b) over and over until b = 0. Whatever value of a is left at that point is the GCD. You'll find it in Euclid's Elements (~300 BC), Book VII, which makes it one of the oldest non-trivial algorithms people still run every day. Its complexity is O(log min(a, b)), and Lamé's theorem tells us the slowest case happens with consecutive Fibonacci numbers as inputs.

Here's a run: gcd(48, 18) → gcd(18, 12) → gcd(12, 6) → gcd(6, 0) = 6. There's also the extended Euclidean algorithm, which hands back Bézout coefficients x, y satisfying a·x + b·y = gcd(a, b). That's the route used to compute modular inverses.

Applications

• Cryptography: the modular inverse behind RSA key generation and ECDSA comes from extended Euclid.
• Simplifying fractions: divide both parts of a/b by gcd(a, b) and you land on the lowest terms.
• Diophantine equations: ax + by = c only has integer solutions when gcd(a, b) divides c.
• Competitive programming: a go-to for number-theory problems and reductions.

FAQ

What is gcd(a, 0)? By convention it's gcd(a, 0) = |a|, and that serves as the base case of the recursion.

Does it work with negative numbers? Yes. Most implementations take absolute values up front, because the GCD is defined to be non-negative.

What about gcd of more than two numbers? Lean on associativity and chain them: gcd(a, b, c) = gcd(gcd(a, b), c).