Teorema de Lamé
Origem: Wikipédia, a enciclopédia livre.
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.
O Teorema foi originalmente enunciado na seguinte forma:
O número de passos de divisão no algoritmo de Euclides com entradas 
e 
é limitado superiormente por 
vezes a quantidade de dígitos decimais em 
.
[editar] Referências
Eric Bach. Algorithm Number Theory: Eficcient algorithms. Vol. 1. 1996. MIT Press 496 p. 1 ISBN 0262024055
