Un método de más de dos mil años que sigue en uso
El algoritmo de Euclides encuentra el máximo común divisor de dos enteros repitiendo divisiones con resto. El máximo común divisor, o MCD, es el mayor número positivo que divide a ambos sin dejar resto. Si dividimos el mayor por el menor, sustituimos la pareja por el divisor y el resto. Repetimos hasta obtener resto cero; el último resto no nulo es la respuesta. El método aparece en los Elementos de Euclides y continúa dentro de software matemático y criptográfico porque es simple, exacto y muy eficiente.
Ejemplo con 252 y 105: 252 = 2 × 105 + 42; después 105 = 2 × 42 + 21; por último 42 = 2 × 21 + 0. El último resto no nulo es 21, así que MCD(252, 105) = 21. No fue necesario listar todos los divisores de ninguno de los dos números.
El resto conserva los divisores comunes
Si a = q·b + r, cualquier número que divide tanto a como b también divide a a − q·b, que es r. En sentido contrario, cualquier divisor común de b y r divide q·b + r, que es a. Por eso las parejas (a, b) y (b, r) tienen exactamente los mismos divisores comunes y el mismo MCD. Cada paso reduce el problema sin cambiar la respuesta.
El proceso termina porque los restos son enteros no negativos y cada nuevo resto es menor que el divisor anterior. No puede existir una cadena infinita de enteros que disminuyen de ese modo. Cuando el resto llega a cero, el divisor de esa última división divide al número anterior y, por la propiedad conservada, es el mayor divisor común de la pareja original.
Volver hacia atrás para encontrar una identidad
El algoritmo extendido no solo obtiene el MCD: encuentra enteros x e y tales que ax + by = MCD(a, b). En el ejemplo, 21 = 105 − 2 × 42 y 42 = 252 − 2 × 105. Sustituyendo, 21 = 5 × 105 − 2 × 252. Esta identidad de Bézout convierte una serie de divisiones en coeficientes útiles.
Si MCD(a, n) = 1, a tiene inverso módulo n: existe x tal que ax deja resto 1 al dividir por n. El algoritmo extendido calcula ese x. Los inversos modulares son fundamentales en teoría de números y en sistemas de clave pública. La conexión no convierte el algoritmo por sí solo en cifrado; lo hace una pieza fiable dentro de construcciones mayores.
Por qué no se atasca con números enormes
En cada paso el resto se reduce con rapidez. El peor comportamiento aparece con números consecutivos de Fibonacci, donde los cocientes son pequeños y hacen falta más divisiones, pero aun así el número de pasos crece aproximadamente con el número de cifras, no con el valor del número. Esa diferencia permite trabajar con enteros de cientos o miles de bits.
La implementación debe definir cómo trata signos y cero. Habitualmente MCD(a, 0) = |a| y el resultado se toma no negativo. En lenguajes de programación, la operación resto puede comportarse de forma distinta con números negativos, así que normalizar entradas evita errores. Para enteros gigantes existen variantes que procesan varios cocientes a la vez.
Existe también un algoritmo binario del MCD que reemplaza muchas divisiones por restas y desplazamientos de bits. Aprovecha que los factores de 2 pueden separarse con facilidad y que el MCD de dos impares se conserva al restarlos. En ciertas arquitecturas resulta útil, aunque las bibliotecas modernas eligen variantes según el tamaño de los enteros. Comparar implementaciones exige contar operaciones de máquina, memoria realmente disponible y coste de trabajar con enteros que ocupan muchas palabras digitales.
Fracciones, congruencias y claves
Reducir una fracción a términos irreducibles consiste en dividir numerador y denominador por su MCD. Resolver ecuaciones diofánticas lineales depende de si el MCD divide el término independiente. En la teoría de números, estas relaciones ayudan a estudiar congruencias, divisibilidad y preguntas como la conjetura de Goldbach. El método también aparece en cálculos con polinomios, donde la idea de dividir con resto se conserva.
RSA utiliza inversos modulares durante la construcción de claves y otras técnicas criptográficas recurren a operaciones relacionadas. La transición hacia la criptografía poscuántica cambia algunos problemas difíciles, pero no vuelve inútil la aritmética elemental. Algoritmos antiguos continúan debajo de bibliotecas modernas porque resuelven exactamente una tarea bien definida.
Una receta corta con una comprobación final
Ordena los números de mayor a menor. Divide, guarda el resto y reemplaza la pareja por divisor y resto. Continúa hasta obtener cero. Para comprobar, verifica que el resultado divide a ambos y que los cocientes no esconden un factor común mayor. Si necesitas el inverso, guarda los cocientes y sustituye las ecuaciones hacia atrás.
Su elegancia no nace solo de ser corto. Cada línea tiene una justificación que conserva la solución y una medida que garantiza el final. Esa combinación —invariante y progreso— es una idea central en diseño de algoritmos. Euclides no propuso código informático, pero dejó un procedimiento que puede ejecutarse paso a paso, demostrarse y escalar. Por eso sigue siendo uno de los mejores ejemplos de cómo una prueba matemática puede convertirse directamente en cálculo.
