Pular para o conteúdo principal

Como calcular o Máximo Divisor Comum

O Máximo Divisor Comum é um instrumento importante da Matemática mas, infelizmente, muitos alunos não sabem defini-lo corretamente e utilizam métodos arcaicos e inadequados para calculá-lo.


O que é o MDC?


Vamos retornar ao conceito de Divisibilidade: dizemos que b é um divisor de a se e somente se existir um c tal que a = b . c . Com base nisto, sejam [latex]a, b, d in mathbb{N}[/latex]. Se [latex]d mid a[/latex], pela definição de divisibilidade, sabemos que [latex]d leq a[/latex]. Desta forma, podemos considerar um conjunto denotado por [latex]Div_{mathbb{N}}(a)[/latex] cujos elementos são todos os divisores de a. Tal conjunto é finito e possui um maior elemento, que é igual ao próprio a.

Podemos aplicar este mesmo conceito a outro número Natural b : o conjunto de todos os divisores de b é o conjunto [latex]Div_{mathbb{N}}(b)[/latex], que é finito e possui um maior elemento, que é o próprio b.

Logo, os divisores comuns de a e de b é o conjunto formado pela intersecção dos elementos de [latex]Div_{mathbb{N}}(a)[/latex] e [latex]Div_{mathbb{N}}(b)[/latex] ou, em linguagem matemática:

[latex]Div_{mathbb{N}}(a,b)=Div_{mathbb{N}}(a) cap Div_{mathbb{N}}(b)[/latex]


Este conjunto é não vazio, pois [latex]1 mid a[/latex] e [latex]1 mid b[/latex] e é limitado superiormente por min(a,b). Além disso, pelo corolário do Princípio da Boa Ordenação, ele possui um maior elemento, que é único.

Desta forma, é fácil perceber que o Máximo Divisor Comum de a e de b, sendo a e b não simultaneamente nulos, denotado por MDC(a,b) nada mais é do que o maior elemento do conjunto [latex]Div_{mathbb{N}}(a,b)[/latex].

Assim, fica óbvio que, para calcularmos o MDC de dois números quaisquer, tudo que temos a fazer é escrever o conjunto dos divisores de cada número, fazer a intersecção entre os dois conjuntos e pegar o maior elemento da intersecção. Por exemplo: seja determinar o MDC(2,4). [latex]Div_{mathbb{N}}(2)={1,2}[/latex] e [latex]Div_{mathbb{N}}(4)={1,2,4}[/latex]. Logo, [latex]Div_{mathbb{N}}(2,4)={1,2}[/latex] e, portanto, o MDC(2,4)=2.

Esta é uma tarefa fácil quando os números são pequenos e possuem poucos divisores, como no caso acima, mas torna-se inviável à medida que lidamos com números muito grandes. Neste caso, usamos as propriedades do MDC combinadas ao Algoritmo de Euclides.

Propriedades do MDC


Sejam [latex]a,b in mathbb{N}, a neq 0[/latex]. São válidas as propriedades:

  1. MDC(a,0) = a;

  2. MDC(a,1)= 1;

  3. MDC(a,a)=a;

  4. MDC(a,b)=MDC(b,a);

  5. [latex]a mid b Leftrightarrow MDC(a,b)=a[/latex]


Há ainda outra propriedade a qual diz que, se um número divide o MDC de dois números, então ele também divide estes dois números.

Algoritmo de Euclides para o Cálculo do MDC


Sejam [latex]a,b,n in mathbb{N*}[/latex] tais que [latex]na leq b[/latex]. O algoritmo de Euclides nos permite afirmar que:

MDC(a, b - na) = MDC(a, b)


Para demonstrarmos, basta provar que [latex]Div_{mathbb{N}}(a, b-na)=Div_{mathbb{N}}(a, b)[/latex]. Como estamos falando de conjuntos, temos que provar que o primeiro está contido ou é igual ao segundo e vice-versa:

