|
|
|
|||||
 |
|||||||
|
|
|
|||||
|
|
|||||||
João Bosco Pitombeira de Carvalho
O algoritmo de Euclides é um tópico muito importante, um dos mais antigos algoritmos matemáticos utilizados até hoje. Em verdade, segundo [2], trata-se do mais antigo algoritmo não trivial ainda em uso. Ele permite achar, de maneira eficiente, o máximo divisor comum de dois inteiros. Além disso, dados dois inteiros positivos a e b, o algoritmo de Euclides permite achar inteiros s e t tais que mdc(a, b) = sa + tb, resultado fundamental para a resolução de equações diofantinas (estudadas, nesta revista, em [3]), mas que raramente sequer é mencionado no ensino médio. O artigo indicado em [1] apresenta um dispositivo prático para calcular tais inteiros s e t, comentando que "a expressão literal explícita dos coeficientes s e t em função dos quocientes (que aparecem no algoritmo de Euclides) não tem aspecto agradável". O objetivo deste artigo é mostrar que essa expressão pode ser obtida através do uso de matrizes 2 × 2. O emprego de matrizes de pequena ordem, por exemplo, 2 × 2 ou 3 × 3, em problemas interessantes deveria ser encorajado no ensino médio. O que deve ser evitado é apresentar as noções da notação e do cálculo matricial e não empregá-los em problemas significativos, o que seria equivalente a apresentar as operações aritméticas e nunca utilizá-las para resolver problemas! Os únicos conhecimentos exigidos são o produto de matrizes e a inversa de uma matriz quadrada, ambos no caso de matrizes 2 × 2. Mostraremos que essas matrizes permitem escrever elegantemente o algoritmo de Euclides e, portanto, achar uma solução s e t da equação sa + tb = mdc(a, b). Mostremos como isso funciona com um exemplo. Sejam a = 36 e b = 14. O algoritmo de Euclides nos fornece
O número 2, o último resto não nulo, é o máximo divisor comum de 36 e 14: 2 = mdc(36, 14). Substituamos a primeira igualdade pela seguinte igualdade entre matrizes:
que nos fornece de novo a igualdade 36 = 14 × 2 + 8, e também a igualdade trivial 14 = 1 × 14 + 0 × 8. Escrevendo todas as igualdades acima na forma matricial, temos
Assim, Ora, a matriz Então, temos Dessa igualdade matricial, vemos que 2 × 36 −5 × 14 = 2, e, portanto, uma solução é (s, t) = (2, −5). Deve ser notado que, a partir dessa solução, podem ser obtidas todas as outras (ver [3]). De um modo geral, aplicando o algoritmo de Euclides a a e b, encontram-se os quocientes q1, q2, ..., qn (despreza-se o último quociente), calcula-se o produto das matrizes
A segunda linha da matriz P−1 fornece a solução procurada. Como o determinante do produto de matrizes é o produto dos determinantes dos fatores e todas as matrizes
Referências bibliográficas [1] CARNEIRO, José Paulo. Dispositivo prático para expressar o mdc de dois números como uma combinação linear deles. RPM 37. |
.
é invertível e sua inversa é 
e a matriz inversa de P, P
têm determinante igual a −1, segue que a matriz P tem determinante 1 ou −1, conforme n seja ímpar ou par, o que facilita o cálculo de P