Máximo común divisor y mínimo común múltiplo

El máximo común divisor y el mínimo común múltiplo

En la clase sobre divisibilidad y división con resto se estudió la relación $d \mid a$ entre dos naturales. Cuando se consideran dos números a la vez, interesan los divisores que tienen en común y los múltiplos que comparten. Todo par de naturales $a$ y $b$ tiene al menos un divisor común, el $1$, y a lo sumo un número finito de ellos, porque ningún divisor de $a$ supera a $a$; tiene, además, infinitos múltiplos comunes, entre ellos el producto $ab$. Si esto es así, tiene sentido la siguiente definición.

Definición (máximo común divisor y mínimo común múltiplo). El máximo común divisor de dos naturales $a$ y $b$, que se escribe $\operatorname{mcd}(a, b)$, es el mayor natural que divide a ambos. El mínimo común múltiplo, que se escribe $\operatorname{mcm}(a, b)$, es el menor natural que es múltiplo de ambos.

El segundo es el menor elemento de un conjunto no vacío de naturales, que existe por el principio del buen orden. El primero es el mayor elemento del conjunto de los divisores comunes, que no es vacío y está acotado por $a$; que un conjunto no vacío de naturales acotado superiormente tiene máximo se sigue también del buen orden: el conjunto de sus cotas superiores no es vacío y tiene un mínimo $M$, y $M$ pertenece al conjunto, porque si no, todo elemento sería menor que $M$ y, como no hay naturales entre $M - 1$ y $M$, no mayor que $M - 1$, que sería una cota superior menor que $M$ (si $M = 1$, el conjunto es $\{1\}$ y contiene a $M$). Por ejemplo, los divisores comunes de $12$ y $18$ son $1$, $2$, $3$ y $6$, y sus múltiplos comunes son $36$, $72$, $108$, y así sucesivamente:

De la definición se siguen de inmediato algunos casos particulares: $\operatorname{mcd}(a, 1) = 1$ y $\operatorname{mcm}(a, 1) = a$; $\operatorname{mcd}(a, a) = \operatorname{mcm}(a, a) = a$; y, si $a$ divide a $b$, entonces $\operatorname{mcd}(a, b) = a$ y $\operatorname{mcm}(a, b) = b$. Ambas operaciones son, además, simétricas: el orden de los números no altera el resultado.

Cálculo mediante la descomposición en factores primos

Por el teorema fundamental de la aritmética, todo natural mayor que $1$ se descompone de manera única en factores primos. Conviene escribir $a$ y $b$ con los mismos primos $p_1, \ldots, p_k$, admitiendo exponentes nulos para los primos que solo aparecen en uno de ellos:

Un natural $d$ divide a $a$ exactamente cuando en su descomposición no aparecen otros primos que los de $a$, y cada uno con exponente no mayor que el que tiene en $a$. De ello se sigue que $d$ divide a la vez a $a$ y a $b$ cuando el exponente de cada primo en $d$ no supera a ninguno de los dos exponentes; el mayor divisor común se obtiene, por tanto, tomando para cada primo el menor de los dos exponentes. Del mismo modo, $m$ es múltiplo común cuando el exponente de cada primo en $m$ alcanza a los dos, y el menor múltiplo común toma para cada primo el mayor de los dos exponentes. Por ejemplo:

El método es claro, pero depende de saber factorizar, y factorizar números grandes es muy costoso: no se conoce ningún procedimiento rápido para hacerlo. El algoritmo de la sección siguiente calcula el máximo común divisor sin factorizar, solo con divisiones.