O algoritmo de Euclides é o avô de todos os algoritmos, porque é o mais antigo algoritmo não trivial que sobreviveu até os dias de hoje.

— Donald Knuth, The Art of Computer Programming, vol. 2 (1969)

Você tem duas varas, uma de 252 cm e outra de 105 cm, e quer encontrar a maior régua que mede as duas exatamente, um número inteiro de vezes. Em linguagem de hoje, quer o máximo divisor comum, $\operatorname{mdc}(252,105)$. Pode-se listar todos os divisores de cada número e procurar o maior em comum, mas com números grandes isso é impraticável. No Livro VII dos Elementos, Euclides ensina um caminho muito mais rápido.

Subtrair o menor do maior

A ideia de Euclides, nas Proposições VII.1 e VII.2, é simples: qualquer régua que meça as duas varas também mede a diferença entre elas. Então, em vez de procurar a medida comum de 252 e 105, podemos procurá-la para 105 e $252-105=147$. E depois para 105 e $147-105=42$. Subtrai-se sempre o menor do maior, até os dois ficarem iguais:

$$(252,105)\to(147,105)\to(42,105)\to(42,63)\to(42,21)\to(21,21).$$

Os dois ficaram iguais a 21. Esse é o máximo divisor comum. Os gregos chamavam o procedimento de antanáiresis, “subtração recíproca”.

A versão com divisões

Subtrair várias vezes o mesmo número é dividir. Juntando as subtrações repetidas numa divisão com resto, o algoritmo fica mais curto:

$$\begin{aligned}252&=2\cdot105+42\\105&=2\cdot42+21\\42&=2\cdot21+0\end{aligned}$$

O último resto diferente de zero é o máximo divisor comum:

$$\boxed{\operatorname{mdc}(252,105)=21.}$$

Por que funciona

Se $a=qb+r$, então:

  • todo número que divide $a$ e $b$ divide também $r=a-qb$;
  • todo número que divide $b$ e $r$ divide também $a=qb+r$.

Os pares $(a,b)$ e $(b,r)$ têm exatamente os mesmos divisores comuns, então $\operatorname{mdc}(a,b)=\operatorname{mdc}(b,r)$. E por que o algoritmo termina? Porque os restos são inteiros positivos que diminuem a cada passo, $42>21>0$, e uma sequência de inteiros positivos não pode diminuir para sempre. Em algum momento o resto é zero, e $\operatorname{mdc}(d,0)=d$.

O algoritmo é rápido. O francês Gabriel Lamé provou em 1844 que o número de divisões nunca passa de cinco vezes o número de algarismos do menor dos dois números. Para números de cem algarismos, bastam no máximo 500 divisões.

A volta pelas contas

As contas também permitem escrever o mdc como combinação dos dois números. Volte de baixo para cima:

$$\begin{aligned}21&=105-2\cdot42\\&=105-2\cdot(252-2\cdot105)\\&=5\cdot105-2\cdot252.\end{aligned}$$

Confira: $525-504=21$. Em geral, para quaisquer $a$ e $b$, existem inteiros $x$ e $y$ com $ax+by=\operatorname{mdc}(a,b)$. É a identidade de Bézout, e o procedimento de voltar pelas contas se chama algoritmo de Euclides estendido.

Exercício: encontre o máximo divisor comum de 391 e 299.

$391=1\cdot299+92$, $299=3\cdot92+23$ e $92=4\cdot23+0$. O mdc é 23. De fato, $391=17\cdot23$ e $299=13\cdot23$.

Exercício: simplifique a fração 252/105 e escreva 1 como combinação de 12 e 5.

Dividindo os dois termos pelo mdc, 21: $\frac{252}{105}=\frac{12}5$. Agora $12=2\cdot5+2$ e $5=2\cdot2+1$. Voltando: $1=5-2\cdot2=5-2\cdot(12-2\cdot5)=5\cdot5-2\cdot12$. Confira: $25-24=1$.

Fontes: Elementos, Proposições VII.1 e VII.2, edição de D. E. Joyce · Donald E. Knuth, The Art of Computer Programming, vol. 2, seção 4.5.2 · Gabriel Lamé, “Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur”, Comptes rendus 19 (1844).

Todos os tópicos de Euclides · ← A álgebra feita com quadrados e retângulos · Os números primos não acabam →

Créditos das imagens.