miniaturadaimagem|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.Vianna (1914), p. 71. Por exemplo, os divisores comuns de e são e , logo . A definição abrange qualquer número de termos, por exemplo . Com esta notação, dizemos que dois números inteiros e são primos entre si , se e somente se . Em alguns casos nós denotamos o mdc entre dois números simplesmente por .

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

Propriedades

Se e é um divisor de , então . Todo número que for divisor comum de e também é um divisor de ; Considerando que todos os números são fatores de (pois para qualquer inteiro) então ; Se é um inteiro não negativo então ; Se então ;

Se é um inteiro positivo então ; Calcular o máximo divisor comum é uma operação associativa: ; Tem-se . , onde representa o mínimo múltiplo comum; O máximo divisor comum e o mínimo múltiplo comum verificam as seguintes propriedades distributivas:

Se é um número primo ou ; (Identidade de Bézout) Se , então existem inteiros e tais que ; Se , então ; Se e e são divisíveis por então: ; Se e são inteiros e onde e são inteiros, então: .

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 de e . Note que: e , então (fatores comuns aos números e o menor expoente do fator. No caso do tínhamos expoentes e , mas pegamos o menor, daí ficou só e não 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.

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

Bibliografia

Jaime Evaristo, Introdução à Álgebra com aplicações à Ciência da Computação, UFAL, ISBN 8-571-77058-1. Jaime Evaristo, Introdução à álgebra abstrata, UFAL, 1999 ISBN 8-571-77125-1. Mary Jane Sterling, Álgebra I Para Leigos, Alta Books Editora, 2013 ISBN 8-576-08256-X Taiane Vieira, Roberto Giugliani, Matemática Discreta - 3ed: Coleção Schaum, Bookman Editora, 2013 ISBN 8-565-83778-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. 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. Knuth, Donald E.; Graham, R. L.; Patashnik, O. (March 1994). Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley. ISBN 0-201-55802-5. Nymann, J. E. (1972). "On the probability that k positive integers are relatively prime". Journal of Number Theory 4 (5): 469–473. . 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. . Chor, B.; Goldreich, O. (1990). "An improved parallel algorithm for integer GCD". Algorithmica 5 (1–4): 1–10. . 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)

Categoria:Teoria dos números