Calculadora de MCD y MCM
Introduce dos números enteros positivos para hallar su máximo común divisor (MCD) mediante el algoritmo de Euclides, mostrando cada paso del cálculo. El mínimo común múltiplo (MCM) se calcula al mismo tiempo.
| Máximo común divisor (MCD) | |
|---|---|
| Mínimo común múltiplo (MCM) |
Pasos del algoritmo de Euclides
| Fórmula |
|---|
| = × + |
¿Qué es el algoritmo de Euclides?
El algoritmo de Euclides es un método clásico para hallar el máximo común divisor de dos enteros. El procedimiento: se toma el resto de dividir el número mayor entre el menor, y se repite la misma operación con el divisor y ese resto. Cuando el resto llega a 0, el divisor en ese punto es el máximo común divisor. Esto permite hallar el MCD incluso de números muy grandes con relativamente pocos pasos. Aparece registrado en los "Elementos" de Euclides, de alrededor del 300 a. C., lo que lo convierte en uno de los algoritmos más antiguos que aún se usan hoy.
Consejos
- El mínimo común múltiplo (MCM) se puede hallar con la fórmula "A × B ÷ MCD". Se usa habitualmente para encontrar un denominador común entre fracciones, o para averiguar cuándo coincidirán varios eventos con periodos distintos.
- Si dos números son coprimos (su MCD es 1), su MCM es simplemente A × B.
- Una ventaja práctica del algoritmo de Euclides es que puede calcular el MCD de números grandes más rápido que pasando por la factorización en números primos.
- El orden en que introduzcas los dos números no afecta al resultado: el cálculo comienza automáticamente por el mayor de los dos.
Preguntas frecuentes
A propósito — por qué un algoritmo de 2000 años sigue en uso diario
El algoritmo de Euclides aparece en el Libro VII de los "Elementos" de Euclides, escritos por el matemático griego alrededor del 300 a. C. Se le considera uno de los algoritmos más antiguos de los que se tiene constancia, y más de dos mil años después sigue siendo uno de los primeros algoritmos que se presentan en los libros de texto de ciencias de la computación.
El motivo de que haya perdurado tanto tiempo radica en su eficiencia computacional. Matemáticamente, se ha demostrado que el número de pasos que requiere el algoritmo de Euclides es aproximadamente proporcional a la cantidad de dígitos de la entrada (el peor caso ocurre con pares de números relacionados con la sucesión de Fibonacci), lo que significa que puede hallar el MCD incluso de enteros enormes en un tiempo práctico.
La criptografía moderna —el cifrado RSA, por ejemplo— sigue utilizando el cálculo del MCD (o su forma extendida, el algoritmo de Euclides extendido) durante la generación de claves. Es una muestra llamativa de la universalidad de las matemáticas que un descubrimiento antiguo sustente parte de la tecnología que hoy protege internet.