martes, 1 de marzo de 2016

MINIMO COMUN

Precisiones[editar]

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 denomina divisor común de los números a y b.1 Obsérvese que dos números enteros cualesquiera tienen divisores comunes. 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:
  1. d es divisor común de los números a y b y
  2. d es divisible por cualquier otro divisor común de los números a y b.
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, 3, -3, 4, -4, 6, -6, 12 y -12 que son divisores comunes de 36 y 60.2

Cálculo del MCD[editar]

Los tres 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]

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.
Divisores 48 60.svg
\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]

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.
Ejemplo 1:
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).
Ejemplo 2:
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

Usando el mínimo común múltiplo[editar]

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 siguiente fórmula, que involucra el mínimo común múltiplo de a y b:
\operatorname{mcd}(a,b) = \frac{a\cdot b}{\operatorname{MCM}(a,b)}

MCD de tres o más números[editar]

El máximo común divisor de tres o más números se puede definir usando recursivamente:  \ \operatorname{mcd}(a,b,c) = \operatorname{mcd}(a, \operatorname{mcd}(b,c)) .3 4

Propiedades[editar]

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]

  1. Para cualquier par de números enteros a≠0, b≠0, existe un único mcd d ≥ 1.5
  2. El m.c.d. de los números a y b puede ser representado en forma de combinación lineal de estos números. Esto es (a, b) = ax + by
  3. 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).
  4. 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.6
  5. Cuando un número a es coprimo con los números m y n, también lo es con el producto mn.7
  6. (a,b) es divisor de (a, bc)8
  7. t(a,b) = (ta, tb) para todo t entero9
  8. Si (m, b)= 1 entonces (am, b)= (a, b)10
  9. Si (m,b)= 1, (am, n) = 1 entones (am, bn) = (a, b)
  10. Para todo x, (a, b)= (b, a) = (a, -b) = (a, b + ax)11
  11. " Por definición, (0, 0) = 0 ".12 De tal modo el mcd se definiría en todo ℤxℤ.
  12. (a, b) = b si sólo si b | a, ( O sea si a es múltiplo de b).
  13. si (a,b)= D, entonces (an, bn) = Dn13
  14. mZ + nZ = (m,n)Z. Si sumamos sendos múltiplos de dos enteros es lo mismo que considerar los múltiplos de su máximo común divisor.14
  15. (a^2, ab, b^2)= (a,b)^215

MCD como operación interna[editar]

  • EL Mcd se puede estructurar como una operación en ℤ, de este modo a cualquier par de enteros, o sea a un elemento de ℤxℤ le asigna un único elemento de ℤ.
  • Para cualquier par de enteros (a,b) existe un entero no negativo d que es su máximo común divisor. Esto es a*b = (a,b) = d
  • El MCD goza de la propiedad asociativa, como de la propiedad conmutativa.
  • El mcd posee un elemento identidad, el cero, de modo tal que (a, 0)= (0,a)= a16
  • El mcd tiene un comportamiento dual que el mínimo común múltiplo y a los enteros no negativos a y b los liga la ecuación ab = (a,b)[a,b]17
  • Propiedad de 1: (a,1) = 1 para cualquier entero a18
Publicado por en

No hay comentarios:

Publicar un comentario

Suscribirse a: Enviar comentarios (Atom)