Mínimo común múltiplo

El mínimo común múltiplo de dos enteros a y b se denota como mcm( a , b ). ^{[ 1 ]} Algunos libros de texto antiguos usan [ a , b ]. ^{[ 3 ] [ 4 ]}

${\displaystyle \operatorname {lcm} (4,6)}$

Los múltiplos de 4 son:

${\displaystyle 4,8,12,16,20,24,28,32,36,40,44,48,52,56,60,64,68,72,76,...}$

Los múltiplos de 6 son:

${\displaystyle 6,12,18,24,30,36,42,48,54,60,66,72,...}$

Los múltiplos comunes de 4 y 6 son los números que aparecen en ambas listas:

${\displaystyle 12,24,36,48,60,72,...}$

En esta lista, el número más pequeño es 12. Por lo tanto, el mínimo común múltiplo es  12.

Supongamos que hay dos engranajes que engranan en una máquina , con m y n dientes respectivamente, y que los engranajes están marcados por un segmento de línea trazado desde el centro del primer engranaje hasta el centro del segundo. Cuando los engranajes comienzan a girar, el número de rotaciones que el primer engranaje debe completar para realinear el segmento de línea se puede calcular utilizando${\displaystyle \operatorname {lcm} (m,n)}$. El primer engranaje debe completarse${\textstyle {\frac {\operatorname {lcm} (m,n)}{m}}}$rotaciones para la realineación. Para entonces, el segundo engranaje habrá hecho${\textstyle {\frac {\operatorname {lcm} (m,n)}{n}}}$rotaciones.

Supongamos que hay tres planetas girando alrededor de una estrella que tardan l , m y n unidades de tiempo, respectivamente, en completar sus órbitas. Supongamos que l , m y n son números enteros. Suponiendo que los planetas comenzaron a moverse alrededor de la estrella después de una alineación lineal inicial, todos los planetas alcanzan una alineación lineal nuevamente después de${\displaystyle \operatorname {lcm} (l,m,n)}$unidades de tiempo. En este momento, el primer, segundo y tercer planeta habrán completado${\textstyle {\frac {\operatorname {lcm} (l,m,n)}{l}}}$,${\textstyle {\frac {\operatorname {lcm} (l,m,n)}{m}}}$y${\textstyle {\frac {\operatorname {lcm} (l,m,n)}{n}}}$órbitas, respectivamente, alrededor de la estrella. ^{[ 5 ]}

El mínimo común múltiplo se puede calcular a partir del máximo común divisor (mcd) con la fórmula

${\displaystyle \operatorname {lcm} (a,b)={\frac {|ab|}{\gcd(a,b)}}.}$

Para evitar introducir números enteros mayores que el resultado, es conveniente utilizar fórmulas equivalentes.

${\displaystyle \operatorname {lcm} (a,b)=|a|\,{\frac {|b|}{\gcd(a,b)}}=|b|\,{\frac {|a|}{\gcd(a,b)}},}$

donde el resultado de la división es siempre un número entero.

Estas fórmulas también son válidas cuando exactamente uno de a y b es 0 , ya que mcd( a , 0) = | a | . Sin embargo, si ambos ay b son 0 , estas fórmulas causarían una división por cero ; por lo tanto, mcm(0, 0) = 0 debe considerarse como un caso especial.

Volviendo al ejemplo anterior,

${\displaystyle \operatorname {lcm} (21,6)=6\times {\frac {21}{\gcd(21,6)}}=6\times {\frac {21}{3}}=6\times 7=42.}$

Existen algoritmos rápidos , como el algoritmo euclidiano para calcular el máximo común divisor (MCD), que no requieren factorizar los números . Para enteros muy grandes, existen algoritmos aún más rápidos para las tres operaciones involucradas (multiplicación, MCD y división); véase Multiplicación rápida . Dado que estos algoritmos son más eficientes con factores de tamaño similar, resulta más eficiente dividir el mayor argumento del mínimo común múltiplo (mcm) entre el MCD de los argumentos, como en el ejemplo anterior.

