O Algoritmo de Euclides para mdc: Parte 2

Entre para nossa lista e receba conteúdos exclusivos!

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.

Outros Artigos

Entre para nossa lista e receba conteúdos exclusivos!

contato@meuguru.com

CNPJ 42.269.770/0001-84

Nos siga nas redes!