Máximo divisor comum

O máximo divisor comum (abreviadamente, 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 somente 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]\land [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..

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

Ver artigo principal: 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 (1914). Elementos de Arithmetica 15 ed. Rio de Janeiro: Francisco Alves 

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)»