# Máximo divisor comum

O máximo divisor comum (abreviadamente, MDC) entre dois ou mais números reais é o maior número real que é fator de tais números. Por exemplo, os divisores comuns de $12$ e $18$ são $1,2,3$ e $6$, logo $mdc(12,18)=6$. A definição abrange qualquer número de termos, por exemplo $mdc(10,15,25,30)=5$. Com esta notação, dizemos que dois números inteiros $a$ e $b$ são primos entre si , se e somente se $mdc(a,b)=1$. Em alguns casos nós denotamos o mdc entre dois números simplesmente por $(a,b)$.
No contexto da teoria dos anéis, um máximo divisor comum é definido de forma análoga: ele é um elemento $m$ que divide $a$ e $b$, e tal que qualquer outro divisor $x$ comum de $a$ e $b$ é um divisor de $m$. Nem sempre existe um máximo divisor comum, e nem sempre ele é único.

## Propriedades

* Se $b>0$ e é um divisor de $a$, então $mdc(a,b)=b$.
* Todo número que for divisor comum de $a$ e $b$ também é um divisor de $mdc(a,b)$;
* Considerando que todos os números são fatores de $0$ (pois $0=0.a$ para qualquer $a$ inteiro) então $mdc(a,0)=|a|$;
* Se $m$ é um inteiro não negativo então $mdc(m.a,m.b)=m.mdc(a,b)$;
* Se $mdc(a,b)=1$ então $mdc(a.b,c)=mdc(a,c).mdc(b,c)$;
* $mdc(a,b)=mdc(b,a)$;
* $mdc(-a,b)=mdc(a,-b)=mdc(-a,-b)=mdc(a,b)$;
* Se $a$ é um inteiro positivo então $mdc(a,a)=a$;
* Calcular o máximo divisor comum é uma operação associativa: $mdc(a,mdc(b,c))=mdc(mdc(a,b),c)=mdc(a,b,c)$;
* Tem-se . $mdc(a,b).mmc(a,b)=ab$, onde $mmc(a,b)$ representa o mínimo múltiplo comum;
* O máximo divisor comum e o mínimo múltiplo comum verificam as seguintes propriedades distributivas:
    $mdc(a,mmc(b,c))=mmc(mdc(a,b),mdc(a,c))$
    $mmc(a,mdc(b,c))=mdc(mmc(a,b),mmc(a,c))$;
    $mdc(ca,cb)=c.mdc(a,b)$;
* Se $p$ é um número primo $mdc(p,a)=p$ ou $mdc(p,a)=1$;
* (Identidade de Bézout) Se $d=mdc(a,b)$, então existem inteiros $x$ e $y$ tais que $d=ax+by$;
* Se $ax+by=1$, então $mdc(a,b)=1$;
* Se $c>0$ e $a$ e $b$ são divisíveis por $c$ então: $mdc({\frac {a}{c}},{\frac {b}{c}})={\frac {1}{c}}mdc(a,b)$;
* Se $a$ e $b$ são inteiros e $a=q*b+r$ onde $q$ e $r$ são inteiros, então: $mdc(a,b)=mdc(b,r)$.

## Determinação do máximo divisor comum

Há duas formas de determinar o máximo divisor comum de dois números:
* A primeira é fatorar os números e a partir daí, pegar os fatores comuns a todos números e deixá-los com o menor expoente que o fator analisado apresentar entre todos os números.
* Exemplo:
    Achemos o $MDC$ de $30$ e $12$. Note que: $30=2\times 3\times 5$ e $12=3\times 2^{2}$, então $(30,12)=2\times 3$ (fatores comuns aos números e o menor expoente do fator. No caso do $2$ tínhamos expoentes $1$ e $2$, mas pegamos o menor, daí ficou só $2$ e não $2$ ao quadrado).
* A segunda consiste em escrever os dois números, separados por um traço vertical; em seguida, compara-se os números, e em baixo do maior deles coloca-se a diferença entre os dois. Agora compara-se o último número que se escreveu, com o que ficou na outra coluna, repetindo-se o processo até que se obtenha igualdade entre os números nas duas colunas, que é o resultado procurado.

### Algoritmo de Euclides

O algoritmo de Euclides consiste em efectuar divisões sucessivas entre dois números até obter resto zero. O máximo divisor comum entre os dois números iniciais é o último resto diferente de zero obtido. Este método não requer qualquer factorização.