El MCD permite encontrar el mayor divisor compartido y el MCM el menor múltiplo común. Son herramientas útiles para simplificar fracciones, sincronizar ciclos y resolver problemas de divisibilidad.
El máximo común divisor y el mínimo común múltiplo se apoyan en los conceptos de divisibilidad, múltiplos, divisores y factorización vistos en temas anteriores.
En programación aparecen en problemas donde hay que simplificar proporciones, reducir fracciones, coordinar eventos periódicos, repartir cantidades en grupos iguales o buscar patrones que se repiten.
En este tema veremos primero la idea matemática y luego la convertiremos en funciones JavaScript.
El máximo común divisor, abreviado MCD, es el mayor número que divide exactamente a dos o más números.
El número 6 es el mayor divisor que comparten 12 y 18.
const a = 12;
const b = 18;
console.log(a % 6);
console.log(b % 6);Una forma directa de calcular el MCD es buscar todos los divisores comunes y quedarse con el mayor.
function mcdPorBusqueda(a, b) {
let resultado = 1;
const limite = Math.min(a, b);
for (let divisor = 1; divisor <= limite; divisor++) {
if (a % divisor === 0 && b % divisor === 0) {
resultado = divisor;
}
}
return resultado;
}
console.log(mcdPorBusqueda(12, 18));
console.log(mcdPorBusqueda(20, 30));Este algoritmo es fácil de entender, aunque puede ser lento si los números son grandes.
El algoritmo de Euclides calcula el MCD usando restos. La idea es que el MCD de dos números no cambia si reemplazamos el mayor por el resto de dividirlo por el menor.
function mcd(a, b) {
while (b !== 0) {
const resto = a % b;
a = b;
b = resto;
}
return a;
}
console.log(mcd(48, 18));
console.log(mcd(12, 18));Este algoritmo es eficiente y se usa con mucha frecuencia en programación.
El MCD se considera positivo. Si recibimos valores negativos, podemos trabajar con sus valores absolutos usando Math.abs().
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(-48, 18));
console.log(mcd(48, -18));Esta pequeña validación hace que la función sea más robusta.
Una aplicación muy importante del MCD es simplificar fracciones. Para reducir una fracción, dividimos numerador y denominador por su MCD.
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;
}
const numerador = 18;
const denominador = 24;
const divisorComun = mcd(numerador, denominador);
console.log(numerador / divisorComun);
console.log(denominador / divisorComun);El mínimo común múltiplo, abreviado MCM, es el menor número positivo que es múltiplo de dos o más números.
El 12 es el menor múltiplo positivo que comparten 4 y 6.
console.log(12 % 4);
console.log(12 % 6);Una forma directa de calcular el MCM es empezar desde el mayor de los dos números y avanzar hasta encontrar un valor divisible por ambos.
function mcmPorBusqueda(a, b) {
let candidato = Math.max(a, b);
while (true) {
if (candidato % a === 0 && candidato % b === 0) {
return candidato;
}
candidato++;
}
}
console.log(mcmPorBusqueda(4, 6));
console.log(mcmPorBusqueda(8, 12));Este método es claro, pero puede tardar mucho con números grandes.
Para dos números positivos, existe una relación muy útil:
Esta fórmula permite calcular el MCM de forma eficiente si ya tenemos una función para el MCD.
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;
}
function mcm(a, b) {
return Math.abs(a * b) / mcd(a, b);
}
console.log(mcm(4, 6));
console.log(mcm(8, 12));
console.log(mcm(15, 20));También podemos calcular MCD y MCM usando factorización prima. El MCD toma los factores comunes con menor exponente. El MCM toma todos los factores con mayor exponente.
Este enfoque es muy útil para entender la relación matemática, aunque el algoritmo de Euclides suele ser más práctico para programar el MCD.
El MCM aparece cuando dos eventos se repiten con diferentes intervalos y queremos saber cuándo coinciden nuevamente.
Si una tarea ocurre cada 4 segundos y otra cada 6 segundos, ambas coinciden cada 12 segundos.
function mcd(a, b) {
while (b !== 0) {
const resto = a % b;
a = b;
b = resto;
}
return a;
}
function mcm(a, b) {
return Math.abs(a * b) / mcd(a, b);
}
const tareaA = 4;
const tareaB = 6;
console.log(mcm(tareaA, tareaB));El MCD ayuda a repartir cantidades en grupos iguales del mayor tamaño posible. Por ejemplo, si tenemos 24 lápices y 36 hojas, podemos armar paquetes idénticos usando el MCD.
function mcd(a, b) {
while (b !== 0) {
const resto = a % b;
a = b;
b = resto;
}
return a;
}
const lapices = 24;
const hojas = 36;
const paquetes = mcd(lapices, hojas);
console.log(paquetes);
console.log(lapices / paquetes);
console.log(hojas / paquetes);El primer resultado indica cuántos paquetes iguales se pueden formar. Los siguientes indican cuántos lápices y hojas tendrá cada paquete.
Podemos extender las funciones para trabajar con listas de números usando reduce(). La idea es aplicar la operación de a pares.
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;
}
function mcm(a, b) {
return Math.abs(a * b) / mcd(a, b);
}
const numeros = [12, 18, 30];
console.log(numeros.reduce((acumulado, numero) => mcd(acumulado, numero)));
console.log(numeros.reduce((acumulado, numero) => mcm(acumulado, numero)));Este patrón es útil cuando una entrada contiene varias cantidades y necesitamos una respuesta común para todas.
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(0, 8));
console.log(mcd(8, 0));
console.log(mcd(0, 0));El caso MCD(0, 0) requiere una decisión según el contexto del programa. Matemáticamente suele considerarse indefinido.
El máximo común divisor y el mínimo común múltiplo convierten ideas de divisibilidad en herramientas prácticas. Permiten simplificar, sincronizar, repartir y razonar sobre patrones repetitivos.
En el próximo tema estudiaremos fracciones y operaciones con fracciones, donde el MCD y el MCM volverán a ser especialmente útiles.