Máximo común divisor

miniatura|Rectángulo 24×60 recuberto con dez baldosas cadradas de 12×12, onde 12 é o mcd de 24 e 60. En xeral, un rectángulo *a*×*b* pode recubrirse con baldosas cadradas de lado *c* só se *c* é un divisor común de *a* e *b*.
En matemáticas, o **máximo común divisor** (**MCD** ou **mdc**) ou **máximo divisor común** de dous ou máis números enteiros é o maior número enteiro que os divide sen deixar resto.

## Definicións 
Se *a* e *b* son números enteiros distintos de cero e se o número *c* é tal que *c*|*a* e á súa vez *c*|*b*, este número *c* denomínase *divisor común* dos números *a* e *b*. Cómpre observar que dous números enteiros calquera teñen divisores comúns; cando os únicos divisores comúns dos números *a* e *b* son 1 e -1, eses números chámanse primos entre si.

Un número enteiro *d* chámase máximo común divisor dos números *a* e *b* cando:
# *d* é divisor común dos números *a* e *b* e
# *d* é divisible por calquera outro divisor común dos números *a* e *b*.

**Exemplo**:
:12 é o mcd de 36 e 60. Pois 12|36 e 12|60; á súa vez 12 é divisible por 1, -1, 2, -2, 3, -3, 4, -4, 6, -6, 12 e -12 que son divisores comúns de 36 e 60.

## Cálculo do máximo divisor común 
O tres métodos máis utilizados para o cálculo do máximo divisor común de dous números son:

### Por descomposición en factores primos 
O máximo común divisor de dous números pode calcularse determinando a descomposición en factores primos dos dous números e tomando os factores comúns elevados á menor potencia, o produto dos cales será o mcd.

**Exemplo**: para calcular o máximo común divisor de 48 e de 60 obtense da súa factorización en factores primos.
dereita|200x200px

|
:
|}

O mcd son os factores comúns co seu menor expoñente, isto é:
: 
   \operatorname{mcd} (48; 60) =
   2^2 \cdot 3 =
   12

Na práctica, este método só é operativo para números pequenos levando en xeral demasiado tempo calcular a descomposición en factores primos de dous números calquera.

### Algoritmo de Euclides 
Un método máis eficiente é o algoritmo de Euclides, que emprega o algoritmo da división xunto co feito de que o mcd de dous números tamén divide o resto obtido de dividir o maior entre o máis pequeno.

**Exemplo 1**:
Se se divide 60 entre 48 dando un cociente de 1 e un resto de 12, o MCD será polo tanto divisor de 12. Despois divídese 48 entre 12 dando un resto de 0, o que significa que 12 é o mcd. Formalmente pode describirse como:
:\operatorname{mcd}(a,0) = a
:\operatorname{mcd}(a,b) = \operatorname{mcd}(b, a \,\mathrm{mod}\, b).

**Exemplo 2**:
O MCD de 42 e 56 é 14. En efecto:
: 
   \operatorname{mcd}(42,56) = 14 \,

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

### Co mínimo múltiplo común 
O máximo divisor común tamén pode ser calculado empregando o mínimo común múltiplo. Se *a* e *b* son distintos de cero, entón o máximo divisor común de *a* e *b* obtense mediante a seguinte fórmula, que involucra o mínimo múltiplo común de *a* e *b*:
: 
   \operatorname{mcd}(a,b) =
   \frac{a\cdot b}{\operatorname{MCM}(a,b)}

### MCD de tres ou máis números 
O máximo común divisor de tres ou máis números pódese definir recursivamente empregando o método:
 \ \operatorname{mcd}(a,b,c) = \operatorname{mcd}(a, \operatorname{mcd}(b,c)) .

## Propiedades 
1. Se \ \operatorname{mcd}(a,b)=d entón \ \operatorname{mcd} \left(\frac{a}{d}, \frac{b}{d}\right)= 1   
2. Se \ m é un enteiro, \ \operatorname{mcd}(ma,mb)= |m|\cdot \operatorname{mcd}(a,b) 
3. Se \ p é un número primo, entón \ \operatorname{mcd}(p,m)=p o bien \ \operatorname{mcd}(m,p)=1  
4. Se d=\operatorname{mcd}(m,n),\ m=d'm'',\ n=d'n*,\ \operatorname{mcd}(m*,n'')=1, entón \ d=d'  
5. Se \ d' é un divisor común de \ m e \ n, entón d'\mid \operatorname{mcd}(m,n)
6. Se \ m=nq+r, entón \operatorname{mcd}(m,n)=\operatorname{mcd}(n,r)
7. Se \ 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, entón  \operatorname{mcd}(m,n)=p_1^{\operatorname{min}(\alpha_1,\beta_1)}\cdots p_k ^ {\operatorname{min} (\alpha_k, \beta_k)}  Esta última propiedade indica que o máximo divisor común de dous números é o produto dos seus factores primos comúns elevados ao menor expoñente.

