RSS

Máximo común divisor

11 jun

En matemáticas, se define el máximo común divisor (abreviado MCD) de dos o más números enteros al mayor número que los divide sin dejar resto. Por ejemplo, el MCD de 42 y 56 es 14.

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:

Por descomposición en factores primos

Artículo principal: Factorización de enteros.

El máximo común divisor de dos números puede calcularse determinando la descomposición en factores primos de los dos números y tomando los factores comunes elevados a la menor potencia, el producto de los cuales será el MCD. Por ejemplo, para calcular el máximo común divisor de 48 y de 60 obtenemos la factorización en factores primos

De las factorizaciones de 48 y 60:

     \begin{array}{r|l}        48 & 2  \\        24 & 2  \\        12 & 2  \\         6 & 2  \\         3 & 3  \\         1 &       \end{array}
     48 = 2^4 \cdot 3 \,
     \begin{array}{r|l}        60 & 2  \\        30& 2  \\        15 & 3  \\         5 & 5  \\         1 &     \end{array}
     60 = 2^2 \cdot 3 \cdot 5 \,

El MCD son los factores comunes con su menor exponente, esto es:

     \operatorname{mcd} (48, 60) =     2^2 \cdot 3 =     12

En la práctica, este método solo es operativo para números pequeños tomando en general demasiado tiempo calcular la descomposición en factores primos de dos números cualesquiera.

Usando el algoritmo de Euclides

Artículo principal: Algoritmo de Euclides.

Un método más eficiente es el algoritmo de Euclides, que utiliza el algoritmo de la división junto al hecho que el MCD de dos números también divide al resto obtenido de dividir el mayor entre el más pequeño. Por ejemplo, si se divide 60 entre 48 dando un cociente de 1 y un resto de 12, el MCD será por tanto divisor de 12. Después se divide 48 entre 12 dando un resto de 0, lo que significa que 12 es el mcd. Formalmente puede describirse como:

\operatorname{mcd}(a,0) = a
\operatorname{mcd}(a,b) = \operatorname{mcd}(b,a - b \left\lfloor {a \over b} \right\rfloor).

En la práctica, este método solo es operativo para números pequeños tomando en general

Usando el mínimo común múltiplo

El máximo común divisor también puede ser calculado usando el mínimo común múltiplo. Si a y b son distintos de cero, entonces el máximo común divisor de a y b se obtiene mediante la siguente fórmula, que involucra el mínimo común múltiplo (mcm) de a y b:

\operatorname{mcd}(a,b)=\frac{a\cdot b}{\operatorname{mcm}(a,b)}.

MCD de tres o más números

El máximo común divisor de tres números se puede calcular como sigue:  \ \operatorname{mcd}(a,b,c) = \operatorname{mcd}(a, \operatorname{mcd}(b,c)) , aunque hay métodos más prácticos y sencillos.

Método de Nicómaco

Su cálculo se basa en restar el resto, del mayor número entre el menor número, al número menor hasta que nos dé el mismo número:

 

     60 | 48  
     12 | 36  
        | 24  
        | 12  

M.C.D (60,48) = 12
 
Deja un comentario

Publicado por en junio 11, 2012 en 5.Máximo común divisor

 

Deja un comentario

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

 
Seguir

Recibe cada nueva publicación en tu buzón de correo electrónico.

A %d blogueros les gusta esto: