¿Qué es el algoritmo de Euclides?
El algoritmo de Euclides es uno de los métodos matemáticos más antiguos que se conocen, descrito por el matemático griego Euclides hacia el año 300 a. C. Sirve para hallar el máximo común divisor (MCD) de dos números enteros, es decir, el mayor número que divide a ambos sin dejar resto. Esta calculadora aplica el algoritmo a cualquier par de enteros no negativos y, además, te devuelve su mínimo común múltiplo (mcm).
Cómo usarla
Escribe tus dos números en los campos a y b y pulsa calcular. La herramienta muestra el MCD como resultado principal y el mcm como valor secundario. El orden no importa: \(\operatorname{mcd}(48, 36)\) es igual que \(\operatorname{mcd}(36, 48)\). Los valores negativos se tratan por su valor absoluto y, si uno de los números es 0, el MCD es simplemente el otro número.
La fórmula al detalle
El algoritmo se apoya en una idea muy sencilla: todo divisor común de a y b también divide a su resto a mod b. Por eso vamos sustituyendo repetidamente el número mayor por el resto:
$$\operatorname{mcd}(a, b) = \operatorname{mcd}(b,\, a \bmod b), \quad \operatorname{mcd}(a, 0) = a$$
En cada paso los números se reducen muy rápido, así que incluso valores enormes se resuelven en unas pocas iteraciones. El mcm se obtiene entonces como $$\operatorname{mcm}(a, b) = \frac{a \times b}{\operatorname{mcd}(a, b)}.$$
Ejemplo resuelto
Calculemos \(\operatorname{mcd}(48, 36)\):
$$48 \bmod 36 = 12 \rightarrow \operatorname{mcd}(36, 12)$$
$$36 \bmod 12 = 0 \rightarrow \operatorname{mcd}(12, 0) = 12.$$
Por tanto, el MCD es 12 y el $$\operatorname{mcm} = \frac{48 \times 36}{12} = \frac{1728}{12} = 144.$$
Preguntas frecuentes
¿Y si los dos números son 0? Aquí el MCD de 0 y 0 se define como 0, y el mcm también es 0, ya que no existe ningún múltiplo positivo.
¿Por qué es más rápido que listar los divisores? En lugar de buscar todos los divisores, el algoritmo usa el atajo del resto, lo que reduce drásticamente el tamaño del problema en cada paso, normalmente en tiempo logarítmico.
¿Funciona con números muy grandes? Sí. El algoritmo de Euclides es eficiente incluso con números de muchas cifras, ya que solo necesita un número reducido de operaciones de módulo.
