El Algoritmo de Euclides
El algoritmo de Euclides calcula el máximo común divisor (MCD) de dos enteros mediante divisiones sucesivas. Se apoya en una única observación: todo divisor común de a y b divide también al resto de dividir a entre b. Como los restos decrecen estrictamente, el proceso siempre termina, y el último resto no nulo es el MCD.
Invariante del algoritmo
mcd(a,b)=mcd(b,amodb) La versión extendida y la identidad de Bézout
La versión extendida del algoritmo no solo obtiene el MCD: recorre las mismas divisiones llevando la cuenta de cómo se combina cada resto a partir de los enteros originales. El resultado son dos coeficientes enteros x e y que certifican el MCD como combinación lineal de a y b:
Identidad de Bézout
ax+by=mcd(a,b) La presentación clásica de aula reconstruye esta identidad por sustitución hacia atrás: se despeja el MCD de la última división útil y se van reemplazando los restos anteriores uno a uno. La herramienta muestra ese desarrollo completo, junto con la tabla extendida (r, q, x, y) que ejecuta el mismo cálculo hacia adelante.
Ecuaciones diofánticas lineales
Una ecuación diofántica lineal busca soluciones enteras de ax + by = c. El criterio de solubilidad es directo: existe solución si y solo si mcd(a, b) divide a c. En ese caso, escalar la identidad de Bézout por c/g produce una solución particular, y todas las demás se obtienen desplazándose a lo largo de la recta:
Familia completa de soluciones
x=x0+gbt,y=y0−gat,t∈Z Congruencias lineales e inverso modular
La congruencia ax ≡ b (mod n) es la misma ecuación diofántica disfrazada: ax − ny = b. Con g = mcd(a, n), hay solución si y solo si g divide a b; y cuando la hay, existen exactamente g clases de soluciones módulo n, espaciadas n/g entre sí. El caso g = 1 es el más importante: la solución es única y se obtiene multiplicando por el inverso modular a⁻¹, que es precisamente la solución de ax ≡ 1 (mod n) y sale gratis del propio algoritmo extendido.
Guía de uso de la herramienta
- MCD y Bézout: ingresá dos enteros (admite negativos y cero) y obtené MCD, MCM, coeficientes x e y, las divisiones sucesivas, la sustitución hacia atrás y la comprobación numérica completa.
- Diofántica lineal: resolvé ax + by = c con el criterio de solubilidad explícito, una solución particular canónica y la familia completa parametrizada por t.
- Congruencia lineal: resolvé ax ≡ b (mod n) con reducción canónica visible, todas las clases de solución (o su forma paramétrica) y el inverso modular cuando existe.
- Aritmética exacta: todos los cálculos usan enteros de precisión arbitraria (hasta 40 dígitos por entrada); no hay redondeos en ningún paso.
Convenciones del módulo
Casos con cero
mcd(a, 0) = |a| y mcd(0, 0) = 0 (convención estándar); mcm(a, 0) = 0. El MCD se reporta siempre no negativo.
Soluciones canónicas
En la diofántica, la solución particular se normaliza a 0 ≤ x₀ < |b/g|; en la congruencia, a y b se reducen primero al rango [0, n). Así el resultado es único y reproducible.
Enumeración de clases
Una congruencia con g clases se enumera completa hasta g = 12; por encima se entrega la forma paramétrica x ≡ x₀ (mod n/g), que las describe todas.
El peor caso: Fibonacci
El teorema de Lamé (1844) — considerado el primer análisis de complejidad de un algoritmo — demuestra que el peor caso de Euclides ocurre con números de Fibonacci consecutivos: la cantidad de divisiones nunca supera cinco veces la cantidad de dígitos decimales del menor operando.
Con el límite de 40 dígitos de esta herramienta, el desarrollo más largo posible ronda las 190 divisiones (por ejemplo, dos Fibonacci consecutivos de 40 dígitos), que la tabla muestra completas.
Referencias
- Euclides, Elementos, Libro VII, Proposiciones 1–2 (c. 300 a.C.) — la formulación original por sustracciones sucesivas.
- Bachet, C.-G. (1624). Problèmes plaisants et délectables — primera solución completa de la ecuación lineal en enteros; la identidad lleva el nombre de Bézout por su generalización posterior a polinomios.
- Lamé, G. (1844). "Note sur la limite du nombre des divisions…". C. R. Acad. Sci. Paris, 19, 867–870.
- Niven, I., Zuckerman, H. S. y Montgomery, H. L. (1991). An Introduction to the Theory of Numbers (5.ª ed.). Wiley — cap. 1–2.
- Knuth, D. E. (1997). The Art of Computer Programming, Vol. 2, §4.5.2 — análisis del algoritmo de Euclides y su versión extendida.