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.  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) r₂ = 0: neste caso, temos mdc(a, b) = mdc(b, r₂) = mdc(b, r₂) = b;

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

Segue que:

Novamente, duas novas situações podem ocorrer:

a2) r₃ = 0: neste caso, (a, b) = (r₂, 0) = r₂;

b2) r₃ ≠ 0: neste caso, efetuamos a divisão euclidiana de r₂ por r₃, obtendo:

Segue que:

e assim sucessivamente.

Definido r₁ = b, existe um valor n tal que r_{n + 1} = 0 e r_n ≠ 0. De fato, se tivéssemos para todo n ≠ o, teríamos uma sequência infinita r₁, r_2, r₃, ... tal que:

Segue que:

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 e r₁ = 90. Inserimos estes valores na grade:

Agora, dividimos 240 por 90:

Assim, temos que q₂ = 2 e r₂ = 60. Inserimos estes valores na grade:

Agora, dividimos 90 por 60:

Assim, temos que q₃ = 1 e r₃ = 30. Inserimos estes valores na grade:

Agora, dividimos 60 por 30:

Assim, temos que q₄ = 2 e r₄ = 0. Inserimos estes valores na grade:

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

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

Dividimos a por b:

Assim, temos que q₁ = 3 e r₁ = 69. Inserimos estes valores na grade:

Agora, dividimos 484 por 69:

Assim, temos que q₂ = 7 e r₂ = 1. Inserimos estes valores na grade:

Agora, dividimos 69 por 1:

Assim, temos que q₃ = 69 e r₃ = 0. Inserimos estes valores na grade:

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

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

Dividimos a por b:

Assim, temos que q₁ = 7 e r₁ = 12. Inserimos estes valores na grade:

Agora, dividimos 582 por 12:

Assim, temos que q₂ = 48 e r₂ = 6. Inserimos estes valores na grade:

Agora, dividimos 12 por 6:

Assim, temos que q₃ = 2 e r₃ = 0. Inserimos estes valores na grade:

Como obtivemos um resto igual a zero, o mdc procurado é o último r_n 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

---