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.^{[nota 1]} Por exemplo, os divisores comuns de ${\displaystyle 12}$ e ${\displaystyle 18}$ são ${\displaystyle 1,2,3}$ e ${\displaystyle 6}$, logo ${\displaystyle mdc(12,18)=6}$. A definição abrange qualquer número de termos, por exemplo ${\displaystyle mdc(10,15,25,30)=5}$. Com esta notação, dizemos que dois números inteiros ${\displaystyle a}$ e ${\displaystyle b}$ são primos entre si , se e somente se ${\displaystyle mdc(a,b)=1}$. Em alguns casos nós denotamos o mdc entre dois números simplesmente por ${\displaystyle (a,b)}$.

Máximo Divisor Comum

No contexto da teoria dos anéis, um máximo divisor comum é definido de forma análoga: ele é um elemento ${\displaystyle m}$ que divide ${\displaystyle a}$ e ${\displaystyle b}$, e tal que qualquer outro divisor ${\displaystyle x}$ comum de ${\displaystyle a}$ e ${\displaystyle b}$ é um divisor de ${\displaystyle m}$. Nem sempre existe um máximo divisor comum, e nem sempre ele é único.

Propriedades

1. Se ${\displaystyle b>0}$ e é um divisor de ${\displaystyle a}$, então ${\displaystyle mdc(a,b)=b}$.^{[nota 2]}
2. Todo número que for divisor comum de ${\displaystyle a}$ e ${\displaystyle b}$ também é um divisor de ${\displaystyle mdc(a,b)}$;
3. Considerando que todos os números são fatores de ${\displaystyle 0}$ (pois ${\displaystyle 0=0.a}$ para qualquer ${\displaystyle a}$ inteiro) então ${\displaystyle mdc(a,0)=|a|}$;
4. Se ${\displaystyle m}$ é um inteiro não negativo então ${\displaystyle mdc(m.a,m.b)=m.mdc(a,b)}$;
5. Se ${\displaystyle mdc(a,b)=1}$ então ${\displaystyle mdc(a.b,c)=mdc(a,c).mdc(b,c)}$;
6. ${\displaystyle mdc(a,b)=mdc(b,a)}$;
7. ${\displaystyle mdc(-a,b)=mdc(a,-b)=mdc(-a,-b)=mdc(a,b)}$;
8. Se ${\displaystyle a}$ é um inteiro positivo então ${\displaystyle mdc(a,a)=a}$;
9. Calcular o máximo divisor comum é uma operação associativa: ${\displaystyle mdc(a,mdc(b,c))=mdc(mdc(a,b),c)=mdc(a,b,c)}$;
10. Tem-se . ${\displaystyle mdc(a,b).mmc(a,b)=ab}$, onde ${\displaystyle mmc(a,b)}$ representa o mínimo múltiplo comum;
11. O máximo divisor comum e o mínimo múltiplo comum verificam as seguintes propriedades distributivas:

    ${\displaystyle mdc(a,mmc(b,c))=mmc(mdc(a,b),mdc(a,c))}$

    ${\displaystyle mmc(a,mdc(b,c))=mdc(mmc(a,b),mmc(a,c))}$;

    ${\displaystyle mdc(ca,cb)=c.mdc(a,b)}$;

12. Se ${\displaystyle p}$ é um número primo ${\displaystyle mdc(p,a)=p}$ ou ${\displaystyle mdc(p,a)=1}$;
13. (Identidade de Bézout) Se ${\displaystyle d=mdc(a,b)}$, então existem inteiros ${\displaystyle x}$ e ${\displaystyle y}$ tais que ${\displaystyle d=ax+by}$;
14. Se ${\displaystyle ax+by=1}$, então ${\displaystyle mdc(a,b)=1}$;
15. Se ${\displaystyle c>0}$ e ${\displaystyle a}$ e ${\displaystyle b}$ são divisíveis por ${\displaystyle c}$ então: ${\displaystyle mdc({\frac {a}{c}},{\frac {b}{c}})={\frac {1}{c}}mdc(a,b)}$;
16. Se ${\displaystyle a}$ e ${\displaystyle b}$ são inteiros e ${\displaystyle a=q*b+r}$ onde ${\displaystyle q}$ e ${\displaystyle r}$ são inteiros, então: ${\displaystyle 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:

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.^{[nota 3]}
2. Exemplo:

   Achemos o ${\displaystyle MDC}$ de ${\displaystyle 30}$ e ${\displaystyle 12}$. Note que: ${\displaystyle 30=2\times 3\times 5}$ e ${\displaystyle 12=3\times 2^{2}}$, então ${\displaystyle (30,12)=2\times 3}$ (fatores comuns aos números e o menor expoente do fator. No caso do ${\displaystyle 2}$ tínhamos expoentes ${\displaystyle 1}$ e ${\displaystyle 2}$, mas pegamos o menor, daí ficou só ${\displaystyle 2}$ e não ${\displaystyle 2}$ ao quadrado).

3. 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.^{[nota 4]}

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.^{[nota 5]}

Ver também

• Fatorização
• Número primo
• Algoritmo de Euclides
• Mínimo múltiplo comum
• Números primos entre si
• Algoritmo de Euclides
• Algoritmo de Euclides estendido

Notas

1. Vianna (1914), p. 71.
2. Vianna (1914), p. 72.
3. Vianna (1914), p. 77.
4. Vianna (1914), p. 73.
5. Vianna (1914), p. 72-74.

Referências

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