Máximo divisor comum

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

1. Se $b>0$ e é um divisor de $a$, então $mdc(a,b)=b$.
2. Todo número que for divisor comum de $a$ e $b$ também é um divisor de $mdc(a,b)$;
3. 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|$;
4. Se $m$ é um inteiro não negativo então $mdc(m.a,m.b)=m.mdc(a,b)$;
5. Se $mdc(a,b)=1$ então $mdc(a.b,c)=mdc(a,c).mdc(b,c)$;
6. $mdc(a,b)=mdc(b,a)$;
7. $mdc(-a,b)=mdc(a,-b)=mdc(-a,-b)=mdc(a,b)$;
8. Se $a$ é um inteiro positivo então $mdc(a,a)=a$;
9. Calcular o máximo divisor comum é uma operação associativa: $mdc(a,mdc(b,c))=mdc(mdc(a,b),c)=mdc(a,b,c)$;
10. Tem-se . $mdc(a,b).mmc(a,b)=ab$, onde $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:

    $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)$;

12. Se $p$ é um número primo $mdc(p,a)=p$ ou $mdc(p,a)=1$;
13. (Identidade de Bézout) Se $d=mdc(a,b)$, então existem inteiros $x$ e $y$ tais que $d=ax+by$;
14. Se $ax+by=1$, então $mdc(a,b)=1$;
15. 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)$;
16. 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:

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

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.

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
• Números primos entre si
• Algoritmo de Euclides
• Algoritmo de Euclides estendido

Referências

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

Bibliografia

1. Jaime Evaristo, Introdução à Álgebra com aplicações à Ciência da Computação, UFAL, ISBN 8-571-77058-1.
2. Jaime Evaristo, Introdução à álgebra abstrata, UFAL, 1999 ISBN 8-571-77125-1.
3. Mary Jane Sterling, Álgebra I Para Leigos, Alta Books Editora, 2013 ISBN 8-576-08256-X
4. Taiane Vieira, Roberto Giugliani, Matemática Discreta - 3ed: Coleção Schaum, Bookman Editora, 2013 ISBN 8-565-83778-5
5. Slavin, Keith R. (2008). "Q-Binomials and the Greatest Common Divisor" Ver Artigo. Integers Electronic Journal of Combinatorial Number Theory (University of West Georgia, Charles University in Prague) 8: A5.
6. Schramm, Wolfgang (2008). "The Fourier transform of functions of the greatest common divisor" Ver Artigo. Integers Electronic Journal of Combinatorial Number Theory (University of West Georgia, Charles University in Prague) 8: A50.
7. Knuth, Donald E.; Graham, R. L.; Patashnik, O. (March 1994). Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley. ISBN 0-201-55802-5. (em inglês)
8. Nymann, J. E. (1972). "On the probability that k positive integers are relatively prime". Journal of Number Theory 4 (5): 469–473. doi:10.1016/0022-314X(72)90038-8. (em inglês)
9. Chidambaraswamy, J.; Sitarmachandrarao, R. (1987). "On the probability that the values of m polynomials have a given g.c.d.". Journal of Number Theory 26 (3): 237–245. doi:10.1016/0022-314X(87)90081-3 (em inglês).
10. Chor, B.; Goldreich, O. (1990). "An improved parallel algorithm for integer GCD". Algorithmica 5 (1–4): 1–10. doi:10.1007/BF01840374.
11. Andreescu, T; Feng, Z., 104 Number Theory Problems from Training of the USA IMO Team, Australian Mathematics Trust

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)