Minimo común multiplo

A El diagrama Venn muestra los múltiplos menos comunes de combinaciones de 2, 3, 4, 5 y 7 (6 se salta ya que es 2 × 3, ambos ya representados).
Por ejemplo, un juego de cartas que requiere que sus tarjetas se dividan por igual entre hasta 5 jugadores requiere por lo menos 60 tarjetas, el número en la intersección de los 2, 3, 4 y 5 sets, pero no el 7 set.

En aritmética y teoría de números, el mínimo común múltiplo, mínimo común múltiplo o mínimo común múltiplo de dos enteros a y b, generalmente denotados por lcm(a, b), es el entero positivo más pequeño que es divisible por a y b. Dado que la división de números enteros por cero no está definida, esta definición solo tiene sentido si a y b son distintos de cero. Sin embargo, algunos autores definen lcm(a,0) como 0 para todos los a, ya que 0 es el único múltiplo común de a y 0.

El mcm es el "mínimo común denominador" (lcd) que se puede usar antes de poder sumar, restar o comparar fracciones.

El mínimo común múltiplo de más de dos enteros a, b, c,... generalmente denotado por lcm(a, b, c,...), también está bien definido: Es el entero positivo más pequeño que es divisible por cada uno de a, b, c,...

Resumen

Un múltiplo de un número es el producto de ese número y un número entero. Por ejemplo, 10 es un múltiplo de 5 porque 5 × 2 = 10, por lo que 10 es divisible por 5 y 2. Como 10 es el entero positivo más pequeño que es divisible por 5 y 2, es el mínimo común múltiplo de 5 y 2. Por el mismo principio, 10 es el mínimo común múltiplo de −5 y −2 también.

Notación

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

Ejemplo

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

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,...}$

Múltiplos de 6 son:

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

Múltiplos comunes de 4 y 6 son los números que están 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.

Aplicaciones

Al sumar, restar o comparar fracciones simples, se usa el mínimo común múltiplo de los denominadores (a menudo llamado mínimo común denominador), porque cada una de las fracciones se puede expresar como una fracción con este denominador. Por ejemplo,

${displaystyle {2 over 21}+{1over 6}={4 over 42}+{7 over 42}={11 over 42}}$

donde se utilizó el denominador 42, por ser el mínimo común múltiplo de 21 y 6.

Problema de engranajes

Supongamos que hay dos engranajes en una máquina, teniendo m y n dientes, respectivamente, y los engranajes están marcados por un segmento de línea dibujado desde el centro del primer engranaje al centro del segundo engranaje. Cuando los engranajes comienzan a girar, el número de rotaciones del primer engranaje debe completar para realinear el segmento de línea se puede calcular utilizando ${displaystyle operatorname {lcm} (m,n)}$. El primer equipo debe completar ${displaystyle operatorname {lcm} (m,n) over m}$ rotaciones para el reajuste. Para entonces, el segundo equipo habrá hecho ${displaystyle operatorname {lcm} (m,n) over n}$ rotaciones.

Alineación planetaria

Supongamos que hay tres planetas girando alrededor de una estrella que toma l, m y n unidades de tiempo, respectivamente, para completar sus órbitas. Supongamos que l, m y n son enteros. Asumiendo 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 después de ${displaystyle operatorname {lcm} (l,m,n)}$ unidades de tiempo. En este momento, el primer, segundo y tercer planeta habrá completado ${displaystyle operatorname {lcm} (l,m,n) over l}$, ${displaystyle operatorname {lcm} (l,m,n) over m}$ y ${displaystyle operatorname {lcm} (l,m,n) over n}$ órbitas, respectivamente, alrededor de la estrella.

Cálculo

Usando el máximo común divisor

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 {Sobreviva}{gcd(a,b)}}}$

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

${displaystyle operatorname {lcm} (a,b)= duracióna sometida,{frac {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} ¿Qué?$

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

Estas fórmulas también son válidas cuando exactamente una de a y b< /span> es 0, ya que gcd(a, 0) = |a|. Sin embargo, si tanto a como b< /i> son 0, estas fórmulas provocarían la división por cero; por lo tanto, lcm(0, 0) = 0 debe considerarse como un caso especial.

Para volver al ejemplo anterior,

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

Existen algoritmos rápidos, como el algoritmo euclidiano para calcular el mcd que no requiere factorizar los números. Para números enteros muy grandes, existen algoritmos aún más rápidos para las tres operaciones involucradas (multiplicación, gcd y división); ver Multiplicación rápida. Como estos algoritmos son más eficientes con factores de tamaño similar, es más eficiente dividir el argumento más grande del mcm por el mcd de los argumentos, como en el ejemplo anterior.

Usando factorización prima

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

Por ejemplo:

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

Aquí, el número compuesto 90 se compone de un átomo del número primo 2, dos átomos del número primo 3 y un átomo del número primo 5.

Este hecho se puede usar para encontrar el mcm de un conjunto de números.

Ejemplo: mcm(8,9,21)

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

${9}9}34}4}4}4}4}}}}\2}\2}\2}cdot 7^{1}end{aligned}}$

