Máximo común divisor 

En el contexto de las matemáticas, el máximo común divisor representa el número más grande por el cual se pueden dividir dos o más números. Si se encuentran todos los factores de dos o más números y encuentra que algunos factores son los mismos («Común»), entonces el mayor de estos factores comunes es el Divisor común máximo. Abreviado como «MCD». Para descubrir cuáles son los números que los dividen, hay dos formas: la forma larga y la forma más corta.

Precisiones

Dados ${\displaystyle a}$ y ${\displaystyle b}$ dos números enteros distintos de cero. Si un número ${\displaystyle c}$ divide a ${\displaystyle a}$ y ${\displaystyle b}$, es decir, ${\displaystyle c|a}$ y ${\displaystyle c|b}$, diremos que ${\displaystyle c}$ es divisor común de ${\displaystyle a}$ y ${\displaystyle b}$.​ Obsérvese que dos números enteros cualesquiera tienen divisores comunes. Si los divisores comunes de ${\displaystyle a}$ y ${\displaystyle b}$ son únicamente 1 y -1 entonces diremos son primos entre sí'.

Un número entero d se llama máximo común divisor (M.C.D) de los números a y b cuando:

1. d es divisor común de los números a y b
2. d es divisible por cualquier otro divisor común de los números a y b.

Como calcularlo:

Usando el 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,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\,}$

operando:

${\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)}}}$

Propiedades

1. Si ${\displaystyle \ \operatorname {mcd} (a,b)=d}$ entonces ${\displaystyle \ \operatorname {mcd} \left({\frac {a}{d}},{\frac {b}{d}}\right)=1}$
2. Si ${\displaystyle \ m\in \mathbb {Z} }$, ${\displaystyle \ \operatorname {mcd} (ma,mb)=|m|\cdot \operatorname {mcd} (a,b)}$
3. Si ${\displaystyle \ p}$ es un número primo, entonces ${\displaystyle \ \operatorname {mcd} (p,m)=p}$ o bien ${\displaystyle \ \operatorname {mcd} (m,p)=1}$
4. Si ${\displaystyle d=\operatorname {mcd} (m,n),\ m=d'm'',\ n=d'n'',\ \operatorname {mcd} (m'',n'')=1}$, entonces ${\displaystyle \ d=d'}$
5. Si ${\displaystyle \ d'}$ es un divisor común de ${\displaystyle \ m}$ y ${\displaystyle \ n}$, entonces ${\displaystyle d'\mid \operatorname {mcd} (m,n)}$
6. Si ${\displaystyle \ m=nq+r}$, entonces ${\displaystyle \operatorname {mcd} (m,n)=\operatorname {mcd} (n,r)}$
7. Si ${\displaystyle \ 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:

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

Sigue aprendiendo.