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 CD. Para 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:
Da igualdade acima e pelo Lema 1, temos que:
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:
Segue que:
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:
Segue que:
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:
Segue que:
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.
Exemplo 1: Calcular o mdc(330, 240). Neste caso, a = 330 e b = 240.
Assim, temos que q1 = 1 e r1 = 90. Inserimos estes valores na grade:
Assim, temos que q2 = 2 e r2 = 60. Inserimos estes valores na grade:
Assim, temos que q3 = 1 e r3 = 30. Inserimos estes valores na grade:
Assim, temos que q4 = 2 e r4 = 0. Inserimos estes valores na grade:
Como obtivemos um resto igual a zero, o mdc procurado é o último rn não nulo:
Exemplo 2: Calcular o mdc(484,1521). Neste caso, fazemos a = 1521 e b = 484.
Assim, temos que q1 = 3 e r1 = 69. Inserimos estes valores na grade:
Assim, temos que q2 = 7 e r2 = 1. Inserimos estes valores na grade:
Assim, temos que q3 = 69 e r3 = 0. Inserimos estes valores na grade:
Como obtivemos um resto igual a zero, o mdc procurado é o último rn não nulo:
Exemplo 3: Calcular o mdc(4074, 582). Neste caso, a = 4086 e b = 582.
Assim, temos que q1 = 7 e r1 = 12. Inserimos estes valores na grade:
Assim, temos que q2 = 48 e r2 = 6. Inserimos estes valores na grade:
Assim, temos que q3 = 2 e r3 = 0. Inserimos estes valores na grade:
Como obtivemos um resto igual a zero, o mdc procurado é o último rn não nulo:
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
e demais esse site, eu não me dei bem na prova e vou estudar mais nessa vez..........
ResponderExcluiramei me ajudou muito sz
ResponderExcluirApenas uma pequena gralha:
ResponderExcluirExemplo 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.
Olá Prinfor.
ExcluirRealmente um deslize. Em breve farei a correção.
Um abraço.
faça o uso do algoritmo de euclides e encontre o mdc de 50,90,300. me ajuda..
ResponderExcluirO algoritmo de Euclides funciona com números negativos?
ResponderExcluir