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 \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:

• 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