Máximo divisor comum

O máximo divisor comum ou MDC (mdc) entre dois ou mais números inteiros é o maior número inteiro 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. O máximo divisor comum também pode ser representado só com parênteses. Com esta notação, dizemos que dois números inteiros a e b são primos entre si se e só se mdc(a, b)=1.

Esta operação é tipicamente utilizada para reduzir equações a outras equivalentes:

Seja m o máximo divisor comum entre a e b, e a' e b' o resultado da divisão de ambos por m, respectivamente.

Então, o seguinte é verdadeiro:

1. $[i] a=b \iff 1\cdot a=b\ \iff \frac{m}{m}\cdot a=b \iff m\cdot \frac{a}{m}=b \iff \frac{a}{m}\cdot m=b \iff \frac{a}{m} = \frac{b}{m}$
2. $[ii] \frac{a}{m}=a'$
3. $[iii] \frac{b}{m}=b'$
4. $[i]\rightarrow([ii]\and[iii]) \therefore a=b \iff \frac{a}{m} = \frac{b}{m} \iff 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 é um divisor de a, então (a, b) = b.
• O máximo divisor comum ou MDC é uma operação associativa: (a,(b,c))=((a,b),c)=(a,b,c);
• Tem-se (a,b). [a,b]=ab, onde [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:

  (a, [b,c])=[(a,b),(a,c)]

  [a,(b,c)]=([a,b], [a,c]);

• (ca,cb)=c(a,b);
• Se d=(a,b), então existem inteiros x e y tais que d=ax+by;
• Se ax+by=1, então (a,b)=1;
• Se c>0 e a e b são divisiveis por c então: (a/c,b/c) = 1/c*(a,b);
• Se a e b são inteiros e a=q*b + r onde q e r são inteiros, então:

(a,b)=(b,r).

Determinação do máximo divisor comum

Há duas formas de determinar o máximo divisor comum de dois números:

1. 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).

2. 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.

Ver também

• Fatorização
• Número primo
• Algoritmo de Euclides
• Mínimo múltiplo comum

Referências

• Vianna, João José Luiz. Elementos de Arithmetica. 15 ed. Rio de Janeiro: Francisco Alves, 1914.

Ligações externas

• Calculadora on-line do máximo divisor comum de dois ou mais números inteiros.
• A calculadora on-line GCD. (4 métodos)