Guía: máximo común divisor (MCD)
What is GCD?
El máximo común divisor (MCD) es el mayor número entero que divide sin resto a dos o más enteros. Por ejemplo, MCD(48, 18) = 6, porque 6 es el mayor número que divide exactamente tanto a 48 como a 18. El MCD es un concepto fundamental de la teoría de números y la criptografía.
Euclidean Algorithm
The oldest and most efficient method for calculating GCD is the Euclidean algorithm. It relies on repeated division: GCD(a, b) = GCD(b, a mod b), until b equals 0. For example: GCD(48, 18) → GCD(18, 12) → GCD(12, 6) → GCD(6, 0) = 6. This algorithm is extremely fast and works even for very large numbers.
Properties of GCD
MCD(a, b) * mcm(a, b) = a * b (el producto del MCD y el mcm es igual al producto de los números). Si MCD(a, b) = 1, entonces a y b son primos entre sí. El MCD es siempre menor o igual que el menor de los dos números. MCD(0, a) = |a| para cualquier número a distinto de cero.
Practical Applications
El MCD sirve para simplificar fracciones: se dividen numerador y denominador entre el MCD para obtener una fracción irreducible. En criptografía RSA se emplea al generar claves de cifrado. En informática determina la mayor división común de recursos de memoria o procesador. En música permite determinar intervalos comunes para los ritmos.
Euclides encuentra el divisor de dos números de nueve cifras en tres pasos
Averiguar qué tienen en común dos números parece exigir factorizarlos, y factorizar es lento. El algoritmo de Euclides lo esquiva por completo: mcd(123456789, 987654321) = 9, alcanzado en tres divisiones. La división por tanteo sobre el menor podría haber necesitado 11.111 comprobaciones. El algoritmo tiene más de dos mil años y sigue siendo el que usa cualquier ordenador.
Cómo funciona
- Halla el máximo común divisor de dos o más números con el algoritmo de Euclides.
- Reduce fracciones a su forma irreducible, que es la misma operación con otro traje.
- Informa del número de pasos, ya que la velocidad es todo el asunto.
mcd(a, b) = mcd(b, a mod b), repetido hasta que b = 0 el a restante es la respuesta forma irreducible: a/b dividido por mcd(a, b) en ambas partes coprimos significa mcd = 1 — ningún factor común
Ejemplo resuelto
Euclides con entradas cada vez más desagradables.
- mcd(1071, 462) = 21 en 3 pasos
- mcd(123456789, 987654321) = 9 en 3 pasos
- mcd(2⁴⁰, 3²⁰) = 1 en 15 pasos
- mcd(832040, 514229) = 1 en 28 pasos
- esa última pareja son números de Fibonacci consecutivos: el peor caso que existe
Dos números de nueve cifras se resuelven en tres divisiones. Incluso la entrada deliberadamente peor, una pareja de Fibonacci consecutivos, lleva 28. El recuento crece con el número de cifras, no con el tamaño de los números, y por eso el algoritmo escala hasta valores de cientos de dígitos.
Cómo leer el resultado
- Los números de Fibonacci consecutivos son el peor caso demostrado, y lo son precisamente porque cada división retira lo menos posible. mcd(987, 610) lleva 14 pasos y mcd(75025, 46368) lleva 23: el recuento sube despacio mientras los números explotan.
- Reducir una fracción es un mcd disfrazado. 84/126 comparte un divisor 42 y baja a 2/3 en un paso; el mcd es exactamente el límite de simplificación de cualquier fracción, y dividir por algo menor deja trabajo sin terminar.
- El máximo común divisor y el mínimo común múltiplo son dos mitades de una misma herramienta, unidas por mcd(a,b) × mcm(a,b) = a × b. Tener uno da el otro al coste de una multiplicación y una división.
- El algoritmo de Euclides sostiene la criptografía moderna a través de su forma extendida, que también produce los coeficientes necesarios para los inversos modulares. La generación de claves RSA depende de él, una larga vida póstuma para un procedimiento escrito hacia el 300 a. C.
Preguntas frecuentes
- ¿Por qué no factorizar sin más los dos números?
- Porque factorizar es difícil y Euclides no. Descomponer 123456789 en factores primos es trabajo real; tomar tres restos no lo es. La seguridad de RSA descansa exactamente en esa asimetría: multiplicar y calcular el mcd es barato, factorizar no.
- ¿Qué significa un mcd de 1?
- Que los números son coprimos: no comparten ningún factor mayor que 1. No significa que alguno sea primo — 8 y 9 son coprimos y ninguno lo es. Sí significa que la fracción 8/9 ya es irreducible.