12/08/2012

O Algoritmo de Euclides para Determinação do MDC

O algoritmo de Euclides é um dos algoritmos mais antigos conhecidos e o método destaca-se por ser simples e eficiente para a determinação do MDC entre números inteiros diferentes de zero.

O método aparece pela primeira vez no Livro VII de sua obra Os Elementos, cerca de 300 a. C. e tem sua origem geométrica, como a determinação da maior medida comum entre dois segmentos de reta.

Proposição II do Livro VII: Sendo dados dois números não primos entre si, achar a maior medida comum deles.

Esta proposição nos diz que dados os segmentos AB e CD representando dois números não primos entre si e diferentes de zero, existe um terceiro segmento EF que cabe um número inteiro de vezes nos primeiros dois segmentos, ou seja, o segmento EF mensura os segmentos AB e CDimagePara uma demonstração mais moderna, vamos considerar o lema abaixo:

Lema 1: Sejam a, b e m inteiros. Temos que mdc(a, 0) = |a| e que mdc(a, b) = mdc(b, a) = mdc(|a|, |b|) = mdc(a – mb, b).

Para calcular o mdc(a, b), tendo em vista o lema acima, vamos supor que a e b são não negativos. Se b = 0 ou a = b, então mdc(a,b) = a e nada temos que calcular. Vamos supor que a ≠ b, como mdc(a, b) = mdc(b, a), podemos supor que a > b > 0.

Pela divisão euclidiana, temos que:

clip_image004

Da igualdade acima e pelo Lema 1, temos que:

clip_image006

Desta forma, podemos ter duas situações:

a1) r2 = 0: neste caso, temos mdc(a, b) = mdc(b, r2) = mdc(b, r2) = b;

b1) r2 ≠ 0: neste caso, efetuamos a divisão euclidiana de b por r, obtendo:

clip_image008

Segue que:

clip_image010

Novamente, duas novas situações podem ocorrer:

a2) r3 = 0: neste caso, (a, b) = (r2, 0) = r2;

b2) r3 ≠ 0: neste caso, efetuamos a divisão euclidiana de r2 por r3, obtendo:

clip_image012

Segue que:

clip_image014

e assim sucessivamente.

Definido r1 = b, existe um valor n tal que rn + 1 = 0 e rn ≠ 0. De fato, se tivéssemos para todo n ≠ o, teríamos uma sequência infinita r1, r2, r3, ... tal que:

clip_image016

Segue que:

clip_image018

Portanto, o último resto não nulo rn deste processo, fornece o valor de mdc(a, b).

Calculamos o mdc(a, b) através do dispositivo prático que decorre do processo acima, que chamamos de Algoritmo de Euclides.

imageExemplo 1: Calcular o mdc(330, 240). Neste caso, a = 330 e b = 240.

imageDividimos a por b:

imageAssim, temos que q1 = 1 e r1 = 90. Inserimos estes valores na grade:

imageAgora, dividimos 240 por 90:

imageAssim, temos que q2 = 2 e r2 = 60. Inserimos estes valores na grade:

imageAgora, dividimos 90 por 60:

imageAssim, temos que q3 = 1 e r3 = 30. Inserimos estes valores na grade:

imageAgora, dividimos 60 por 30:

imageAssim, temos que q4 = 2 e r4 = 0. Inserimos estes valores na grade:

imageComo obtivemos um resto igual a zero, o mdc procurado é o último rn não nulo:

clip_image066

Exemplo 2: Calcular o mdc(484,1521). Neste caso, fazemos a = 1521 e b = 484.

imageDividimos a por b:

image

Assim, temos que q1 = 3 e r1 = 69. Inserimos estes valores na grade:

imageAgora, dividimos 484 por 69:

imageAssim, temos que q2 = 7 e r2 = 1. Inserimos estes valores na grade:

imageAgora, dividimos 69 por 1:

imageAssim, temos que q3 = 69 e r3 = 0. Inserimos estes valores na grade:

imageComo obtivemos um resto igual a zero, o mdc procurado é o último rn não nulo:

clip_image080

Exemplo 3: Calcular o mdc(4074, 582). Neste caso, a = 4086 e b = 582.

image Dividimos a por b:

imageAssim, temos que q1 = 7 e r1 = 12. Inserimos estes valores na grade:

imageAgora, dividimos 582 por 12:

imageAssim, temos que q2 = 48 e r2 = 6. Inserimos estes valores na grade:

imageAgora, dividimos 12 por 6:

imageAssim, temos que q3 = 2 e r3 = 0. Inserimos estes valores na grade:

imageComo obtivemos um resto igual a zero, o mdc procurado é o último rn não nulo:

clip_image094


Referências:

[1] Curso de Álgebra V1 – Abramo Hefez – IMPA
[2] Os Elementos de Euclides – Tradução e Irineu Bicudo


Veja mais:

Um Método para Calcular o MMC e o MDC Entre Dois Números
A Demonstração de Euclides Sobre a Existência de Infinitos Números Primos
Teorema de Pitágoras, Segundo Euclides – A Proposição I-47
O Algoritmo de Euclides e a Representação Binomial do mdc(a, b) no blog Elementos de Teixeira

COMO REFERENCIAR ESSE ARTIGO: Título: O Algoritmo de Euclides para Determinação do MDC. Publicado por Kleber Kilhian em 12/08/2012. URL: . Leia os Termos de uso.


Siga também o blog pelo canal no Telegram.
Achou algum link quebrado? Por favor, entre em contato para reportar o erro.
Para escrever em $\LaTeX$ nos comentários, saiba mais em latex.obaricentrodamente.com.

6 comentários:

  1. e demais esse site, eu não me dei bem na prova e vou estudar mais nessa vez..........

    ResponderExcluir
  2. Apenas uma pequena gralha:
    Exemplo 3: Calcular o mdc(4074, 582). Neste caso, a = 4086 e b = 582.
    Pede para calcular com 4074 e depois resolve com 4086.
    Tudo o resto está muito bem explicado. Parabéns.

    ResponderExcluir
    Respostas
    1. Olá Prinfor.

      Realmente um deslize. Em breve farei a correção.

      Um abraço.

      Excluir
  3. faça o uso do algoritmo de euclides e encontre o mdc de 50,90,300. me ajuda..

    ResponderExcluir
  4. O algoritmo de Euclides funciona com números negativos?

    ResponderExcluir

Whatsapp Button works on Mobile Device only

Pesquise no blog