El algoritmo de Euclides calcula el máximo común divisor mediante restos sucesivos. Es corto, eficiente y fundamental para simplificar fracciones, analizar ciclos y construir inversos modulares.
Muchas preguntas sobre enteros dependen de sus divisores comunes: ¿se puede simplificar una fracción?, ¿dos longitudes pueden agruparse en bloques iguales?, ¿un número tiene inverso módulo m? Todas conducen al máximo común divisor.
Buscar todos los divisores de dos números puede ser lento. El algoritmo de Euclides evita esa búsqueda: reemplaza repetidamente el número mayor por el resto de una división hasta llegar a cero.
Decimos que un entero d divide a un entero a si existe un entero k tal que a = dk. Se escribe d | a. En ese caso, d es un divisor de a y a es múltiplo de d.
Los divisores pueden ser positivos o negativos, pero para hablar del máximo común divisor usamos por convención el valor no negativo.
El máximo común divisor de dos enteros a y b, escrito mcd(a, b), es el mayor entero positivo que divide a ambos. Cuando a y b no son ambos cero, este valor está bien definido.
En números pequeños se puede listar divisores. El objetivo del algoritmo de Euclides es obtener el mismo resultado sin construir esas listas.
Si a es un entero y b es positivo, la división euclídea produce enteros q y r únicos tales que a = bq + r, con 0 ≤ r < b. El valor r es el resto.
El algoritmo se basa precisamente en este resto. Cada división reemplaza un problema de máximo común divisor por otro con números más pequeños.
Si a = bq + r, los divisores comunes de a y b son exactamente los divisores comunes de b y r. Por ello:
Si un número d divide a y b, también divide a - bq, que es r. A la inversa, si d divide b y r, divide bq + r, que es a. Esta equivalencia justifica cada paso del algoritmo.
Calculemos mcd(252, 105). Aplicamos divisiones sucesivas hasta que el resto sea cero:
Cada línea conserva el mismo máximo común divisor. Cuando el resto llega a cero, el divisor de esa última división divide exactamente al número anterior y es el máximo común divisor buscado.
La siguiente tabla muestra las variables que se actualizan durante el ejemplo. En cada iteración, el divisor pasa a ser el nuevo dividendo y el resto pasa a ser el nuevo divisor.
| Dividendo a | Divisor b | a mod b |
|---|---|---|
| 252 | 105 | 42 |
| 105 | 42 | 21 |
| 42 | 21 | 0 |
Al finalizar, b vale 0 y a vale 21. Esta observación se traduce directamente a una implementación iterativa.
function mcd(a, b) {
a = Math.abs(a);
b = Math.abs(b);
while (b !== 0) {
const resto = a % b;
a = b;
b = resto;
}
return a;
}
console.log(mcd(252, 105)); // 21
console.log(mcd(36, 24)); // 12
console.log(mcd(-18, 30)); // 6El valor absoluto permite que el resultado sea no negativo incluso si los argumentos iniciales son negativos. Para entradas enteras normales, el ciclo termina cuando el segundo valor se vuelve cero.
La identidad mcd(a, b) = mcd(b, a mod b) también se expresa naturalmente mediante recursión. El caso base ocurre cuando b es cero.
function mcdRecursivo(a, b) {
a = Math.abs(a);
b = Math.abs(b);
if (b === 0) return a;
return mcdRecursivo(b, a % b);
}
console.log(mcdRecursivo(252, 105)); // 21La versión iterativa suele ser preferible en producción porque no depende de la profundidad de la pila de llamadas. Ambas representan exactamente el mismo algoritmo matemático.
La convención habitual es mcd(a, 0) = |a|. Por ejemplo, mcd(15, 0) = 15, ya que los divisores de 15 son precisamente los divisores comunes de 15 y 0.
La función anterior devuelve 0 para mcd(0, 0). Si ese caso no tiene sentido en el dominio del programa, conviene validarlo y lanzar un error explícito.
Dos enteros son coprimos o relativamente primos cuando su máximo común divisor es 1. No significa que ambos sean números primos: solo que no comparten factores positivos mayores que 1.
La coprimalidad es una condición central para los inversos modulares. Un número a tiene inverso módulo m exactamente cuando mcd(a, m) = 1.
function sonCoprimos(a, b) {
return mcd(a, b) === 1;
}
console.log(sonCoprimos(14, 25)); // true
console.log(sonCoprimos(14, 21)); // false
function tieneInversoModular(a, m) {
return Number.isInteger(m) && m > 1 && mcd(a, m) === 1;
}
console.log(tieneInversoModular(3, 7)); // true
console.log(tieneInversoModular(2, 8)); // falseEsta comprobación no calcula todavía el inverso; solo determina si puede existir. El algoritmo extendido de Euclides del próximo tema encontrará su valor cuando la respuesta sea afirmativa.
Para reducir una fracción a/b, dividimos numerador y denominador por mcd(a, b). Así eliminamos todos los factores comunes de una sola vez.
La fracción resultante es irreducible porque mcd(2, 3) = 1. Esta misma idea aparece al normalizar proporciones, relaciones de aspecto y resultados racionales de algoritmos.
function simplificarFraccion(numerador, denominador) {
if (!Number.isInteger(numerador) || !Number.isInteger(denominador) || denominador === 0) {
throw new Error("se requieren enteros y un denominador no nulo");
}
const divisor = mcd(numerador, denominador);
const signo = denominador < 0 ? -1 : 1;
return {
numerador: signo * (numerador / divisor),
denominador: signo * (denominador / divisor)
};
}
console.log(simplificarFraccion(84, 126)); // { numerador: 2, denominador: 3 }
console.log(simplificarFraccion(6, -8)); // { numerador: -3, denominador: 4 }La función deja el signo, si existe, en el numerador. Mantener el denominador positivo da una representación canónica y facilita comparar fracciones.
Para enteros positivos a y b, el mínimo común múltiplo, mcm(a, b), se relaciona con el máximo común divisor mediante:
Para reducir el riesgo de desbordamiento se suele dividir antes de multiplicar: (a / mcd(a, b)) * b. El mcm sirve para sincronizar períodos, como eventos que se repiten cada cierto número de pasos.
Si una tarea se ejecuta cada 6 días y otra cada 8 días, ambas vuelven a coincidir cada mcm(6, 8) = 24 días. El mcd permite obtener ese valor de forma eficiente.
function mcm(a, b) {
if (a === 0 || b === 0) return 0;
return Math.abs((a / mcd(a, b)) * b);
}
console.log(mcm(6, 8)); // 24
console.log(mcm(12, 18)); // 36El modelo funciona para ciclos discretos simples. En calendarios reales se deben sumar condiciones como meses, años bisiestos y zonas horarias.
En cada paso, el nuevo divisor es un resto no negativo menor que el divisor anterior. Por lo tanto, la secuencia de divisores positivos disminuye estrictamente.
Así, el algoritmo debe alcanzar el resto cero. Esta es una aplicación directa del principio del buen orden estudiado al comienzo del curso.
El algoritmo de Euclides es muy eficiente: requiere una cantidad de divisiones proporcional al número de dígitos del menor argumento, es decir, O(log min(a, b)) para números positivos.
El caso que demanda más iteraciones aparece con pares consecutivos de la sucesión de Fibonacci. Aun en ese caso, el crecimiento del número de pasos es logarítmico, mucho menor que probar uno por uno todos los posibles divisores.
Si los enteros superan Number.MAX_SAFE_INTEGER, JavaScript puede redondearlos y obtener restos incorrectos. La versión con BigInt mantiene la exactitud.
function mcdBigInt(a, b) {
a = a < 0n ? -a : a;
b = b < 0n ? -b : b;
while (b !== 0n) {
[a, b] = [b, a % b];
}
return a;
}
console.log(mcdBigInt(12345678901234567890n, 9876543210n));Los valores BigInt no se mezclan con Number en operaciones aritméticas. El sufijo n indica que un literal es un entero arbitrario.
Number para enteros demasiado grandes y confiar en restos inexactos.El algoritmo de Euclides transforma un problema de divisores en una sucesión corta de divisiones. En el próximo tema extenderemos el procedimiento para obtener coeficientes que expresan el mcd como combinación lineal y, con ello, calcular inversos modulares.