Teorema de Lamé é o resultado da análise da complexidade do algoritmo de Euclides, feita por Gabriel Lamé. Usando os números de Fibonacci, ele provou que quando se busca o máximo divisor comum de dois inteiros a e b, o algoritmo termina em no máximo 5k passos, onde k é o número de dígitos (decimais) de b.
Enunciado
Demonstração
Sejam
entradas inteiras e positivas no algoritmo de Euclides. Então:
E considerando a sequência de Fibonacci
dada pela lei de recorrência
,
temos que
e
, isto é,
e
. Então, de maneira geral,
para
de modo que tomando
,
.
Considerando a proporção áurea
observamos que
Como
implica
, segue que
de onde
Além disso, utlizando uma calculadora ou outro método de aproximação, conclui-se que
e, portanto,
.
Seja
o número de dígitos de
e a decomposição em potências de 10, temos que
de onde
implica
. Portanto,
. Fica assim demonstrado o Teorema de Lamé.
Bibliografia
- Eric Bach. Algorithmic Number Theory: Eficcient algorithms. Vol. 1. 1996. MIT Press 496 p. 1 ISBN 0262024055
- João Bosco Pitombeira de Carvalho. Olhando mais de cima: Euclides, Fibonacci e Lamé. Revista do Professor de Matemática, São Paulo, n. 24, p.32-40, 2 sem. 1993.
Portal das tecnologias de informação