Calculadora del Algoritmo Euclidiano Extendido

La Calculadora del Algoritmo Euclidiano Extendido calcula el Máximo Común Divisor (MCD) de dos números enteros y halla los coeficientes de Bézout, es decir, los enteros s y t que satisfacen mcd(a, b) = s·a + t·b. Además de calcular el MCD, esta herramienta proporciona una tabla de división paso a paso totalmente animada, sustitución hacia atrás y el cálculo del inverso modular, lo que la hace ideal para cursos de teoría de números, estudio de criptografía y programación competitiva.

¿Qué es el algoritmo de Euclides extendido?

El algoritmo de Euclides extendido (AEE) es una extensión del algoritmo clásico de Euclides para el MCD. Mientras que el algoritmo básico encuentra el mcd(a, b) mediante divisiones sucesivas, la versión extendida rastrea simultáneamente dos secuencias de números enteros que registran cómo cada resto puede expresarse como una combinación lineal de las entradas originales.

Cómo funciona el algoritmo

El AEE mantiene tres pares de valores — (r, s, t) — a través de cada paso de la división:

1. Inicializar: r₀ = |a|, r₁ = |b|, s₀ = 1, s₁ = 0, t₀ = 0, t₁ = 1
2. Cada paso: calcular el cociente q = ⌊rₙ₋₁ / rₙ⌋, luego actualizar rₙ₊₁ = rₙ₋₁ − q·rₙ, sₙ₊₁ = sₙ₋₁ − q·sₙ, tₙ₊₁ = tₙ₋₁ − q·tₙ
3. Detenerse cuando el resto = 0; el resto anterior es el mcd(a, b)
4. Los valores s y t correspondientes son los coeficientes de Bézout

Ejemplo paso a paso: mcd(252, 105)

Resultado: mcd(252, 105) = 21, con la identidad de Bézout: 21 = (−2) × 252 + 5 × 105 (s = −2, t = 5). Pruébalo tú mismo con la calculadora de arriba para obtener los coeficientes exactos.

Aplicaciones del algoritmo de Euclides extendido

1. Inverso modular (Criptografía)

La aplicación más importante es el cálculo de inversos modulares. Si mcd(a, m) = 1, entonces el coeficiente de Bézout s satisface:

Los inversos modulares son esenciales en el cifrado RSA (cálculo del exponente de la clave privada d), el intercambio de claves Diffie-Hellman y la criptografía de curva elíptica.

2. Resolución de ecuaciones diofánticas lineales

La ecuación ax + by = c tiene soluciones enteras si y solo si mcd(a, b) divide a c. De ser así, una solución particular es x₀ = s·(c/d), y₀ = t·(c/d) donde d = mcd(a, b) y s, t son los coeficientes de Bézout.

3. Teorema chino del resto

El AEE se utiliza en la prueba constructiva y el cálculo del teorema chino del resto — hallando x tal que x ≡ a₁ (mod m₁) y x ≡ a₂ (mod m₂) — mediante el cálculo de los inversos modulares de los módulos.

4. Reducción de fracciones y MCM

mcd(a, b) = 1 confirma que a/b ya está en su mínima expresión. El MCM es mcm(a, b) = |a·b| / mcd(a, b).

Los coeficientes de Bézout no son únicos

Los coeficientes de Bézout s y t no son únicos. Si (s, t) es una solución, entonces (s + k·(b/d), t − k·(a/d)) también es una solución para cualquier entero k, donde d = mcd(a, b). El AEE devuelve la solución donde |s| ≤ |b/d| y |t| ≤ |a/d|.

Complejidad temporal

El algoritmo de Euclides extendido se ejecuta en O(log min(a, b)) iteraciones, al igual que el algoritmo de Euclides básico. Según el teorema de Lamé, el número de pasos nunca supera 5 veces el número de dígitos decimales de la entrada más pequeña. Esto lo hace extremadamente eficiente incluso para los grandes números enteros utilizados en aplicaciones criptográficas.

Preguntas frecuentes

¿Qué es el algoritmo de Euclides extendido?

El algoritmo de Euclides extendido amplía el algoritmo para el MCD de Euclides para calcular también los coeficientes de Bézout s y t que satisfacen mcd(a, b) = s·a + t·b. Rastrea cómo cada resto puede expresarse como una combinación lineal de a y b a lo largo del proceso de división.

¿Qué son los coeficientes de Bézout?

Los coeficientes de Bézout son números enteros s y t cuya existencia está garantizada por la identidad de Bézout (un teorema de la teoría de números). Satisfacen mcd(a, b) = s·a + t·b y se calculan eficientemente mediante el algoritmo de Euclides extendido. Se utilizan en el cálculo del inverso modular, la resolución de ecuaciones diofánticas y el teorema chino del resto.

¿Cómo encuentro el inverso modular usando el algoritmo de Euclides extendido?

Si mcd(a, b) = 1 (a y b son coprimos), el coeficiente de Bézout s satisface s·a ≡ 1 (mod b). El inverso modular de a mod b es s mod b (ajustado para ser positivo). Esta calculadora muestra esto directamente en los resultados.

¿Cuándo no existe el inverso modular?

El inverso modular de a módulo m existe si y solo si mcd(a, m) = 1. Si mcd(a, m) > 1, ningún número entero x satisface a·x ≡ 1 (mod m).

¿Cuál es la complejidad temporal del algoritmo de Euclides extendido?

O(log min(a, b)) divisiones, igual que el algoritmo de Euclides básico. Por el teorema de Lamé, el número de pasos está limitado por 5 veces el número de dígitos decimales de la entrada más pequeña, lo que lo hace muy eficiente.