Maximo Comun Divisor

Cálculo del Máximo Común Divisor
por Paulino Valderas
Como sabéis, en muchos problemas y ejercicios se necesita calcular el Máximo Común Divisor (m.c.d.) y el Mínimo Común Múltiplo (m.c.m.) de varios números. Algunos de vosotros conocéis la técnica del cálculo, pero para otros resulta un poco difícil, por no decir imposible, cuando hay que hacer el cálculo mentalmente. Para todos, sin embargo,sería interesante que os leyerais este artículo; puede que descubráis algo nuevo, o simplemente os ayude a comprender más a fondo algunos conceptos que parecen simples pero que son muy importantes.
Vamos por partes.
En primer lugar repasemos lo que es la descomposición factorial de los números naturales en factores primos.
Como sabéis todo número natural admite una descomposición única enfactores primos. Si tenemos por ejemplo el número 5600, para calcular la descomposición factorial iríamos probando a dividirlo entre los sucesivos números primos: 2, 3, 5, 7, 11, 13, 17,... Si resulta ser divisible entonces se hace la división, y se sigue probando con el cociente.
El número 5600 es divisible por 2. Dividimos y obtenemos 2800, que también es divisible por 2. Vamos obteniendosucesivamente 1400, 700, 350 y 175. Éste último número ya no es divisible por 2 así que probamos con el 3. Como la suma de sus cifras 1+7+5=13 y 13 no es divisible por 3, entonces el número 175 no es divisible por 3. Pero sí lo es por 5, dividimos y nos da 35. Volvemos a dividir y nos da 7, y como 7 es primo, ya hemos terminado la descomposición factorial. El proceso, (supuestamente conocido por todos) sepuede contemplar en el gráfico adjunto.
[pic]
La descomposición factorial de 5600 sería
[pic]
Supongamos que ahora queremos calcular los divisores de 5600, es decir todos los números posibles que dividen al 5600 de forma exacta. Si empezamos a pensar en algunos, se nos ocurrirán por ejemplo: 1, 2, 4, 5, 7, 10, 100,... ¿Pero como podríamos escribirlos todos? ¿Seguro que no se nos escaparáninguno?
La tarea es larga y laboriosa en general. Sin embargo podemos sistematizarla. ¿Cómo? Con ayuda de los factores primos.
En primer lugar debemos darnos cuenta que, aparte del número 1 que es divisor de cualquier número, cualquier divisor de 5600 se puede formar con los factores primos de la descomposición. Así, el 35 es divisor de 5600 (5600:35=160), porque 35=5·7, y tanto el 5 como el 7 formanparte de la descomposición de 5600. También 40 es divisor de 5600, (5600:40=140) ya que 40=2·2·2·5, y en la descomposición factorial de 5600 el 2 aparece cinco veces, por lo que cualquier número que en su descomposición factorial tenga el 2 cinco veces o menos puede dividir a 5600 siempre que el resto de los factores sean el cinco (dos veces como mucho) y el siete (una vez como mucho).
Entonces,si queremos averiguar todos los divisores de 5600, tenemos que tomar todas las combinaciones posibles de los factores primos, y eso es lo que vamos a hacer a continuación.
Con ningún factor: 1.
Con un solo factor: 2, 5, 7.
Con dos factores: 2·2, 2·5, 2·7, 5·5, 5·7. Es decir: 4, 10, 14, 25, 35.
Con tres factores: 2·2·2, 2·2·5, 2·2·7, 2·5·5, 2·5·7, 5·5·7. Es decir: 8, 20, 28, 50, 70, 175.
Concuatro factores: 2·2·2·2, 2·2·2·5, 2·2·2·7, 2·2·5·5, 2·2·5·7, 2·5·5·7. Es decir: 16, 40, 56, 100, 140, 350.
Con cinco factores: 2·2·2·2·2, 2·2·2·2·5, 2·2·2·2·7, 2·2·2·5·5, 2·2·2·5·7, 2·2·5·5·7. Es decir: 32, 80, 112, 200, 280, 700.
Con seis factores: 2·2·2·2·2·5, 2·2·2·2·2·7, 2·2·2·2·5·5, 2·2·2·2·5·7, 2·2·2·5·5·7. Es decir: 160, 224, 400, 560, 1400.
Con siete factores: 2·2·2·2·2·5·5,2·2·2·2·2·5·7, 2·2·2·2·5·5·7. Es decir: 800, 1120, 2800.
Con ocho factores: 2·2·2·2·2·5·5·7. Es decir: 5600.
(¡Uff, menudo trabajo!)
Luego la lista completa de divisores de 5600 es: 1, 2, 4, 5, 7, 8, 10, 14, 16, 20, 25, 28, 32, 35, 40, 50, 56, 70, 80, 100, 112, 140, 160, 175, 200, 224, 280, 350, 400, 560, 700, 800, 1120, 1400, 2800, 5600.
Supongamos que ahora tenemos otro número, por ejemplo el 1440,...