Máximo común divisor

¿Cómo se calcula el máximo común divisor?

Ya sabemos encontrar todos los divisores de un número. Ahora nos interesa hallar un divisor en concreto. Queremos, de entre todos los divisores comunes a varios enteros, el mayor de ellos.

Te preguntarás varias cosas... "¿por qué el mayor?", "¿por qué un divisor común a varios enteros?", "¿sirve esto para algo?" Lo cierto es que el cálculo del máximo común divisor será muy útil para resolver problemas de divisibilidad en los que estén involucrados varios números. Por eso lo de común y divisor. ¿Por qué el mayor y no, por ejemplo, el menor? Piensa detenidamente... ¿Qué número es divisor de cualquier entero?, ¿crees que hay divisores menores que ese número?

Una primera solución podría ser calcular los divisores de cada uno de los enteros con los que estemos trabajando y comprobar cuál es el mayor de los divisores comunes. Sin embargo, es una mala estrategia, porque para números muy grandes tendríamos que hacer muchísimas cuentas.

Acabamos de estudiar que los divisores de un número son una combinación de algunos de sus factores primos. Por tanto, si queremos un divisor común a varios enteros, tendremos que tomar factores primos comunes a todos esos enteros. Si además queremos que sea el mayor de todos los divisores comunes, tendremos que tomar todos los factores que sean comunes, sin olvidarnos de ninguno.

Por ejemplo, si queremos encontrar el máximo común divisor de 120 y 252, lo que hacemos es comparar sus descomposiciones y escoger todos los factores que sean comunes.

ejemplo

 Ni siquiera es necesario separar las potencias como hemos hecho en el ejemplo anterior. Sólo necesitas hacer dos cosas:

icono_algoritmo ALGORITMO Para calcular el máximo común divisor (\begin{verbatim}m.c.d.\end{verbatim}) de varios enteros:

  • Descomponemos los números en factores primos.
  • Escogemos los factores primos comunes a todos ellos, elevados al menor de los exponentes con que aparecen.

Para el ejemplo anterior, después de hacer las descomposiciones, sólo escribiríamos:

esquema

icono_observacion OBSERVACIÓN Cuando nos parezca que no hay ningún factor común, en realidad nos estamos olvidando del 1, que no es primo, pero es factor de cualquier número entero. Por tanto, si no hay coincidencia de ningún factor primo, el máximo común divisor es 1.

Ejemplos

 e
 e
 e
 e
Piensa...

¿Qué sucede si nos piden calcular el máximo común divisor de dos números y uno de esos números es divisor del otro?

Ejercicio

icono_libreta+icono_ordenador Calcula en tu libreta el máximo común divisor de cada apartado utilizando el método que acabamos de describir. Comprueba al final el resultado.

a) \begin{verbatim}m.c.d.\end{verbatim}\(10,15\)=  f) \begin{verbatim}m.c.d.\end{verbatim}\(135,180\)= 
b) \begin{verbatim}m.c.d.\end{verbatim}\(16,24\)=  g) \begin{verbatim}m.c.d.\end{verbatim}\(48,72\)= 
c) \begin{verbatim}m.c.d.\end{verbatim}\(12,16\)=  h) \begin{verbatim}m.c.d.\end{verbatim}\(105,120\)= 
d) \begin{verbatim}m.c.d.\end{verbatim}\(18,32\)=  i) \begin{verbatim}m.c.d.\end{verbatim}\(8,12,16\)= 
e) \begin{verbatim}m.c.d.\end{verbatim}\(36,45\)=  j) \begin{verbatim}m.c.d.\end{verbatim}\(45,60,105\)=