Esse texto é uma continuação da parte 1 e tem como objetivo efetivamente apresentar e ensinar o leitor a calcular o Algoritmo de Euclides para mdc. Essa algoritmo é bastante poderoso, pois, pode ajudar a calcular o MDC entre dois números em situações em que não é fácil encontrar seus divisores, e também é utilizado para resolver vários problemas matemáticos.
Introdução
Antes de partir para o algoritmo em si vamos relembrar o Teorema que serve como base para ele.
Teorema. Dados dois números naturais, a e b, então o mdc(a, b)=mdc(a, b-a).
Um corolário bastante simples desse teorema, que não passa de uma versão re-escrita dele é que:
Corolário 1. Dados dois números naturais, a e b, então o mdc(a, b)=mdc(a, b-a·c), para todo número c inteiro.
Daí um caso particular desse Corolário 1 é bastante usado para facilitar a aplicação do Teorema:
Corolário 2. Dados dois números naturais, a e b, então o mdc(a, b)=mdc(a, r), onde r é o resto da divisão de b por a.
O Algoritmo de Euclides para mdc
Para o algoritmo em si vamos até um exemplo prático.
Vamos calcular o MDC de 160 e 372.
Primeiro, vamos colocá-los em ordem decrescente:
1) mdc(372, 160)
Daí, vamos calcular o resto da divisão de 372 por 160, caso o leitor tenha dificuldade pode consultar o seguinte texto:
Logo, como o resto 372 por 160 é 52, então pelo Teorema visto:
2) mdc(372, 160) = mdc(160, 52)
Podemos repetir esse processo e achar o resto de 160 por 52, que é 4. Logo:
3) mdc(372, 160) = mdc(160, 52) = mdc(52, 4).
Mas, fazendo esse processo novamente vamos notar que 52 é divisível por 4. Logo 4 é mdc entre 52 e 4, e, portanto:
4) mdc(372, 160) = mdc(160, 52) = mdc(52, 4) = 4.
Prontinho, logo após esses passos achamos o MDC que procuramos sem ter que saber como decompor esses números em primos.
Esse procedimento que fizemos é o chamado Algoritmo de Euclides para mdc. Portanto o algoritmo é repetir a divisão entre os dois números que queremos calcular o MDC achando seu resto e encontrando um MDC mais simples, até que algum dos números divida o outro, e quando isso acontece achamos o MDC.
Exemplo.
Veja mais um exemplo:
mdc(294, 119)
Como 294=2·119+56
mdc(294, 119) = mdc(119, 56)
Como 119=2·56+7
mdc(294, 119) = mdc(119, 56) = mdc(56, 7)
E, como 56=8·7
mdc(294, 119) = mdc(119, 56) = mdc(56, 7) = 8
Próximos textos.
Nos próximos textos vamos ver exemplos aplicados a números, exercícios mais elaborados e uma aplicação em linguagem C dele.