El mcm será el producto de multiplicar la potencia más alta de cada número primo. La potencia más alta 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}=8cdot 9cdot 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 de la siguiente manera, con la descomposición en factores primos de cada uno de los dos números demostrados en cada círculo y todos los factores que comparten en la intersección. Luego, el mcm se puede encontrar multiplicando todos los números primos en el diagrama.

Este es un ejemplo:

48 = 2 × 2 × 2 × 3,

180 = 2 × 2 × 3 × 5,

compartiendo dos "2"s y un "3" en común:

Menos común múltiple = 2 × 2 × 2 × 3 × 3 × 5 = 720

Divisor común más grande = 2 × 2 × 3 = 12

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

Usando un algoritmo simple

Este método funciona fácilmente para encontrar el mcm de varios enteros.

Sea una secuencia finita de enteros positivos X = (x₁, x ₂,..., x_n), n > 1. El algoritmo procede en pasos de la siguiente manera: en cada paso m examina y actualiza la secuencia X^{(m) = (x₁(m), x₂ (m),..., x_n< sup>(m)}), X⁽¹⁾ = X, donde X^(m) es la mésima iteración de X, es decir, X en el paso m del algoritmo, etc. El propósito del examen es elegir el elemento mínimo (quizás uno de muchos) de la secuencia X ^(m). Suponiendo que x_k0^(m) es el elemento seleccionado, la secuencia X^(m+1) se define como

x_k^()m+1) = x_k^()m), k ل k₀

x_k0^()m+1) = x_k0^()m) + x_k0¹⁾.

Es decir, el elemento menor se incrementa en la correspondiente x mientras que el resto de elementos pasan de X^(m) a X^(m+1) sin cambios.

El algoritmo se detiene cuando todos los elementos en la secuencia X^(m) son iguales. Su valor común L es exactamente lcm(X).

Por ejemplo, si X = X⁽¹⁾ = (3, 4, 6), los pasos del algoritmo producen:

X²⁾ = (6, 4, 6)

X³⁾ = (6, 8, 6)

X⁴⁾ = (6, 8, 12) - eligiendo el segundo 6

X⁵⁾ = (9, 8, 12)

X⁽⁶⁾ = (9, 12, 12)

X⁽⁷⁾ = (12, 12, 12) so lcm = 12.

Usando el método de la tabla

Este método funciona para cualquier cantidad de números. Uno comienza enumerando todos los números verticalmente en una tabla (en este ejemplo, 4, 7, 12, 21 y 42):

El proceso comienza dividiendo todos los números por 2. Si 2 divide cualquiera de ellos de manera uniforme, escribe 2 en una nueva columna en la parte superior de la tabla y el resultado de la división por 2 de cada número en el espacio para la derecha en esta nueva columna. Si un número no es divisible por igual, simplemente vuelve a escribir el número. Si 2 no se divide por igual en ninguno de los números, repita este procedimiento con el siguiente número primo más pequeño, 3 (ver más abajo).

Ahora, asumiendo que 2 dividió al menos un número (como en este ejemplo), verifique si 2 divide nuevamente:

