Lección 1.4: El mínimo común múltiplo — Espinoza Olimpiadas

¿Qué es el MCM y por qué importa?

El mínimo común múltiplo (MCM) de dos enteros positivos $a$ y $b$ es el menor entero positivo que es múltiplo tanto de $a$ como de $b$ . Lo denotamos $\text{mcm}(a,b)$ o $[a,b]$ . Por ejemplo, $\text{mcm}(4,6) = 12$ porque $12$ es el menor positivo divisible por $4$ y por $6$ .

El MCM aparece naturalmente cuando queremos sincronizar ciclos: si un evento ocurre cada $a$ días y otro cada $b$ días, ambos coinciden por primera vez en el día $\text{mcm}(a,b)$ . En olimpiadas, el MCM suele aparecer en problemas de "¿cuándo vuelven a coincidir?", en demostraciones de existencia de múltiplos con propiedades especiales, y en el estudio de fracciones.

La herramienta más limpia para calcular el MCM es el Teorema Fundamental de la Aritmética (TFA): todo entero mayor que $1$ se escribe de forma única como producto de primos. Con la descomposición en mano, el MCD y el MCM se leen directamente.

Definición vía el TFA

Sean $a = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_r^{\alpha_r}$ y $b = p_1^{\beta_1} p_2^{\beta_2} \cdots p_r^{\beta_r}$ las descomposiciones primas de $a$ y $b$ (algunos exponentes pueden ser cero). Entonces: $\gcd(a,b) = p_1^{\min(\alpha_1,\beta_1)} \cdots p_r^{\min(\alpha_r,\beta_r)}$ y $\text{mcm}(a,b) = p_1^{\max(\alpha_1,\beta_1)} \cdots p_r^{\max(\alpha_r,\beta_r)}$ .

Ejemplo: $a = 360 = 2^3 \cdot 3^2 \cdot 5$ y $b = 2100 = 2^2 \cdot 3 \cdot 5^2 \cdot 7$ . Entonces $\gcd(360, 2100) = 2^{\min(3,2)} \cdot 3^{\min(2,1)} \cdot 5^{\min(1,2)} \cdot 7^{\min(0,1)} = 2^2 \cdot 3 \cdot 5 = 60$ y $\text{mcm}(360, 2100) = 2^3 \cdot 3^2 \cdot 5^2 \cdot 7 = 8\cdot9\cdot25\cdot7 = 12600$ .

La fórmula del TFA muestra además una simetría hermosa: para cada primo $p$ , el exponente en el MCD es el mínimo de los dos exponentes, y en el MCM es el máximo. Esta simetría min/max es la clave de la identidad $\text{mcm} \cdot \gcd = ab$ que demostramos a continuación.

\text{mcm}(a,b) = \prod_p p^{\max(v_p(a),\, v_p(b))}

La identidad fundamental: mcm × MCD = ab

Teorema: para todo par de enteros positivos $a, b$ : $\text{mcm}(a,b) \cdot \gcd(a,b) = a \cdot b$ .

Demostración: para cada primo $p$ , sea $\alpha = v_p(a)$ y $\beta = v_p(b)$ los exponentes de $p$ en $a$ y $b$ respectivamente. La contribución de $p$ al lado izquierdo es $p^{\max(\alpha,\beta)} \cdot p^{\min(\alpha,\beta)} = p^{\max(\alpha,\beta)+\min(\alpha,\beta)}$ . Ahora usamos la identidad $\max(\alpha,\beta) + \min(\alpha,\beta) = \alpha + \beta$ (siempre cierta para reales). Así la contribución de $p$ es $p^{\alpha+\beta}$ , que es exactamente la contribución de $p$ a $a \cdot b$ . Como esto vale para todo primo $p$ , tenemos $\text{mcm}(a,b) \cdot \gcd(a,b) = ab$ .

Consecuencia práctica: si conocemos el MCD, calculamos el MCM como $\text{mcm}(a,b) = ab / \gcd(a,b)$ , sin necesidad de factorizar. Ejemplo: $\text{mcm}(252, 105) = 252 \cdot 105 / 21 = 26460/21 = 1260$ .

\text{mcm}(a,b) \cdot \gcd(a,b) = a \cdot b

Propiedades del MCM

Propiedades básicas: (1) $\text{mcm}(a,b) = \text{mcm}(b,a)$ (simetría). (2) $\text{mcm}(a,a) = a$ . (3) $a \mid b \iff \text{mcm}(a,b) = b$ (y equivalentemente $\gcd(a,b)=a$ ). (4) $\text{mcm}(a,b,c) = \text{mcm}(\text{mcm}(a,b), c)$ (asociatividad, permite extender a tres o más números). (5) $\text{mcm}(ca, cb) = c \cdot \text{mcm}(a,b)$ para $c > 0$ (homogeneidad).

