Mínimo común múltiplo (mcm) en Python

Esta entrada del blog pertenece a una serie:

• Números primos en Python
• Factorización en Python
• Máximo común divisor (MCD) en Python
• Mínimo común múltiplo (mcm) en Python

Veamos la denominación en inglés y en español.

• gcd = greatest common divisor = máximo común divisor = MCD
• lcm = least common multiple = mínimo común múltiplo = mcm 

Código en repl.it

Concepto y resolución manual

El mínimo común múltiplo de dos o más números es el menor de los múltiplos comunes a todos ellos.

Ejemplo

El mcm de 12 y 22 es igual a 132. En la imagen se pueden ver los múltiplos de 12 en la columna C y los múltiplos de 22 en la columna D. En color naranja se ven los múltiplos comunes, siendo el menor de  todos ellos el número 132.

La resolución manual tiene los siguientes pasos.

1. Descomponemos en factores primos ambos números. En nuestro ejemplo: 
• 12 = 2² × 3 × 1
• 22 = 2 × 11 × 1
2. El mcm se forma con el producto de los números comunes y no comunes a la máxima potencia. En nuestro ejemplo:
• mcm(12,22) = 2² × 3 × 11 = 132

mcm → comunes y no comunes a la máxima potencia

Usos del mínimo común múltiplo

Caso 1

Podemos calcular el menor número divisible entre dos números dados a y b. Por ejemplo, si nos piden:

Calcular el menor número que es divisible entre 12 y entre 21.

Ese número sería 132 que es el mcm de 12 y 21.

Caso 2

Dos amigos hacen la misma ruta uno cada 12 días y otro cada 22 días. ¿Cuándo coincidirán?

Siempre que tengamos casos de fenómenos periódicos con diferente frecuencia y nos pidan calcular la próxima coincidencia, estamos ante un caso de cálculo del mínimo común múltiplo.

La solución en este caso, sería el mcm de ambos números que es 132 días.

Método 1: calculando previamente el Máximo común divisor

La relación entre el MCD (Máximo común divisor) y el mínimo común múltiplo (mcm) de dos números a y b es la siguiente.

a × b = MCD(a,b) × mcm(a,b)

Calcularemos previamente el MCD usando la función math.gcd.

from math import gcd  
x=300  
y=33880  
MCD=gcd(x,y)  
mcm=int(x*y/gcd(x,y))  
print("El mínimo común múltiplo entre {} y {} es {}\n".format(x,y,mcm))  
print('''Si los dos números son a y b se puede comprobar que:\n  
\ta × b = MCD × mcm''')  
print('\t{} × {} = {} × {}'.format(x,y,MCD,mcm))  

Método 2: buscando los múltiplos comunes

Nos metemos en un bucle donde vamos dando valores a una variable instrumental t que representa el número de veces que se han de multiplicar a y b, para llegar a obtener los sucesivos múltiplos. Esos valores se van añadiendo a sendas listas y cada nueva incorporación se va comprobando si el valor obtenido se encuentra en la otra lista. Cuando se produce esa coincidencia es que hemos encontrado el mínimo común múltiplo.

def mcm(a,b):  
 multiplos_a=[]  
 multiplos_b=[]  
 for t in range(1,a*b+1):  
  multiplos_a.append(t*a)  
  multiplos_b.append(t*b)  
  if t*a in multiplos_b:  
   return t*a  
  elif t*b in multiplos_a:  
   return t*b  
 return a*b  
x=12  
y=22  
print('El mínimo común múltiplo de {} y {} es {}.'.format(x,y,mcm(x,y)))  

Método 3: mcm de varios números

Existe una propiedad matemática que nos dice que

mcm(a,b,c) = mcm(a, mcm(b,c)

Esto se puede extender, no solo a tres números a, b, c sino a cualquier cantidad de números sobre los que queramos calcular el mínimo común múltiplo, utilizando para ello la recurrencia.