Una vez que 2 ya no divide ningún número en la columna actual, repita el procedimiento dividiendo por el siguiente número primo más grande, 3. Una vez que 3 ya no se divide, intente con los siguientes números primos más grandes, 5 luego 7, etc. El proceso termina cuando todos los números se han reducido a 1 (la columna debajo del último divisor primo consta solo de 1's).

Ahora, multiplica los números de la fila superior para obtener el mcm. En este caso, es 2 × 2 × 3 × 7 = 84.

Como algoritmo computacional general, lo anterior es bastante ineficiente. Uno nunca querría implementarlo en el software: toma demasiados pasos y requiere demasiado espacio de almacenamiento. Se puede obtener un algoritmo numérico mucho más eficiente utilizando el algoritmo de Euclides para calcular primero el mcd y luego obtener el mcm por división.

Fórmulas

Teorema fundamental de la aritmética

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

${displaystyle {fn}cdots =prod} ¿Qué?$

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

Dados dos números enteros positivos ${textstyle a=prod ¿Qué?$ y ${textstyle b=prod ¿Qué?$, su menos común divisor múltiple y mayor común son dados por las fórmulas

${displaystyle gcd(a,b)=prod ¿Qué?$

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, cada número racional se puede escribir únicamente como el 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 limit=2^{2}{0}, tendrían una relación=2^{1}3^{1}3}3}, tendrían un efecto=2^{1}=0}=2, tenían el nombre de operador {lcm} (4,6) correspondían=2}3^{1}=12[8pt]{1} {[8pt]{1}=0}=0}} {[8pt]}}=0}=0}}}}}=0}} {[4}=0}=0}=0}=0}=0}=0}=0}=0}=0}=0}=2}=0}=0}=0}=0}=0} {[4}=0}=0}=0}=0}=0}=0}=0}=0}=0}=0}=0}=0}=0}=0}=0}=0} { {0} {0} {0} {0} {0} {0} {0} {0}} {0} {0} {0} {0} {0} {0} {0} {0} {0} {0} {0} {0} {0} {0} {0} {0}} {0} {0} {0} {0} {0} {0} {0} {0}} {}}}} {}}} {}}}} {}}}}} {0}}}}}} {}}} {0}} {} {} {} {} {}}}}}}} {}}}}}}}}}}}}}}}}}} {}}}}}} {}}}} {} {}}}}}}}} {} {}}}}}} {} {}}}} {}}} {} {}}}}}} {} {} {} {}}}}}}}}}}} {}}}}}}}}}}}}}}} {1}{6} {=2^{-1}3^{-1} {3}{3}{3}{3}{4} {4}}} {2}}}} {cc} {cc}} {cc}}} {cc}}} {c}} {3} {c} {c}}} {cc}}}} {3}{3}{3}{}{3}{}{}} {3}{}}}}} {c}{}}} {c}}{}} {c}}}}} {c}} {}} {c} {}}}}} {}}}}}{}}}}}}}}{}}}}}}}} {c} {c} {c}}}} {c} {c} {c} {c}}}}}}}}}}}}}}} {c} {c} {c}} {c}}}}}}}}}}}}}}}}}}$

Enrejado-teórico

Los enteros positivos pueden estar parcialmente ordenados por divisibilidad: si a divide a b (es decir, si b es un entero múltiplo de < i>a) escribe a ≤ b (o equivalentemente, b ≥ a). (Tenga en cuenta que la definición habitual basada en la magnitud de ≤ no se usa aquí).

Bajo este ordenamiento, los enteros positivos se convierten en una red, con la reunión dada por el gcd y la reunión dada por el lcm. La prueba es sencilla, aunque un poco tediosa; equivale a comprobar que lcm y mcd satisfacen los axiomas de encuentro y unión. Poner el lcm y el gcd en este contexto más general establece una dualidad entre ellos:

Si una fórmula que implica variables enteros, gcd, lcm, ≤ y ≥ es verdadera, entonces la fórmula obtenida mediante conmutación gcd con lcm y conmutación ≥ con ≤ también es verdadera. (Recordar ≤ se define como divides).

Los siguientes pares de fórmulas duales son casos especiales de identidades teóricas reticulares generales.

También se puede demostrar que esta red es distributiva; es decir, lcm se distribuye sobre gcd y gcd se distribuye sobre lcm:

${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)). }$

Otro

• Vamos D ser el producto de ⋅()D) números primos distintos (es decir, D es libre de cuadrados).

Entonces

${displaystyle ¦{(x,y);:;;fnMicrosoftware {lcm} (x,y)=D}Sobreviv=3^{omega (D)}}$

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

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

${displaystyle operatorname {lcm} (a_{1},a_{2},ldotsa_{r})=operatorname {lcm} (operatorname {lcm} (a_{1},a_{2},ldotsa_{r-1}),a_{r}).}$

En anillos conmutativos

El mínimo común múltiplo se puede definir generalmente sobre anillos conmutativos de la siguiente manera: Sean a y b elementos de un anillo conmutativo R. Un múltiplo común de a y b es un elemento m de R tal que ambos a y b dividen m (es decir, existen elementos x e y de R< /i> tal que ax = m y by = m). Un mínimo común múltiplo de a y b es un múltiplo común que es mínimo, en el sentido de que para cualquier otro múltiplo común n de a y b, m divide n.

En general, dos elementos en un anillo conmutativo no pueden tener mínimo común múltiplo o más de uno. Sin embargo, dos mínimos comunes múltiplos cualesquiera del mismo par de elementos son asociados. En un dominio de factorización única, dos elementos cualesquiera tienen un mínimo común múltiplo. En un dominio ideal principal, el mínimo común múltiplo de a y b se puede caracterizar como un generador de la intersección de los ideales generados por a y b (la intersección de una colección de ideales es siempre un ideal).