El teorema de factorización única indica que todo entero positivo mayor que 1 puede escribirse de una sola manera como producto de números primos . Los números primos pueden considerarse como los elementos atómicos que, al combinarse, forman un número compuesto .

Por ejemplo:

${\displaystyle 90=2^{1}\cdot 3^{2}\cdot 5^{1}=2\cdot 3\cdot 3\cdot 5.}$

En este caso, el número compuesto 90 está formado por un átomo del número primo 2, dos átomos del número primo 3 y un átomo del número primo 5.

Este hecho puede utilizarse para hallar el mínimo común múltiplo (mcm) de un conjunto de números.

Ejemplo: mcm(8,9,21)

Factoriza cada número y exprésalo como un producto de potencias de números primos .

${\displaystyle {\begin{aligned}8&=2^{3}\\9&=3^{2}\\21&=3^{1}\cdot 7^{1}\end{aligned}}}$

El mcm será el producto de multiplicar la mayor potencia de cada número primo entre sí. La mayor potencia de los tres números primos 2, 3 y 7 es 2³ ^, 3² ^y 7¹ ^, respectivamente. Por lo tanto,

${\displaystyle \operatorname {lcm} (8,9,21)=2^{3}\cdot 3^{2}\cdot 7^{1}=8\cdot 9\cdot 7=504.}$

Este método no es tan eficiente como la reducción al máximo común divisor, ya que no se conoce ningún algoritmo general eficiente para la factorización de enteros .

El mismo método también se puede ilustrar con un diagrama de Venn , donde la factorización prima de cada uno de los dos números se muestra en cada círculo y todos los factores comunes se ubican en la intersección. El mínimo común múltiplo (mcm) se obtiene multiplicando todos los números primos del diagrama.

Aquí tienes un ejemplo:

48 = 2 × 2 × 2 × 2 × 3,

180 = 2 × 2 × 3 × 3 × 5,

que comparten dos "2" y un "3":

Mínimo común múltiplo = 2 × 2 × 2 × 2 × 3 × 3 × 5 = 720

Máximo común divisor = 2 × 2 × 3 = 12

Producto = 2 × 2 × 2 × 2 × 3 × 2 × 2 × 3 × 3 × 5 = 8640

Esto también funciona para el máximo común divisor (mcd), con la diferencia de que, en lugar de multiplicar todos los números del diagrama de Venn, se multiplican solo los factores primos que se encuentran en la intersección. Por lo tanto, el mcd de 48 y 180 es 2  ×  2  ×  3  =  12.

Según el teorema fundamental de la aritmética , todo número entero mayor que 1 puede representarse de forma única como un producto de números primos, hasta el orden de los factores:

${\displaystyle n=2^{n_{2}}3^{n_{3}}5^{n_{5}}7^{n_{7}}\cdots =\prod _{p}p^{n_{p}},}$

donde los exponentes n ₂ , n ₃ , ... son enteros no negativos; por ejemplo, 84 = 2 ² 3 ¹ 5 ⁰ 7 ¹ 11 ⁰ 13 ⁰ ...

Dados dos números enteros positivos${\textstyle a=\prod _{p}p^{a_{p}}}$y${\textstyle b=\prod _ {p}p^{b_ {p}}}$, su máximo común divisor y mínimo común múltiplo vienen dados por las fórmulas

${\displaystyle \gcd(a,b)=\prod _{p}p^{\min(a_{p},b_{p})}}$

y

${\displaystyle \operatorname {lcm} (a,b)=\prod _{p}p^{\max(a_{p},b_{p})}.}$

Desde

${\displaystyle \min(x,y)+\max(x,y)=x+y,}$

esto da

${\displaystyle \gcd(a,b)\operatorname {lcm} (a,b)=ab.}$

