Algoritmo de Euclides (descrição detalhada)

O Algoritmo de Euclides consiste num conjunto de procedimento que permitem de uma forma simples e eficaz de calcular o máximo divisor comum entre dois números naturais, recorrendo ao algoritmo da divisão.

Intuição: Após a aplicação do algoritmo da divisão de dois números naturais, qualquer número que divida o Dividendo ($D$) e o divisor ($d$) também divide o resto ($r$).

Exemplo: Após efectuarmos a divisão de $26$ por $10$ concluímos que $26=10\times 2+6$. Ou seja, neste caso:

• $D=16$
• $d=10$
• $r=6$. 

Como, $1$, $2$, $13$, $26$ dividem $26$ ($D$), e $1$, $2$, $5$, $10$ dividem $10$ ($d$), os divisores comuns a $26$ e $10$ são $1$ e $2$. Mas como facilmente podemos observar, todos os divisores comuns a $26$ e $10$ são também divisores de $6$ ($r$).

Nota: Contudo, o inverso nem sempre é verdade. No exemplo anterior, podemos constatar que $3$ divide $6$ ($r$), e $3$ não divide $10$ ($d$) nem $26$ ($D$).

Mais geralmente, qualquer divisor comum a $D$ e $d$, é divisor comum a $D$, $d$ e $r$, e em particular, é divisor comum apenas de $d$ e $r$.

E é neste último princípio que se baseia o algoritmo de Euclides.

Dados dois números naturais, um maior do que o outro:

1. Aplicamos o algoritmo da divisão considerando $D$ o maior e $d$ o menor para obter $r$.
2. Como os divisores comuns a $D$ e $d$ são os mesmos de $d$ e $r$, voltamos a efectuar o primeiro passo, mas agora aplicando o algoritmo da divisão a $d$ e $r$.
3. Repetimos o passo 2  sucessivamente até obtermos resto 0. Quando isso acontecer, o máximo divisor comum que procuramos é exactamente o último número que consideramos para $d$.

Exemplo: Para ilustrar o que vem sendo referido, calculemos o máximo divisor comum entre $40$ e $30$.

Aplicando o algoritmo da divisão concluímos que $$40=30\times1+10.$$

De seguida, por forma continuarmos o procedimento descrito pelo algoritmo de Euclides, como não obtivemos resto 0, aplicamos ao algoritmo da divisão, mas desta vez, a 30 e 10 concluindo que $$30=10\times 3+\underline{0}.$$  

Como obtivemos resto $0$ o processo está terminado porque, pelo procedimento que utilizamos, os divisores comuns entre $40$ e $30$, são divisores comuns entre $30$ e $10$, que por sua vez são divisores comuns entre $10$ e $0$. Ora, como qualquer número divide $0$, os divisores comuns entre $40$ e $30$ vão ser, na prática, apenas de os divisores de $10$, que são $1$,$2$,$5$,e $10$. O que significa que o máximo divisor comum entre $40$ e $30$ é $10$ (o último número que consideramos para $d$ na aplicação do algoritmo). Ou seja, em linguagem matemática $m.d.c.(40,30)=10$.

Também pode ver uma ilustração geométrica do algoritmo de Euclides nesta publicação.