El algoritmo de Euclides da el MCD y la receta para fabricarlo
Publicado el 27/10/2026 · 3 min de lectura · Calculadoras del día a día
Daniel Okonkwo — Desarrollador front-end y redactor de Tecnología en OneKitly
Rendimiento web · Formatos de archivo
Verificado con 2 fuentes
El algoritmo ordinario sustituye una y otra vez el número mayor por su resto contra el menor: 252 deja 42 contra 105, 105 deja 21 contra 42, y 42 no deja nada contra 21, así que 21 es el máximo común divisor. La versión extendida guarda constancia de cómo se construyó cada resto por el camino y devuelve dos enteros que combinan los números originales en ese divisor — aquí −2 y 5, puesto que 252 × (−2) + 105 × 5 = −504 + 525 = 21. Esa combinación existe siempre, hecho llamado identidad de Bézout, y es la que produce un inverso modular: cuando el divisor es uno, el coeficiente del primer número es exactamente el inverso de ese número módulo el segundo.
252 y 105 tienen un máximo común divisor de 21, y la versión extendida devuelve además −2 y 5: 252 × (−2) + 105 × 5 = 21 exactamente.
Por qué termina tan rápido
Cada paso sustituye un par por un par menor, y el encogimiento es rápido: tras dos pasos el número mayor vale como mucho la mitad de lo que era, porque un resto siempre es menor que el divisor y uno de los dos tiene que quedar por debajo de la mitad. El número de pasos es por tanto proporcional al número de cifras y no a los números en sí, de ahí la facilidad con que el método trata valores de cientos de cifras. El peor caso resulta ser el de los números de Fibonacci consecutivos, detalle grato y razón por la que la cota se enuncia normalmente en logaritmo.
Los coeficientes no son únicos
Para 240 y 46 el algoritmo devuelve −9 y 47, dando 240 × (−9) + 46 × 47 = 2, y esa es una respuesta entre infinitas: sumar veintitrés al primer coeficiente y restar ciento veinte al segundo da otro par válido, y así sin fin. El algoritmo devuelve el par de menores magnitudes, representante útil, y toda implementación que compare dos resultados debe normalizar antes de concluir que difieren. Es un riesgo general de los problemas cuyas respuestas forman una familia y no un punto.
| Paso | Resto |
|---|---|
| 252 = 2 × 105 + 42 | 42 |
| 105 = 2 × 42 + 21 | 21 |
| 42 = 2 × 21 + 0 | 0 — fin |
Preguntas frecuentes
- ¿Qué antigüedad tiene este método?
- Aparece en los Elementos de Euclides, escritos unos trescientos años antes de nuestra era, lo que lo convierte en el algoritmo más antiguo aún de uso corriente. Nada en él se ha mejorado en el sentido que importa: existen variantes que evitan la división o encajan mejor en hardware binario, pero el número de pasos y la idea subyacente no han cambiado. Que un procedimiento escrito para geometría sobre papiro esté dentro de todo aparato que hace criptografía de clave pública es una de las continuidades más llamativas del campo.
- ¿Para qué sirven los coeficientes además de los inversos?
- Para resolver ecuaciones en números enteros, que es para lo que se quisieron primero. Una ecuación que pide cantidades enteras de dos magnitudes que deben totalizar una tercera tiene solución exactamente cuando el máximo común divisor de las dos divide a la tercera, y los coeficientes dan una directamente; las demás siguen sumando múltiplos de un paso fijo. Eso cubre componer un importe con dos valores de moneda, sincronizar dos ciclos repetitivos, y cualquier pregunta análoga donde no se permitan respuestas fraccionarias. Es también la maquinaria tras reconstruir un valor a partir de varios restos a la vez.
Artículos que podrían interesarte
Todas las guías →Herramientas relacionadas
Fuentes
¿Has detectado un error en este artículo?