(U)Ma Temática Elementar por José C. Santos

Artigo José Carlos Santos em (U)Ma Temática Elementar

Artigo de fevereiro de 2014

O máximo divisor comum de dois números naturais m e n é, como o nome indica, o maior número que é divisor tanto de m como de n. Se, por exemplo, os números em questão são 33 e 15, então, como os divisores de 33 são 1, 3, 11 e 33 e como os divisores de 15 são 1, 3, 5 e 15, os únicos números que dividem tanto 33 como 15 são 1 e 3 e o maior destes é 3. O máximo divisor comum de m e n representa-se geralmente por (m,n) e viu-se então que (33,15) = 3.

Calcular o máximo divisor comum de dois números por este processo torna-se rapidamente muito moroso. Existe um método de cálculo, o algoritmo de Euclides, que é muito mais eficiente para encontrar o máximo divisor comum de dois números naturais. Funciona assim: divide-se m por n, obtendo-se um quociente q₁ e um resto r₁, que é necessariamente menor que n. Em seguida recomeça-se com os números n e r₁, obtendo-se um novo quociente q₂ e um novo resto r₂ < r₁. Continua-se assim até se chegar a um resto que seja 0. Então (m,n) é o último resto que se obteve antes desse. Assim, por exemplo se partirmos dos números 132 e 30, os cálculos a efectuar são os seguintes:

Nesta última divisão, o resto é nulo. Logo, (132,30) = 6, que foi o último resto não nulo. É evidente que este cálculo foi muito mais simples do que aquele que teria envolvido determinar todos os divisores de 132 e todos os divisores de 30.

O algoritmo de Euclides surgiu nos Elementos de Euclides. De facto, vem aí duas vezes: no livro VII (numa versão numérica, que é aquela que foi vista acima) e no livro X (numa versão geométrica). Possivelmente, já era conhecido antes do tempo de Euclides, mas não há provas directas disso. Este algoritmo foi redescoberto no Índia e na China e foi divulgado na Europa Ocidental no século XVII. Hoje em dia, em Portugal, faz parte do programa do 2º Ciclo do Ensino Básico.

No entanto, até o algoritmo de Euclides acabou por ser superado. Em 1967, surgiu um novo algoritmo, o algoritmo de Stein, que envolve ligeiramente menos cálculos que o de Euclides. O algoritmo é o seguinte: se m = n, então (m,n) = n. Caso contrário, examina-se a paridade de m e de n e então:

No caso do exemplo anterior, os cálculos seriam os seguintes:

À primeira vista, poderia parecer que o algoritmo de Stein leva a mais cálculos e é mais complexo que o de Euclides, mas isso é porque o algoritmo de Euclides tem uma dificuldade oculta: a divisão. Com efeito, para se poder empregar o algoritmo de Euclides é necessário que se saibam dividir números arbitrariamente grandes, mas as únicas divisões que surgem no algoritmo de Stein são divisões por 2 de números pares.

Como se pode ver por este exemplo, até na Matemática Elementar há avanços recentes.