Máximo común divisor

El maximo como un divisor:

(«m.c.d.» o «mcd») de dos o más números naturales es el mayor divisor posible de todos ellos.

Propiedades

Ejemplo m.c.d:

        mcd(5,7)=1,  mcd(10,20)=10,  mcd(100,7)=1

1. Si $\ mcda,bd$ entonces $\ mcd\left({\frac {a}{d}},{\frac {b}{d}}\right)=1$

2. Si $\ m$ es un entero, $\ mcd(ma,mb)=|m|\cdot mcd(a,b)$

3. Si $\ p$ es un número primo, entonces $\ mcd(p,m)=p$ o bien $mcd(p,m)=1$

4. Si $\ d=mcd(m,n),\ m=dm',\ n=dn'$, entonces $\ mcd(m',n')=1$

5. Si $d=mcd(m,n),\ m=d'm'',\ n=d'n'',\ mcd(m'',n'')=1$, entonces $\ d=d'$

6. Si $\ d'$ es un divisor común de $\ m$ y $\ n$, entonces $d'\mid mcd(m,n)$

7. Si $\ m=nq+r$, entonces $\ mcd(m,n)=mcd(n,r)$

8. Si $\ m=p_{1}^{\alpha _{1}}\cdots p_{k}^{\alpha _{k}}$ y $\ n=p_{1}^{\beta _{1}}\cdots p_{k}^{\beta _{k}},\$$\alpha _{i},\beta _{i}\geq 0,i=1,...,k$, entonces:

$mcd(m,n)=p_{1}^{min(\alpha _{1},\beta _{1})}\cdots p_{k}^{min(\alpha _{k},\beta _{k})}$

La última propiedad dice que el máximo común divisor de dos números resulta ser el producto de sus factores primos comunes elevados al menor exponente....

Geométricamente, el máximo común divisor de a y b es el número de puntos de coordenadas enteras que hay en el segmento que une los puntos (0,0) y (a,b), excluyendo el (0,0).

En palabras más simples, el máximo común divisor de dos o más números es el número, más grande posible, que permite dividir a esos números al mismo tiempo.

Cálculo del MCD

Los dos métodos más utilizados para el cálculo del máximo común divisor de dos números son:

• Se descompondrán los números en factores primos y se tomarán los factores comunes con su menor exponente, el producto de los cuales será el m.c.d.

• Si el número es muy grande este método no es operativo porque no conocemos los posibles factores. En ese caso tenemos que utilizar el más rápido algoritmo de Euclides.

El m.c.d. de tres números se puede calcular como sigue: mcd(a,b,c) = mcd(a, mcd(b,c)).

• mcd(48, 60). Podemos comprobar que los divisores de 48 y 60 son:

48 = {1,2,3,4,6,8,12,16,24,48};

60 = {1,2,3,4,5,6,10,12,15,20,30,60}

por lo que el máximo común divisor de ambos es 12. Véamoslo utilizando los dos métodos descritos anteriormente:

• De las factorizaciones de 48 y 60, (48 = 2⁴.3 y 60=2².3.5) podemos inferir que su m.c.d. es 2².3 = 12 o comúnmente expresado como mcd(60,48)=12.

Como puede verse hemos necesitado calcular los factorización de 48 y 60 en factores primos (En torno a 10 divisiones siendo los factores sencillos).

• Si en cambio utilizamos el algoritmo de Euclides:

Calculamos el resto de dividir 60 por 48, 12 (En este caso es igual a restar 48 a 60).

Calculamos el resto de dividir 48 por 12: 0. Por tanto, el mcd de 48 y 60 es 12.

Como puede verse utilizando el algoritmo de Euclides hemos necesitado:

Una resta

Una división

• otro ejemplo:

(6936,1200) = 2³ · 3 = 24.

• un último ejemplo, mcd(7000000, 7000002).

Tras un sencillo cálculo obtenemos los factores de ambos números:

7000000 = 2⁶ . 5⁶ . 7

7000002 = 2¹ . 3² . 157 . 2477

por lo que su mcd es 2 (Se trata del único factor común elevado al mínimo exponente, 1).

Si utilizamos el algoritmo de Euclides llegamos al mismo resultado (haciendo dos divisiones).

Hay también un método gráfico y sencillo para calcular el máximo común divisor, véase el vídeo de abajo, en apartado enlaces externos.

El MCD es inversamente proporcional a este.

Véase también

• Mínimo común múltiplo
• Algoritmo de Euclides

Enlaces externos

• El Máximo común divisor en Enciclopedia libre universal en español
• La calculadora MCD en línea ( 4 métodos )
• MCD en números decimales