Máximo divisor comum

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
NoFonti.svg
Este artigo ou se(c)ção cita uma ou mais fontes fiáveis e independentes, mas ela(s) não cobre(m) todo o texto (desde Maio de 2011).
Por favor, melhore este artigo providenciando mais fontes fiáveis e independentes e inserindo-as em notas de rodapé ou no corpo do texto, conforme o livro de estilo.
Encontre fontes: Googlenotícias, livros, acadêmicoScirusBing. Veja como referenciar e citar as fontes.

O máximo divisor comum ou MDC (mdc) entre dois ou mais números inteiros é o maior número inteiro que é fator de tais números.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.

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

  • Se b > 0 é um divisor de a, então (a, b) = b.2
  • 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[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.3 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.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.

Ver também[editar | editar código-fonte]

Notas[editar | editar código-fonte]

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

Referências[editar | editar código-fonte]

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

Wikilivros
O wikilivro Teoria de números tem uma página intitulada Máximo divisor comum