ATRACTOR

Vamos determinar o máximo divisor comum de dois inteiros positivos \(a\) e \(b\).

Começamos por dividir \(a\) por \(b\): obtemos um quociente \(q_{1}\) e um resto \(r_{1}\) (e o resto é menor do que \(b\)):\[a=bq_{1}+r_{1}.\]

Qualquer divisor comum de \(a\) e \(b\) também é divisor comum de \(a\) e \(bq_{1}\), portanto também é divisor de \(r_{1}\); então é divisor comum de \(b\) e \(r_{1}\).

Mas qualquer divisor comum de \(b\) e \(r_{1}\) também é divisor comum de \(bq_{1}\) e \(r_{1}\), portanto também é divisor de \(a\); então é divisor comum de \(a\) e \(b\).

Conclusão: os divisores comuns de \(a\) e \(b\) são os divisores comuns de \(b\) e \(r_{1}\), portanto, para achar o máximo divisor comum de \(a\) e \(b\) basta encontrarmos o máximo divisor comum de \(b\) e \(r_{1}\).

Vamos agora repetir o processo, dividindo \(b\) por \(r_{1}\): obtemos um quociente \(q_{2}\) e um resto \(r_{2}\) (e \(r_{2}\) é menor do que \(r_{1}\)):\[b=r_{1}q_{2}+r_{2}.\]

Usando o mesmo argumento, vemos que os divisores comuns de \(b\) e \(r_{1}\) são os divisores comuns de \(r_{1}\) e \(r_{2}\).

Continuando assim, como cada resto é menor do que o anterior, acabaremos por ter um resto igual a \(0\); por exemplo, se o último resto diferente de zero fôr \(r_{4}\), temos \[\begin{array}{ccl} a & = & bq_{1}+r_{1}\\ b & = & r_{1}q_{2}+r_{2}\\ r_{1} & = & r_{2}q_{3}+r_{3}\\ r_{2} & = & r_{3}q_{4}+r_{4}\\ r_{3} & = & r_{4}q_{5} \end{array}\]

O máximo divisor comum de \(a\) e \(b\) é o máximo divisor comum de \(b\) e \(r_{1}\), que é o máximo divisor comum de \(r_{1}\) e \(r_{2}\), que, por sua vez, é o máximo divisor comum de \(r_{2}\) e \(r_{3}\), que é, ainda, o máximo divisor comum de \(r_{3}\) e \(r_{4}\). Como \(r_{3}\) é múltiplo de \(r_{4}\), o máximo divisor comum de \(r_{3}\) e \(r_{4}\) é \(r_{4}\).

Da mesma maneira se vê que o máximo divisor comum de \(a\) e \(b\) é sempre o último resto diferente de \(0\).

A execução do algoritmo pode ser "seguida" no diagrama de um applet (diagrama do algoritmo). Nesse diagrama, o resto da divisão de \(a\) por \(b\) obtem-se subtraindo \(b\) de \(a\) as vezes que forem precisas (i.e., até chegar a um número menor que \(b\)).

Outro applet permite ver uma interpretação geométrica do algoritmo de Euclides. A ideia é que num rectângulo de lados \(a\) e \(b\) \((<a)\), se formos "tirando" quadrados de lado \(b\), acaba por ficar um rectângulo com um lado medindo \(b\) e em que a medida de outro é o resto da divisão de \(a\) por \(b\).

O algoritmo será tanto mais eficiente quanto menor for o número de divisões necessárias para encontrar o máximo divisor comum. Se quiser ver alguns exemplos e descobrir quais os piores casos, clique aqui.

A partir do conhecimento desses piores casos, é possível concluir que o número de divisões necessárias ao algoritmo para encontrar o máximo divisor comum entre dois naturais não excede cinco vezes o número de dígitos do menor deles. Para perceber como, clique aqui.