Cotas: siempre se tiene $\max(a,b) \le \text{mcm}(a,b) \le ab$ . El mínimo $\max(a,b)$ se alcanza cuando uno divide al otro; el máximo $ab$ se alcanza cuando $\gcd(a,b)=1$ .

MCM y divisibilidad: $c \mid \text{mcm}(a,b)$ para todo $c$ que sea múltiplo común de $a$ y $b$ . Esto es precisamente la propiedad de mínimo: $\text{mcm}(a,b)$ es el generador del conjunto $\{n \in \mathbb{Z}^+ : a\mid n \text{ y } b\mid n\}$ como divisibilidad se refiere. En el capítulo de congruencias, este hecho se reformula diciendo que $\text{mcm}(a,b)$ es el "orden" de la intersección de los grupos $a\mathbb{Z}$ y $b\mathbb{Z}$ .

Problemas con MCM y MCD simultáneos

Tipo clásico 1: Dados $\gcd(a,b) = d$ y $\text{mcm}(a,b) = m$ , ¿cuántos pares $(a,b)$ existen? Como $d\mid a$ y $d\mid b$ , escribimos $a = d\alpha$ , $b = d\beta$ con $\gcd(\alpha,\beta)=1$ (la lección 1.1 garantiza esto). Además $\text{mcm}(a,b) = d\alpha\beta = m$ , así $\alpha\beta = m/d$ . Los pares son los divisores $\alpha$ de $m/d$ con $\gcd(\alpha, m/(d\alpha))=1$ .

Tipo clásico 2: Halla todos los pares $(a,b)$ con $a \le b$ , $\gcd(a,b)=6$ , $\text{mcm}(a,b)=180$ . Verificamos: $6\cdot180=1080=ab$ y $6\mid 180$ ✓. Escribimos $a=6\alpha$ , $b=6\beta$ , $\gcd(\alpha,\beta)=1$ , $\alpha\beta=30$ . Los pares $\{\alpha,\beta\}$ con $\alpha\le\beta$ , $\gcd(\alpha,\beta)=1$ y $\alpha\beta=30$ : son $\{1,30\},\{2,15\},\{3,10\},\{5,6\}$ . Verificamos coprimalidad: $\gcd(1,30)=1$ ✓, $\gcd(2,15)=1$ ✓, $\gcd(3,10)=1$ ✓, $\gcd(5,6)=1$ ✓. Así hay 4 pares: $(6,180),(12,90),(18,60),(30,36)$ .

Tipo clásico 3 (ONEM): Demuestra que $\text{mcm}(a,b,c) \cdot \gcd(a,b) \cdot \gcd(b,c) \cdot \gcd(a,c) \ge abc$ . Este tipo de desigualdad entre MCM y MCD se demuestra prima a prima: fijado un primo $p$ , sea $\alpha \le \beta \le \gamma$ los exponentes ordenados. El lado izquierdo aporta $\gamma + \alpha + \beta + \alpha = \gamma + \beta + 2\alpha$ y el lado derecho aporta $\alpha + \beta + \gamma$ . Como $2\alpha \ge \alpha$ , la desigualdad se cumple.

Cierre del Capítulo 1

Hemos completado el capítulo de divisibilidad y MCD. Las cuatro lecciones cubren las herramientas centrales: el algoritmo de Euclides calcula el MCD eficientemente; la identidad de Bézout da los coeficientes explícitos y abre la puerta a ecuaciones diofánticas; los criterios de divisibilidad permiten leer propiedades de un número desde sus cifras; y el MCM cierra el cuadro con la relación $\text{mcm} \cdot \gcd = ab$ .

Estos cuatro temas reaparecen constantemente a lo largo del módulo. En el capítulo 2 el TFA funda los cálculos de MCD y MCM sobre la factorización prima. En el capítulo 3 las congruencias generalizan los criterios de divisibilidad. En el capítulo 6 las ecuaciones diofánticas lineales retoman la identidad de Bézout con mayor profundidad.

El consejo práctico para competencias: cuando veas $\gcd$ o $\text{mcm}$ en un problema, escribe inmediatamente $a = d\alpha$ , $b = d\beta$ con $d = \gcd(a,b)$ y $\gcd(\alpha,\beta)=1$ . Esta substitución estándar transforma la mayoría de los problemas de MCD/MCM en problemas sobre números coprimos, que son mucho más manejables.

El mínimo común múltiplo