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

$CD$ .

o-algoritmo-de-euclides-para-detetminacao-do-mdc

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 \neq b$ , como

$mdc(a, b) = mdc(b, a)$ , podemos supor que

$a > b > 0$ .

Pela divisão euclidiana, temos que:

$a=b \cdot q_1 + r_2$

onde

$0 \leq r_2 < b$ .

Da igualdade acima e pelo Lema 1, temos que:

$mdc(a,b) = mdc(a-b\cdot q_1, b) = mdc(r_2,b)=mdc(b,r_2)$

Desta forma, podemos ter duas situações:

$a_1)$

$r_2=0$ . Neste caso, temos:

$mdc(a, b) = mdc(b, r2) = mdc(b, r2) = b$

$b_1)$

$r_2 \neq 0$ . Neste caso, efetuamos a divisão euclidiana de

$b$ por

$r$ , obtendo:

$b = r_2 \cdot q_2 + r_3$
onde

$0\leq r_3 <r_2$ $

Segue que:

$mdc(a,b) = mdc(b,r_2) = mdc(r_2,r_3)$

Novamente, duas novas situações podem ocorrer:

$a_2)$

$r_3=0$ . Neste caso, temos:

$(a, b) = (r_2, 0) = r_2$

$b_2)$

$r_3 \neq0$ . Neste caso, efetuamos a divisão euclidiana de

$r_2$ por

$r_3$ , obtendo:

$r_2 = r_3 \cdot q_ 3+r_4$

onde

$0 \leq r_4 < r_3$ .

Segue que:

$mdc(a,b) = mdc(b,r_2) = mdc(r_2,r_3) = mdc(r_3,r_4)$

e assim sucessivamente.

Definido

$r_1=b$ , existe um valor

$n$ tal que

$r_{n+1} = 0$ e

$r_n \neq 0$ . De fato, se tivéssemos para todo

$n\neq 0$ , teríamos uma sequência infinita

$r_1,r_2,r_3,\cdots$ , tal que:

$r_1 > r_2 > r_3> \cdots > 0$

Segue que:

$mdc(a,b)=mdc(b,r_2)=\cdots = mdc(r_n,r_{n+1}) = mdc(r_n,0)=r_n$

Portanto, o último resto não nulo

$r_n$ 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$ .

Dividimos

$a$ por

$b$ :

Assim, temos que

$q_1=1$ e

$r_1=90$ . Inserimos estes valores na grade:

Agora, dividimos

$240$ por

$90$ :

Assim, temos que

$q_2=2$ e

$r_2=60$ . Inserimos estes valores na grade:

Agora, dividimos $90$ por $60$ :

Assim, temos que

$q_3=1$ e

$r_3=30$ . Inserimos estes valores na grade:

Agora, dividimos

$60$ por

$30$ :

Assim, temos que

$q_4=2$ e

$r_4=0$ . Inserimos estes valores na grade:

Como obtivemos um resto igual a zero, o

$mdc$ procurado é o último

$r_n$ não nulo:

$mdc(330,240) = 30$

Exemplo 2:

Calcular o

$mdc(484,1521)$ . Neste caso, fazemos

$a = 1521$ e

$b = 484$ .

Dividimos

$a$ por

$b$ :

Assim, temos que

$q_1=3$ e

$r_1=69$ . Inserimos estes valores na grade:

Agora, dividimos

$484$ por

$69$ :

Assim, temos que

$q_2=7$ e

$r_2=1$ . Inserimos estes valores na grade:

Agora, dividimos

$69$ por

$1$ :

Assim, temos que

$q_3=69$ e

$r_3=0$ . Inserimos estes valores na grade:

Como obtivemos um resto igual a zero, o

$mdc$ procurado é o último

$r_n$ não nulo:

$mdc(484,1521)=1$

Exemplo 3:

Calcular o

$mdc(4074, 582)$ . Neste caso,

$a = 4086$ e

$b = 582$ .

Dividimos

$a$ por

$b$ :

Assim, temos que

$q_1=7$ e

$r_1=12$ . Inserimos estes valores na grade:

Agora, dividimos

$582$ por

$12$ :

Assim, temos que

$q_2 = 48$ e

$r_2 = 6$ . Inserimos estes valores na grade:

Agora, dividimos

$12$ por

$6$ :

Assim, temos que

$q_3 = 2$ e

$r_3 = 0$ . Inserimos estes valores na grade:

Como obtivemos um resto igual a zero, o

$mdc$ procurado é o último

$r_n$ não nulo:

$mdc(4086, 582)=6$

Referências:

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

Veja mais:

6 comentários:

Anônimo23/9/13 17:22
e demais esse site, eu não me dei bem na prova e vou estudar mais nessa vez..........
ResponderExcluir
Respostas
carolina29/5/14 20:32
amei me ajudou muito sz
ResponderExcluir
Respostas
prinfor27/6/14 19:39
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
Anônimo24/6/16 14:45
faça o uso do algoritmo de euclides e encontre o mdc de 50,90,300. me ajuda..
ResponderExcluir
Respostas
Anônimo13/3/18 02:12
O algoritmo de Euclides funciona com números negativos?
ResponderExcluir
Respostas

12/08/2012

O Algoritmo de Euclides para determinação do MDC