MATEMATICAS 2°parcial: MAXIMO COMUN DIVISOR (MCD)

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 losdivide sin dejar resto. Por ejemplo, el mcd de 42 y 56 es 14. En efecto:

$\operatorname{mcd}(42,56) = 14 \,$

operando:

$\frac{42}{14} = 3 \; , \quad \frac{56}{14} = 4$

Siendo 3 y 4 primos entre sí (no existe ningún número natural, aparte de 1, que divida a la vez al 3 y al 4).

Precisiones[editar · editar código]

Si a y b son números enteros distintos de cero y si el número c es de modo que c|a y a su vez c|b, a este número c se denominadivisor común de los números a y b.¹ Obsérvese que dos números enteros cualesquiera tienen divisores comunes. Ellos son 1 y -1. Cuando existen, únicamente, como divisores comunes 1 y -1 de los números a y b, estos se llaman primos entre sí.

Un número entero d se llama máximo común divisor (mcd) de los números a y b cuando: i) d es divisor común de los números a yb y ii) d es divisible por cualquier otro divisor común de los números a y b.

Como ejemplo, 12 es el mcd de 36 y 60. Pues 12|36 y 12|60; a su vez 12 es divisible por 1, -1, 2, -2, 4, -4, 6, -6, 12 y -12 que son divisores comunes de 36 y 60.²

Cálculo del mcd[editar · editar código]

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[editar · editar código]

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.

Ejemplo: para calcular el máximo común divisor de 48 y de 60 se obtiene de su factorización en factores primos

$\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 cualquiera.

Usando el algoritmo de Euclides[editar · editar código]

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).$

MCD de tres o más números[editar · editar código]

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.

Propiedades[editar · editar código]

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

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

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

4. Si $d=\operatorname{mcd}(m,n),\ m=d'm'',\ n=d'n'',\ \operatorname{mcd}(m'',n'')=1$ , entonces $\ d=d'$

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

6. Si $\ m=nq+r$ , entonces $\operatorname{mcd}(m,n)=\operatorname{mcd}(n,r)$

7. Si $\ m=p_1^{\alpha_1}\cdots p_k^{\alpha_k}\;\, \mathrm y \;\, n=p_1^{\beta_1}\cdots p_k^{\beta_k},\;\, \alpha_i, \beta_i\geq 0, \;\, i=1,...,k$ , entonces:

$\operatorname{mcd}(m,n)=p_1^{\operatorname{min}(\alpha_1,\beta_1)}\cdots p_k ^ {\operatorname{min} (\alpha_k, \beta_k)}$

La última propiedad indica 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).

Proposiciones[editar · editar código]

Para cualquier par de números enteros a≠0, b≠0, existe un mcd. ³
El m.c.d. de los números a y b puede ser representado en forma de combinación lineal de estos números.
Si dos números enteros son primos entre sí, i.e. su mcd = 1 o en otra notación (a,b) = 1, entonces cabe la representación ma+ nb = 1 donde m y n son números enteros (Identidad de Bézout).
si a|bc y (a,b) = 1, será a|c. En otras palabras, si un número a divide un producto de otros dos números y es coprimo con uno de ellos, entonces divide necesariamente el otro número o factor⁴ .
Cuando un número a es coprimo con los números m y n, también lo es con el producto mn⁵ .

Aplicaciones[editar · editar código]

El mcd se utiliza para simplificar fracciones. Por ejemplo, para simplificar la fracción $\scriptstyle \frac {48}{60}$ se calcula primero el mcd(60, 48) = 12, dividiéndose el numerador y el denominador de la fracción inicial por 12 para obtener la fracción simplificada $\scriptstyle \frac {4}{5}$ .

El mcd también se utiliza para calcular el mínimo común múltiplo de dos números. En efecto, el producto de los dos números es igual al producto de su máximo común divisor por su mínimo común múltiplo. Así, para calcular el mínimo común múltiplo de 48 y de 60, calculamos primero su mcd, 12, siendo su mínimo común múltiplo $\scriptstyle \frac {48 \cdot 60}{12} = 240$ .

El mcd y el algoritmo de Euclides se emplea en la resolución de ecuaciones diofánticas lineales con dos incógnitas.⁶

Referencias[editar · editar código]

Jump up↑ «División inexacta» (1997) Belski y Kaluzhin Editorial Científica, Lima; pg.10
Jump up↑ Ibídem, pg. 10
Jump up↑ Ibídem, pg. 11
Jump up↑ Ibídem, pg. 13
Jump up↑ Ibídem, pg. 13
Jump up↑ Ibídem pg. 17 y 20

MATEMATICAS 2°parcial

jueves, 3 de octubre de 2013

MAXIMO COMUN DIVISOR (MCD)