Máximo Común Divisor

Cálculo del Máximo Común Divisor

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 en factores 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 obteniendo sucesivamente 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) se puede contemplar en el gráfico adjunto.

La descomposición factorial de 5600 sería

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 forman parte 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.

Con cuatro 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, y queremos calcular el m.c.d. de ambos. Como la definición misma dice, tenemos que buscar un número que sea divisor de los dos, de 5600 y de 1440, y que sea el mayor posible. Así, de entrada, divisores comunes se nos pueden ocurrir varios: el 1 sería el más fácil, también el 2, el 5 o el 10. ¿Pero cuál es el mayor de todos?

Una idea perfectamente válida sería sacar la lista de los divisores de 1440, compararla con la de 5600, ver qué números aparecen en las dos listas y tomar el mayor.

Vamos a hacerlo. Descomponemos 1440 en factores primos.

Haciendo el mismo proceso que hemos hecho arriba (y que vosotros podéis comprobar haciéndolo vosotros mismos en una hoja de papel), nos sale la siguiente lista de divisores: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 30, 32, 36, 40, 45, 48, 60, 72, 80, 90, 96, 120, 144, 160, 180, 240, 288, 360, 480, 720, 1440.

Si comprobáis ambas listas veréis que los divisores comunes (los que aparecen en las dos) son: 1, 2, 4, 5, 8, 10, 16, 20, 32, 40, 80, 160.

¡Luego el m.c.d. es 160!

¿De verdad hay que hacer tanto trabajo para calcular el m.c.d.?

Por supuesto que no. ¿Cómo hemos obtenido los divisores? Tomando los factores primos de la descomposición en todas las combinaciones posibles. Saldrán divisores comunes CUANDO TOMEMOS FACTORES QUE APAREZCAN EN LAS DOS DESCOMPOSICIONES.

Si queremos construir un divisor común podemos tomar el 2 y el 5, porque ambos números aparecen en la descomposición de 5600 y de 1440. Pero no podemos tomar el 7, que sólo aparece en el 5600, ni el 3, que sólo aparece con el 1440.

Además el 2 lo podemos tomar cinco veces, pues aparece cinco veces tanto en el 5600 como en el 1440. Pero el 5 sólo lo podemos tomar una vez: en el 1440 sólo aparece una vez.

De aquí: 2·2·2·2·2·5 = 160.

Espero que ahora entendáis mejor la famosa REGLA PARA OBTENER EL M.C.D. DE DOS NÚMEROS: "De la descomposición factorial de ambos números se toman los factores primos comunes con el menor exponente".