Minimo común multiplo - Least common multiple

Un diagrama de Venn que muestra los múltiplos menos comunes de combinaciones de 2, 3, 4, 5 y 7 (6 se omite porque es 2 × 3, los cuales ya están representados).
Por ejemplo, un juego de cartas que requiere que sus cartas se dividan equitativamente entre hasta 5 jugadores requiere al menos 60 cartas, el número en la intersección de los juegos 2, 3, 4 y 5, pero no el juego 7.

En aritmética y teoría de los números , el mínimo común múltiplo , más bajo múltiplo común , o más pequeño común múltiplo de dos números enteros un y b , generalmente denotado por lcm ( un ,  b ) , es el número entero positivo más pequeño que es divisible por tanto una y b . Desde la división de números enteros por cero no está definida, esta definición no ha hecho más que significa que si un y b son ambos diferentes de cero. Sin embargo, algunos autores definen lcm ( a , 0) como 0 para todo a , que es el resultado de tomar el lcm como el mínimo límite superior en la celosía de divisibilidad.

El mcm es el " mínimo común denominador " (lcd) que se puede usar antes de que se puedan sumar, restar o comparar fracciones . El mcm de más de dos enteros también está bien definido: es el menor entero positivo divisible por cada uno de ellos.

Visión general

Un múltiplo de un número es el producto de ese número por un número entero. Por ejemplo, 10 es un múltiplo de 5 porque 5 × 2 = 10, entonces 10 es divisible entre 5 y 2. Como 10 es el número 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. Según 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 números enteros a y b se denota como lcm ( un , b ). Algunos libros de texto antiguos usan [ a , b ], mientras que el lenguaje de programación J usa a*.b.

Ejemplo

${\ 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 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 el 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} + {1 \ over 6} = {4 \ over 42} + {7 \ over 42} = {11 \ over 42}}$

donde se usó el denominador 42, porque es el mínimo común múltiplo de 21 y 6.

Problema de engranajes

Supongamos que hay dos engranajes de engrane en una máquina , teniendo m y n dientes, respectivamente, y los engranajes están marcados por un segmento de línea trazada desde el centro del primer engranaje para el centro de la segunda marcha. Cuando los engranajes comienzan a girar, el número de rotaciones que debe completar el primer engranaje para realinear el segmento de línea se puede calcular usando . La primera marcha debe completar rotaciones para el realineamiento. En ese momento, la segunda marcha habrá realizado rotaciones. ${\ Displaystyle \ operatorname {lcm} (m, n)}$${\ Displaystyle \ operatorname {lcm} (m, n) \ over m}$${\ Displaystyle \ operatorname {lcm} (m, n) \ over n}$

Alineación planetaria

Supongamos que hay tres planetas que giran alrededor de una estrella que toman l , m y n unidades de tiempo, respectivamente, para 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 vuelven a alcanzar una alineación lineal después de unidades de tiempo. En este momento, el primer, segundo y tercer planeta se habrá completado , y órbitas, respectivamente, alrededor de la estrella. ${\ Displaystyle \ operatorname {lcm} (l, m, n)}$${\ Displaystyle \ operatorname {lcm} (l, m, n) \ over l}$${\ Displaystyle \ operatorname {lcm} (l, m, n) \ over m}$${\ Displaystyle \ operatorname {lcm} (l, m, n) \ over n}$

Cálculo

Usando el máximo común divisor

La siguiente fórmula reduce el problema de calcular el mínimo común múltiplo al problema de calcular el máximo común divisor (mcd), también conocido como el máximo común divisor :

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

Esta fórmula también es válida cuando exactamente uno de a y b es 0, ya que mcd ( a , 0) = | a |. Sin embargo, si tanto a como b son 0, esta fórmula provocaría una división por cero ; lcm (0, 0) = 0 es un caso especial.

Existen algoritmos rápidos para calcular el mcd que no requieren factorizar los números , como el algoritmo euclidiano . Para volver al ejemplo anterior,

${\ Displaystyle \ operatorname {lcm} (21,6) = {21 \ cdot 6 \ over \ gcd (21,6)} = {21 \ cdot 6 \ over \ gcd (3,6)} = {21 \ cdot 6 \ over 3} = {\ frac {126} {3}} = 42.}$

Debido gcd ( a , b ) es un divisor de tanto un y b , que es más eficiente para calcular la lcm dividiendo antes multiplicando:

${\ Displaystyle \ operatorname {lcm} (a, b) = \ left ({| a | \ over \ gcd (a, b)} \ right) \ cdot | b | = \ left ({| b | \ over \ gcd (a, b)} \ derecha) \ cdot | a |.}$

Esto reduce el tamaño de una entrada tanto para la división y la multiplicación, y reduce el almacenamiento requerido necesario para resultados intermedios (es decir, el desbordamiento en el un × b cálculo). Debido gcd ( a , b ) es un divisor de tanto un y b , la división está garantizado para producir un número entero, por lo que el resultado intermedio se puede almacenar en un número entero. Implementado de esta manera, el ejemplo anterior se convierte en:

${\ Displaystyle \ operatorname {lcm} (21,6) = {21 \ over \ gcd (21,6)} \ cdot 6 = {21 \ over \ gcd (3,6)} \ cdot 6 = {21 \ over 3} \ cdot 6 = 7 \ cdot 6 = 42.}$

Usando la factorización prima

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

Por ejemplo:

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

Aquí, 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 se puede usar para hallar el mcm de un conjunto de números.

Ejemplo: mcm (8,9,21)

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

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

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} = 8 \ cdot 9 \ cdot 7 = 504.}$

Este método no es tan eficiente como reducir al máximo común divisor, ya que no se conoce un 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 factorización prima de cada uno de los dos números demostrados en cada círculo y todos los factores que comparten en común en la intersección. Entonces, el mcm se puede encontrar multiplicando todos los números primos en el diagrama.

Aquí hay un ejemplo:

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

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

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

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

Máximo común divisor = 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 como sigue: en cada paso m examina y actualiza la secuencia X ^{( m )} = ( x ₁ ^{( m )} , x ₂ ^{( m )} , ..., x _n ^{( 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 seleccionar el elemento menor (quizás uno de muchos) de la secuencia X ^{( m )} . Suponiendo que x _{k 0} ^{( m )} es el elemento seleccionado, la secuencia X ^{( m +1)} se define como

x _k ^{( metro +1)} = x _k ^{( metro )} , k ≠ k ₀

x _{k 0} ^{( metro +1)} = x _{k 0} ^{( metro )} + x _{k 0} ⁽¹⁾ .

En otras palabras, el elemento mínimo se incrementa en la correspondiente x mientras que el resto de los elementos pasan de X ^{( m )} a X ^{( m +1)} sin cambios.

El algoritmo se detiene cuando todos los elementos de la secuencia X ^{( m )} son iguales. Su valor común L es exactamente mcm ( 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) entonces mcm = 12.

Usando el método de la tabla

Este método funciona para cualquier número 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, escriba 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 a la derecha de esta nueva columna. Si un número no es divisible uniformemente, simplemente vuelva a escribir el número. Si 2 no se divide uniformemente en ninguno de los números, repita este procedimiento con el siguiente número primo más grande, 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 divida, pruebe los siguientes números primos más grandes, 5 luego 7, etc. El proceso termina cuando todos los números primos los números se han reducido a 1 (la columna debajo del último divisor primo consta solo de unos).

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 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 Euclid 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 , un entero positivo es el producto de números primos , y esta representación es única hasta el orden de los números primos:

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

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 y , su mínimo común múltiplo y su máximo común divisor vienen dados por las fórmulas ${\ textstyle a = \ prod _ {p} p ^ {a_ {p}}}$${\ textstyle b = \ prod _ {p} p ^ {b_ {p}}}$

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

Ya que

${\ 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 de forma única 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 {align} 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 {alineado}}}$

Teórico de celosía

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

Bajo este orden, los enteros positivos se convierten en una celosía , con meet dado por el mcd y join dado por el mcm. La prueba es sencilla, aunque un poco tediosa; equivale a comprobar que lcm y gcd satisfacen los axiomas de meet y join. Poner el lcm y el gcd en este contexto más general establece una dualidad entre ellos:

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

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

También se puede demostrar que esta red es distributiva ; es decir, lcm distribuye sobre gcd y gcd 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 auto-dual:

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

Otro

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

Luego

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

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

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

${\ Displaystyle \ operatorname {lcm} (a_ {1}, a_ {2}, \ ldots, a_ {r}) = \ operatorname {lcm} (\ operatorname {lcm} (a_ {1}, a_ {2}, \ ldots, a_ {r-1}), a_ {r}).}$

En anillos conmutativos

El mínimo común múltiplo se puede definir generalmente sobre anillos conmutativos como sigue: Sea una y b ser elementos de un anillo conmutativo R . Un múltiplo común de una y b es un elemento m de R tal que tanto una y b brecha m (, existen que es elementos x y y de R tal que ax = m y por = m ). Un mínimo común múltiplo de a y b es un común múltiplo que es mínimo, en el sentido de que para cualquier otro común n de a y b , m divide  n .

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

Ver también

• Cancelación anómala
• Enteros primos
• Función de Chebyshev

Notas

Referencias

• Crandall, Richard; Pomerance, Carl (2001), Números primos: una perspectiva computacional , Nueva York: Springer , ISBN 0-387-94777-9
• Hardy, GH; Wright, EM (1979), Introducción a la teoría de los números (quinta edición) , Oxford: Oxford University Press , ISBN 978-0-19-853171-5
• Landau, Edmund (1966), Teoría de números elemental , Nueva York: Chelsea
• Long, Calvin T. (1972), Introducción elemental a la teoría de números (2a ed.), Lexington: DC Heath and Company , LCCN  77-171950
• Pettofrezzo, Anthony J .; Byrkit, Donald R. (1970), Elementos de la teoría de números , Englewood Cliffs: Prentice Hall , LCCN  77-81766