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

5 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

Por favor, leiam antes de comentar:

▪ Escreva um comentário apenas referente ao tema;

▪ Para demais, utilize o formulário de contato;

▪ Comentários ofensivos ou spans não serão publicados;

▪ Desde o dia 23/07/2013, todos os comentários passaram a ser moderados. Para maiores detalhes, veja a nota de moderação aqui;

▪ É possível escrever fórmulas em $\LaTeX$ nos comentários deste blog graças a um script da Mathjax. Para fórmulas inline ou alinhadas à esquerda, escreva a fórmula entre os símbolos de $\$$; Para fórmulas centralizadas, utilize o símbolo duplo $\$\$$.

Por exemplo, a^2 + b^2 = c^2 entre os símbolos de $\$\$$, gera:
$$a^2+b^2=c^2$$
▪ Para visualizar as fórmulas em $\LaTeX$ antes de publicá-las, acessem este link.

Redes Sociais

Arquivo do Blog

Related Posts Plugin for WordPress, Blogger...