(U)Ma Temática Elementar por José C. Santos
Eixos de Opinião fevereiro de 2014
Publicado a 21 de Fevereiro de 2014

 


A Matemática elementar tem muito que se lhe diga. Embora nos seja familiar, é sempre possível encará-la de um ponto de vista novo ou inesperado.              

José Carlos Santos - Departamento de Matemática da FCUP     


Dia 21 de cada mês

                 


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

Artigo de fevereiro de 2014

Clube de Matemática SPM

Facebook Clube SPM

Título: O algoritmo de Euclides


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 q1 e um resto r1, que é necessariamente menor que n. Em seguida recomeça-se com os números n e r1, obtendo-se um novo quociente q2 e um novo resto r2 < r1. 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:

132 = 30×4+12

30   = 12×2+6

12   = 6×2


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:


 se m e n forem pares, (m,n) = 2× (m/2,n/2);

 se m for par e n for ímpar, (m,n) = (m/2,n);

 o caso em que m é ímpar e n é par é análogo;

 se m e n forem ímpares e m > n, (m,n) = ((m – n)/2,n);

 o caso em que m e n são ímpares e m < n é análogo.


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

(132,30)   = 2×(66,15)

 

                         = 2×(33,15)

 

                         = 2×(9,15)

 

                         = 2×(9,3)

 

                         = 2×(3,3)

 

                                   = 6


À 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.