que es El Máximo Común Divisor y da ejemplos
Respuestas a la pregunta
Respuesta:
El máximo común divisor (MCD) de dos o más número natural o enteros (no números con decimales) es el número más grande que les divide. Máximo común divisor (MCD) de 10 y 20: Divisor de 20: 1, 2, 4, 5, 10 y 20. Divisor de 10: 1, 2, 5 y 10
Explicación paso a paso:
El máximo común divisor de dos números a y b es el número más grande que divide a a y divide a b.
Para denotar el máximo común divisor de a y b escribiremos M.C.D.(a, b) ó MCD(a, b).
Respuesta:
Dados {\displaystyle a}a y {\displaystyle b}b dos números enteros distintos de cero. Si un número {\displaystyle c}c divide a {\displaystyle a}a y {\displaystyle b}b, es decir, {\displaystyle c|a}{\displaystyle c|a} y {\displaystyle c|b}{\displaystyle c|b}, diremos que {\displaystyle c}c es divisor común de {\displaystyle a}a y {\displaystyle b}b.1 Obsérvese que dos números enteros cualesquiera tienen divisores comunes. Si los divisores comunes de {\displaystyle a}a y {\displaystyle b}b son únicamente 1 y -1 entonces diremos son primos entre sí.
Un número entero d se llama máximo común divisor (MCD) de los números a y b cuando:
d es divisor común de los números a y b
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, 2, 3, 4, 6 y 12 que son divisores comunes de 36 y 60.2
Cálculo del Máximo Común Divisor
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
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
{\displaystyle {\begin{array}{r|l}48&2\\24&2\\12&2\\6&2\\3&3\\1&\end{array}}}{\displaystyle {\begin{array}{r|l}48&2\\24&2\\12&2\\6&2\\3&3\\1&\end{array}}}
{\displaystyle 48=2^{4}\cdot 3\,}{\displaystyle 48=2^{4}\cdot 3\,}
{\displaystyle {\begin{array}{r|l}60&2\\30&2\\15&3\\5&5\\1&\end{array}}}{\displaystyle {\begin{array}{r|l}60&2\\30&2\\15&3\\5&5\\1&\end{array}}}
{\displaystyle 60=2^{2}\cdot 3\cdot 5\,}{\displaystyle 60=2^{2}\cdot 3\cdot 5\,}
El MCD son los factores comunes con su menor exponente, esto es:
{\displaystyle \operatorname {MCD} (48;60)=2^{2}\cdot 3=12}{\displaystyle \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
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:
{\displaystyle \operatorname {mcd} (a,0)=a}{\displaystyle \operatorname {mcd} (a,0)=a}
{\displaystyle \operatorname {mcd} (a,b)=\operatorname {mcd} (b,a\,\mathrm {mod} \,b).}{\displaystyle \operatorname {mcd} (a,b)=\operatorname {mcd} (b,a\,\mathrm {mod} \,b).}
Ejemplo 2:
El MCD de 42 y 56 es 14. En efecto:
{\displaystyle \operatorname {mcd} (42,56)=14\,}{\displaystyle \operatorname {mcd} (42,56)=14\,}
operando:
{\displaystyle {\frac {42}{14}}=3\;,\quad {\frac {56}{14}}=4}{\displaystyle {\frac {42}{14}}=3\;,\quad {\frac {56}{14}}=4}
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 siguiente fórmula, que involucra el mínimo común múltiplo de a y b:
{\displaystyle \operatorname {MCD} (a,b)={\frac {a\cdot b}{\operatorname {mcm} (a,b)}}}{\displaystyle \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 o más números se puede definir usando recursivamente: {\displaystyle \ \operatorname {MCD} (a,b,c)=\operatorname {MCD} (a,\operatorname {MCD} (b,c))}{\displaystyle \ \operatorname {MCD} (a,b,c)=\operatorname {MCD} (a,\operatorname {MCD} (b,c))}
Explicación paso a paso: