O algoritmo de Euclides

Este algoritmo pode ser implementado através de um dos códigos seguintes:

Para provar que este algoritmo funciona, observamos os factos seguintes:

1. Se d é um divisor comum dos inteiros positivos $a$ e $b$, com $a$ > $b$, então d é também um divisor comum dos inteiros positivos $b$ e $a$ - $b$.
2. O algoritmo produz sucessivamente inteiros positivos cada vez mais pequenos, e, portanto, termina com um numero inteiro ≥ 1.

O algoritmo de Euclides, tal como ele o enunciou nos Elementos, pode não ser muito eficiente. Por exemplo, se tentarmos encontrar MDC(101, 10¹⁰⁰ + 1) por subtração repetida, teremos que subtrair 101 de 10¹⁰⁰ + 1 quase 1098 vezes, o que não é, evidentemente, muito rápido.

No entanto, subtrair repetidamente $b$ de $a$, até que a diferença, $r$ = $a$ - $b$, seja menor do que $b$, é o mesmo que dividir ($a$ por $b$ e obter o resto $r$, como se ilustra na figura seguinte.

Isto dá origem ao seguinte algoritmo de divisão Euclideana: Dados dois números naturais $a$ e $b$, com $a$ > $b$ e $b$ ≠ 0, existem números naturais $q$ e $r$, “quociente” e “resto”, tais que:

A propriedade de divisão é visualmente óbvia, como se ilustra na figura acima, porque qualquer número natural a deve estar entre múltiplos sucessivos de $b$ - na figura, entre $qb$ e ($q + 1$)b. Em particular, a sua distância $r$, ao múltiplo menor, $qb$, e menor do que a distância $b$ entre eles.

A vantagem do algoritmo de divisão euclideana, é que, em geral, é muito mais rápido do que a subtração repetida. Cada divisão de um número natural $b$ por um número $a < b$, com $k$ algarismos, “cancela” cerca de $k$ algarismos em $b$, e conduz a um resto $r$ com no máximo $k$ algarismos. Portanto, o número de divisões e no máximo igual ao número total de dígitos dos números com que começámos. Resumindo

Por exemplo

já que 1345 = 24 × 56 + 1. Em geral, podemos calcular M = MDC($a$, $b$) através do código seguinte:

Recursos relacionados disponíveis na Casa das Ciências:

1. og@r ao m.d.c. e ao m.m.c. com o GeoGebra.