Xeometricamente, o máximo divisor común de *a* e *b* é o número de puntos de coordenadas enteiras que hai no segmento que une os puntos (0, 0) e (*a*, *b*), excluíndo o (0, 0).

### Proposicións 
# Para calquera par de números enteiros *a*≠0, *b*≠0, existe un único mcd *d* ≥ 1.
# O mcd. dos números *a* e *b* pode ser representado en forma de combinación linear destes números. Isto é (*a*, *b*) = *ax* + *by*
# Se dous números enteiros son primos entre si, i.e. o seu mcd = 1 ou noutra notación (*a*, *b*) = 1, entón cómpre a representación *ma* + *nb* = 1 onde *m* e *n* son números enteiros (identidade de Bézout).
# Se *a*|*bc* e (*a*, *b*) = 1, será *a*|*c*. Noutras palabras, se un número *a* divide un produto doutros dous números e é coprimo cun deles, entón divide necesariamente o outro número ou factor.
# Cando un número *a* é coprimo cos números *m* e *n*, tamén o é co produto *mn*.
# (*a*, *b*) é divisor de (*a*, *bc*)
# *t*(*a*, *b*) = (*ta*, *tb*) para todo *t* enteiro
# Se (*m*, *b*)= 1 entón (*am*, *b*)= (*a*, *b*)
# Se (*m*, *b*)= 1, (*am*, *n*) = 1 entón (*am*, *bn*) = (*a*, *b*)
# Para todo *x*, (*a*, *b*)= (*b*, *a*) = (*a*, -*b*) = (*a*, *b* + *ax*)
# Por definición, (0, 0) = 0; deste xeito o mcd defínese en todo ℤ×ℤ.
# (*a*, *b*) = *b* se e só se *b*|*a*, (ou sexa se *a* é múltiplo de *b*).
# Se (*a*, *b*)= *D*, entón (*an*, *bn*) = *Dn*
# *mZ* + *nZ* = (*m*, *n*)*Z*. Sumar senllos múltiplos de dous enteiros é o mesmo que considerar os múltiplos do seu máximo común divisor.
# (a^2, ab, b^2)= (a,b)^2

### MCD como operación interna 
* O mcd pódese estruturar como unha operación en ℤ; deste xeito a calquera par de enteiros, ou sexa a un elemento de ℤ×ℤ asígnalle un único elemento de ℤ.
* Para calquera par de enteiros (*a*, *b*) existe un enteiro non negativo d que é o seu máximo común divisor. Isto é *a***b* = (*a*, *b*) = *d*.
* O mcd goza da propiedade asociativa, como da propiedade conmutativa.
* O mcd posúe un elemento identidade, o cero, de modo tal que (*a*, 0)= (0, *a*)= *a*
* O mcd ten un comportamento dual que o mínimo común múltiplo, e aos enteiros non negativos *a* e *b* lígaos a ecuación *ab* = (*a*, *b*)[*a*, *b*]
* Propiedade do 1: (*a*, 1) = 1 para calquera enteiro *a*, pois o 1 é divisor de todos os enteiros, ou ben xera os elementos de ℤ.

## Aplicacións 
O mcd emprégase para simplificar fraccións. Por exemplo, para simplificar a fracción \scriptstyle \frac {48}{60} calcúlase primeiro o mcd(60, 48) = 12, dividíndose o numerador e o denominador da fracción inicial por 12 para obter a fracción simplificada \scriptstyle \frac {4}{5} .

O mcd tamén se emprega para calcular o mínimo común múltiplo de dous números. En efecto, o produto dos dous números é igual ao produto do seu máximo divisor común polo seu mínimo común múltiplo. Así, para calcular o mínimo común múltiplo de 48 e de 60, calcúlase primeiro o seu mcd, 12, sendo o seu mínimo común múltiplo \scriptstyle \frac {48 \cdot 60}{12} = 240 .

O mcd e o algoritmo de Euclides empréganse na resolución de ecuacións diofánticas lineares con dúas incógnitas e para desenvolver un número racional en fraccións continuas.

## Notas 
## Véxase tamén 
### Bibliografía 
*
* Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford Stein. *Introduction to Algorithms*, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 31.2: Greatest common divisor, pp.&nbsp;856–862.
*
* Donald Knuth. *The Art of Computer Programming*, Volume 2: *Seminumerical Algorithms*, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. Section 4.5.2: The Greatest Common Divisor, pp.&nbsp;333–356.
* 
* 
* Saunders MacLane e Garrett Birkhoff. *A Survey of Modern Algebra*, Fourth Edition. MacMillan Publishing Co., 1977. ISBN 0-02-310070-2. 1–7: "The Euclidean Algorithm."
### Ligazóns externas 
* Weisstein, Eric W. «Greatest Common Divisor».
* Método para calcular o máximo divisor e o mínimo múltiplo comúns á vez