De hecho, todo número racional puede escribirse de forma única como producto de números primos, si se permiten exponentes negativos. Cuando se hace esto, las fórmulas anteriores siguen siendo válidas. Por ejemplo:

${\displaystyle {\begin{aligned}4&=2^{2}3^{0},&6&=2^{1}3^{1},&\gcd(4,6)&=2^{1}3^{0}=2,&\operatorname {lcm} (4,6)&=2^{2}3^{1}=12.\\[8pt]{\tfrac {1}{3}}&=2^{0}3^{-1}5^{0},&{\tfrac {2}{5}}&=2^{1}3^{0}5^{-1},&\gcd \left({\tfrac {1}{3}},{\tfrac {2}{5}}\right)&=2^{0}3^{-1}5^{-1}={\tfrac {1}{15}},&\operatorname {lcm} \left({\tfrac {1}{3}},{\tfrac {2}{5}}\right)&=2^{1}3^{0}5^{0}=2,\\[8pt]{\tfrac {1}{6}}&=2^{-1}3^{-1},&{\tfrac {3}{4}}&=2^{-2}3^{1},&\gcd \left({\tfrac {1}{6}},{\tfrac {3}{4}}\right)&=2^{-2}3^{-1}={\tfrac {1}{12}},&\operatorname {lcm} \left({\tfrac {1}{6}},{\tfrac {3}{4}}\right)&=2^{-1}3^{1}={\tfrac {3}{2}}.\end{aligned}}}$

Los enteros positivos pueden ordenarse parcialmente según su divisibilidad: si a divide a b (es decir, si b es un múltiplo entero de a ), se escribe a ≤ b (o, equivalentemente, b ≥ a ). (Nótese que aquí no se utiliza la definición habitual de ≤ basada en la magnitud).

Bajo este ordenamiento, los enteros positivos forman un retículo , donde la intersección viene dada por el mcd y la unión por el mcm. La demostración es sencilla, aunque un tanto tediosa; consiste en comprobar que el mcm y el mcd satisfacen los axiomas de intersección y unión. Al situar el mcm y el mcd en este contexto más general, se establece una dualidad entre ellos:

Si una fórmula que involucra variables enteras, mcd, mcm, ≤ y ≥ es verdadera, entonces la fórmula obtenida al intercambiar mcd con mcm e intercambiar ≥ con ≤ también es verdadera. (Recuerde que ≤ se define como división).

Los siguientes pares de fórmulas duales son casos especiales de identidades generales de la teoría de retículos.

También se puede demostrar ^{[ 6 ]} que este retículo es distributivo ; es decir, mcm se distribuye sobre mcd y mcd se distribuye sobre mcm:

${\displaystyle \operatorname {lcm} (a,\gcd(b,c))=\gcd(\operatorname {lcm} (a,b),\operatorname {lcm} (a,c)),}$

${\displaystyle \gcd(a,\operatorname {lcm} (b,c))=\operatorname {lcm} (\gcd(a,b),\gcd(a,c)).}$

Esta identidad es autodual:

${\displaystyle \gcd(\operatorname {lcm} (a,b),\operatorname {lcm} (b,c),\operatorname {lcm} (a,c))=\operatorname {lcm} (\gcd(a,b),\gcd(b,c),\gcd(a,c)).}$

• Sea D el producto de ω ( D ) números primos distintos (es decir, D es libre de cuadrados ).

Entonces ^{[ 7 ]}

${\displaystyle |\{(x,y)\;:\;\operatorname {lcm} (x,y)=D\}|=3^{\omega (D)},}$

donde las barras absolutas || denotan la cardinalidad de un conjunto.

• Si ninguno de${\displaystyle a_{1},a_{2},\ldots ,a_{r}}$es cero, entonces

${\displaystyle \operatorname {lcm} (a_{1},a_{2},\ldots ,a_{r})=\operatorname {lcm} (\operatorname {lcm} (a_{1},a_{2},\ldots ,a_{r-1}),a_{r}).}$^{[ 8 ] [ 9 ]}