Calculadora del Algoritmo Euclidiano Extendido
Calcula el MCD de dos números enteros y encuentra los coeficientes de Bézout usando el Algoritmo de Euclides Extendido, con tabla paso a paso, sustitución inversa e inverso modular.
Tu bloqueador de anuncios impide que mostremos anuncios
MiniWebtool es gratis gracias a los anuncios. Si esta herramienta te ayudó, apóyanos con Premium (sin anuncios + herramientas más rápidas) o añade MiniWebtool.com a la lista de permitidos y recarga la página.
- O pásate a Premium (sin anuncios)
- Permite anuncios para MiniWebtool.com y luego recarga
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.
donde s y t son los coeficientes de Bézout (enteros, posiblemente negativos)
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:
- Inicializar: r₀ = |a|, r₁ = |b|, s₀ = 1, s₁ = 0, t₀ = 0, t₁ = 1
- Cada paso: calcular el cociente q = ⌊rₙ₋₁ / rₙ⌋, luego actualizar rₙ₊₁ = rₙ₋₁ − q·rₙ, sₙ₊₁ = sₙ₋₁ − q·sₙ, tₙ₊₁ = tₙ₋₁ − q·tₙ
- Detenerse cuando el resto = 0; el resto anterior es el mcd(a, b)
- Los valores s y t correspondientes son los coeficientes de Bézout
Ejemplo paso a paso: mcd(252, 105)
| Paso | Dividendo | Divisor | Cociente | Resto | s | t |
|---|---|---|---|---|---|---|
| 1 | 252 | 105 | 2 | 42 | 1 | 0 |
| 2 | 105 | 42 | 2 | 21 | 0 | 1 |
| 3 | 42 | 21 | 2 | 0 | 1 | -2 |
Resultado: mcd(252, 105) = 21, con la identidad de Bézout: 21 = (−1) × 252 + (5/2)... En realidad: 21 = 1 × 252 + (−2) × 105 = 42. 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.
Recursos adicionales
Cite este contenido, página o herramienta como:
"Calculadora del Algoritmo Euclidiano Extendido" en https://MiniWebtool.com/es// de MiniWebtool, https://MiniWebtool.com/
por el equipo de miniwebtool. Actualizado: 18 de febrero de 2026
También puede probar nuestro Solucionador de Matemáticas AI GPT para resolver sus problemas matemáticos mediante preguntas y respuestas en lenguaje natural.