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
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".
|