Entradas

a\,x + b\,y = \operatorname{mcd}(a,b)

Entero a

Entero b

Enteros de hasta 40 dígitos, con signo opcional.

Ejemplos

MCD(a, b)

MCM(a, b)

5520

Coeficiente x

−9

Coeficiente y

Identidad de Bézout

240·(−9) + 46·47 = 2

Desarrollo y comprobación

Divisiones sucesivas

240 = 5·46 + 10

46 = 4·10 + 6

10 = 1·6 + 4

6 = 1·4 + 2

4 = 2·2 + 0

Sustitución hacia atrás

2 = 1·6 − 1·4

2 = (−1)·10 + 2·6

2 = 2·46 − 9·10

2 = (−9)·240 + 47·46

Comprobación

Identidad a·x + b·y = mcd

−2160 + (2162) = 2

El MCD divide a ambos enteros

2 | 240 ∧ 2 | 46

mcd · mcm = |a·b|

2 · 5520 = 11040

Fundamentos y Explicación

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

\operatorname{mcd}(a,b) = \operatorname{mcd}(b,\; a \bmod b)

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

a\,x + b\,y = \operatorname{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 = x_0 + \tfrac{b}{g}\,t, \qquad y = y_0 - \tfrac{a}{g}\,t, \qquad t \in \mathbb{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.

Euclides Extendido: MCD, Bézout y Congruencias

Entradas

Ejemplos

Identidad de Bézout

Desarrollo y comprobación

Divisiones sucesivas

Sustitución hacia atrás

Comprobación

Fundamentos y Explicación

El Algoritmo de Euclides

La versión extendida y la identidad de Bézout

Ecuaciones diofánticas lineales

Congruencias lineales e inverso modular

Guía de uso de la herramienta

Convenciones del módulo

El peor caso: Fibonacci

Referencias

El Algoritmo de Euclides

La versión extendida y la identidad de Bézout

Ecuaciones diofánticas lineales

Congruencias lineales e inverso modular

Guía de uso de la herramienta

Convenciones del módulo

El peor caso: Fibonacci

Referencias