[latex]subseteq[/latex]: Seja [latex]d in Div_{mathbb{N}}(a, b-na)[/latex]. Então [latex]d mid a[/latex] e [latex]d mid (b-na)[/latex]. Logo, [latex]d mid (b - na) + na = b[/latex] e, logo, [latex]d mid Div_{mathbb{N}}(a, b-na)[/latex].

[latex]supseteq[/latex] Seja [latex]t in Div_{mathbb{N}}(a,b)[/latex], logo [latex]t mid a[/latex] e [latex]t mid b[/latex]. Pelas propriedades da divisibilidade, se [latex]t mid a Rightarrow
t mid na forall n in mathbb{N}[/latex] e, como [latex]na leq b[/latex], temos que [latex]t mid (b - na)[/latex].

Provado isso, vem a pergunta: qual deve ser o valor de n que devemos escolher? Que tal utilizarmos o velho algorítimo da Divisão Euclidiana? Este algoritmo nos assegura que, se [latex]a leq b[/latex], existem e são únicos [latex]q1, r1 in mathbb{N}[/latex] tais que  b = a . q1 + r1, com r1 < a. Logo, pelo Lema de Euclides, podemos escrever:

MDC (a, b) = MDC(a, b-a.q1) = MDC(a,r1)


Assim, o MDC de a e de b é igual ao MDC de a e do resto da divisão de a por b. Combinado com as propriedades acima, fica fácil calcular o MDC de dois números quaisquer: se a não divide b, pega-se o resto da divisão de a por b e reescreve-se o MDC de a e de b como o MDC de a e do resto de a por b. Como este resto é o menor valor, inverte-se: se o resto dividir a, então acabou e o MDC é igual ao resto; Se não dividir, pegamos o resto da divisão de a por r1, chamado r2, e reescrevemos como o MDC de r1 e de r2. Inverte-se. Se r2 dividir r1, acabou, senão, pegamos o resto da divisão de r1 e r2...

Em determinado momento, ou vamos cair em um dos casos das propriedades do MDC ou o resto rn vai dividir o resto r(n+1) e teremos, desta forma, encontrado o MDC.

Comentários

  1. Alguns posts estão com a formatação meio confusa, como este... Impede um tanto a leitura adequada :(

    ResponderExcluir
  2. Me ajudou bastante essa explicação!!!!!!

    ResponderExcluir
  3. Seria interessante ver o que tem de erro nesse artigo, pois fiquei muito afim de lê-lo .
    Isso é alguma coisa que esta errado na sintaxe que esta fazando o cód da linguagem.

    ResponderExcluir

Postar um comentário

Postagens mais visitadas deste blog

Como acessar configurações avançadas no Sagemcom F@st 2704N

NOVO TUTORIAL: GUIA DEFINITIVO DAS CONFIGURAÇÕES AVANÇADAS DO SAGEMCOM F@ST 2704N!
Atualização 23/01/2015: Alguns problemas apontados e descobertos nesse modem:
1. Alguns usuários relatam dificuldade em salvar alterações na configuração ADSL;
2. Não sei como acessar os logs do modem; mesmo habilitando, eles não aparecem;
3. Se você trocar o DNS do modem, ele voltará ao da Oi ao ser reiniciado;
4. Estou enfrentando alguns problemas sérios de lentidão. Não sei se isso é relacionado ao modem ou a algum dispositivo na minha rede interna.
-----
Os modens da marca Sagemcom estão se tornando muito populares no Brasil, não, quiçá, por sua qualidade, mas porque eles são os atuais queridinhos das operadoras: quando você assina um plano ADSL, geralmente a operadora envia um modem wireless para sua casa a fim de que você possa navegar sem precisar ter gastos extras com esse equipamento. É claro que os equipamentos fornecidos pelas operadoras são básicos, mas saciam as necessidades dos usuários comuns - …

O Guia Definitivo das configurações avançadas no Sagemcom F@st 2704N

Há alguns meses, eu contei minha experiência com o Sagemcom F@st 2704N e tenho recebido diversos comentários sobre suas configurações avançadas. Agora que minhas aulas na faculdade estão acabando, resolvi reservar um tempinho para explorar melhor esse modem que, diga-se de passagem, é muito bom.