Máximo divisor comum

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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.[nota 1] 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.

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[editar | editar código-fonte]

  1. Se b > 0 é um divisor de a, então (a, b) = b.[nota 2]
  2. Calcular o máximo divisor comum é uma operação associativa: (a,(b,c))=((a,b),c) = (a,b,c);
  3. Tem-se (a,b). [a,b] = ab, onde [a,b] representa o mínimo múltiplo comum;
  4. 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);
  5. Se d = (a,b), então existem inteiros x e y</math> tais que d = ax + by;
  6. Se ax + by = 1, então (a,b) = 1 (o item anterior garante a reciproca );
  7. Se c > 0 e a e b são divisíveis por c então: (\frac{a}{c},\frac{b}{c}) = \frac{1}{c} (a, b);
  8. 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[editar | editar código-fonte]

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 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.[nota 4]

Algoritmo de Euclides[editar | editar código-fonte]

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[editar | editar código-fonte]

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

Bibliografia[editar | editar código-fonte]

  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.

Ligações externas[editar | editar código-fonte]

Wikilivros
O wikilivro Teoria de números tem uma página intitulada Máximo divisor comum
Wikisource
O Wikisource contém fontes primárias relacionadas com Elementos de Arithmetica
Portal A Wikipédia possui o
Portal da Matemática.
Ícone de esboço Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o.