Calculadora del algoritmo de Euclides extendido
Introduce dos números enteros para obtener su máximo común divisor y los coeficientes de Bézout x e y con a·x + b·y = mcd(a, b). Cada división, cociente y coeficiente se muestra en una tabla que puedes seguir a mano o descargar.
Última actualización:
Número entero, puede ser negativo o muy grande
Déjalo en blanco para omitir la ecuación diofántica lineal
Cómo usar Calculadora del algoritmo de Euclides extendido
- Introduce a y b, los dos enteros con los que quieres trabajar. Las comas y los espacios en números largos se ignoran.
- Si quieres, introduce c para resolver la ecuación a·x + b·y = c en números enteros.
- Pulsa Calcular (los resultados también se actualizan mientras escribes) para ver el mcd, x, y y la comprobación a·x + b·y = mcd.
- Sigue la tabla: cada fila muestra el cociente, el resto y los coeficientes acumulados s y t.
- Copia o descarga la respuesta, o la tabla de pasos como archivo CSV para tareas o apuntes.
Cómo funciona el algoritmo de Euclides extendido
El algoritmo de Euclides se basa en un hecho: mcd(a, b) = mcd(b, a mod b). Divides el número mayor entre el menor, te quedas con el resto y repites con el divisor y el resto hasta que el resto sea 0. El último resto distinto de cero es el mcd.
La versión extendida también escribe cada resto como combinación de los números originales, ri = si·a + ti·b. Empieza con dos filas, r0 = a (s = 1, t = 0) y r1 = b (s = 0, t = 1), y luego aplica la misma actualización a las tres columnas:
- qi = ⌊ri−1 ÷ ri⌋
- ri+1 = ri−1 − qi·ri, si+1 = si−1 − qi·si, ti+1 = ti−1 − qi·ti
Cuando el resto llega a 0, la fila de arriba contiene el mcd junto con sus coeficientes x = s e y = t.
Ejemplo resuelto: mcd(240, 46)
| i | División | q | r | s | t |
|---|---|---|---|---|---|
| 0 | inicio | 240 | 1 | 0 | |
| 1 | inicio | 5 | 46 | 0 | 1 |
| 2 | 240 = 5·46 + 10 | 4 | 10 | 1 | −5 |
| 3 | 46 = 4·10 + 6 | 1 | 6 | −4 | 21 |
| 4 | 10 = 1·6 + 4 | 1 | 4 | 5 | −26 |
| 5 | 6 = 1·4 + 2 | 2 | 2 | −9 | 47 |
| 6 | 4 = 2·2 + 0 | 0 | 23 | −120 |
El último resto distinto de cero es 2, así que mcd(240, 46) = 2 con x = −9 e y = 47. Comprobación: 240 × (−9) + 46 × 47 = −2,160 + 2,162 = 2. La última fila (23, −120) es un subproducto útil: 240 × 23 − 46 × 120 = 0, y 23 = 46/2 y 120 = 240/2 son los saltos de la solución general.
Dónde se usa
- Inversos modulares. Si mcd(a, m) = 1, entonces a·x ≡ 1 (mod m). Así se calcula el exponente privado en la generación de claves RSA.
- Ecuaciones diofánticas lineales. a·x + b·y = c tiene soluciones enteras solo cuando mcd(a, b) divide a c; los coeficientes dan una solución directamente.
- Teorema chino del resto. Combinar congruencias como x ≡ 2 (mod 3) y x ≡ 3 (mod 5) requiere inversos de un módulo respecto al otro.
- Fracciones y razones. Dividir entre el mcd reduce una fracción a su mínima expresión.
Consejo: los coeficientes que devuelve este método son los "mínimos", con |x| ≤ b/(2g) y |y| ≤ a/(2g) en la mayoría de los casos, así que rara vez son mayores que las entradas.
Preguntas frecuentes
¿Qué hace el algoritmo de Euclides extendido?
Calcula el máximo común divisor de dos enteros a y b y, al mismo tiempo, dos enteros x e y tales que a·x + b·y = mcd(a, b). El algoritmo de Euclides ordinario solo da el mcd; la versión extendida lleva la cuenta de cómo se construye cada resto a partir de a y b.
¿Qué son los coeficientes de Bézout?
Son los enteros x e y de la identidad de Bézout a·x + b·y = mcd(a, b). Siempre existen cuando a y b no son ambos cero, pero no son únicos: si (x, y) funciona, también lo hace (x + k·b/g, y − k·a/g) para cualquier entero k, donde g es el mcd.
¿Cómo calculo un inverso modular con esta calculadora?
Introduce el número como a y el módulo como b. Si mcd(a, b) = 1, el coeficiente x cumple a·x ≡ 1 (mod b), así que x reducido módulo b es el inverso. Por ejemplo, el inverso de 17 módulo 3120 es 2753, porque 17 × 2753 = 46,801 = 15 × 3120 + 1. Si el mcd es mayor que 1, no existe inverso.
¿Por qué uno de mis coeficientes es negativo?
Para a y b positivos, uno de x e y es casi siempre negativo (o cero), porque a·x + b·y tiene que dar algo tan pequeño como el mcd. Es lo esperado. Sumar b/g a x y restar a/g a y da otro par válido si prefieres una x positiva.
¿Cuándo tiene a·x + b·y = c soluciones enteras?
Exactamente cuando mcd(a, b) divide a c. Entonces multiplicas los coeficientes de Bézout por c / mcd(a, b) para obtener una solución, y la solución general suma múltiplos de b/g a x y resta los mismos múltiplos de a/g a y. Si el mcd no divide a c, no hay soluciones enteras.
¿Cuántos pasos necesita el algoritmo de Euclides?
Muy pocos. Según el teorema de Lamé, el número de divisiones es como máximo unas cinco veces el número de cifras del número menor. El peor caso son dos números de Fibonacci consecutivos, como 89 y 55, donde todos los cocientes son 1.
¿Puedo usar números negativos o enormes?
Sí. La calculadora trabaja con aritmética entera exacta de cualquier longitud hasta 400 cifras. Con entradas negativas ejecuta el algoritmo sobre los valores absolutos y luego cambia el signo del coeficiente correspondiente, de modo que a·x + b·y = mcd se sigue cumpliendo. El mcd siempre se indica como un número no negativo.
¿Se prueban todas las herramientas de FreeToolCabin para comprobar su calidad y precisión?
Sí. Cada herramienta del sitio pasa pruebas automáticas en navegadores reales para comprobar que el resultado es correcto y que no hay errores. Si encuentras un fallo o tienes una sugerencia, escríbenos a [email protected] y lo revisaremos.