Teorema de Lamé

La Teorema de Lamé és un resultat de Gabriel Lamé, publicat en 1844, que tracta sobre la complexitat del Algoritme de Euclides. Esta teorema afirma que quan es busca el màxim comú divisor (MCD) de dos sancers $a$ i $b$, en $a>b$, l'algoritme de Euclides termina en com a molt $5k$ passos (divisions); a on $k$ és el número de dígits de $b$ (expressat en base decimal). La prova de la Teorema utilisa la successió de Fibonacci.

Enunciat de la Teorema

Supongam que s'aplica l'algoritme de Euclides en entrades sanceres no negatives $a$ i $b$. El número de passos (divisions) que requerix l'algoritme per a finalisar, és menor o igual que $5$ voltes el número de dígits decimals de $\min (a,b)$ (l'entrada de menor magnitut).

Eixemple

Supongam que s'aplica l'algoritme de Euclides en entrades $a=1235$ i $b=455$. La teorema de Lamé afirma que el número de passos (divisions) que requerix l'algoritme per a finalisar, és menor o igual que $5$ voltes el número de dígits decimals de $\min (1235,455)=455$. És dir, la cantitat de passos és menor o igual a $5\times 3=15$.

Podem comparar esta cota en la cantitat exacta de passos que requerix l'algoritme de Euclides en este eixemple. Els passos de l'algoritme són els següents:$$\begin{array}{c}1235=2\times 455+325,\\ 455=1\times 325+130,\\ 325=2\times 130+65,\\ 130=2\times 65+0.\end{array}$$L'algoritme termina en 4 passos (divisions), que és menor a la cota de 15 passos de la Teorema de Lamé.

Bibliografia

• Bach, Eric (1996). Teoria algorítmica de números . Jeffrey Outlaw Shallit. Cambridge, Massachusetts: MIT Press.ISBN 0-262-02405-5. Plantilla:OCLC
• Carvalho, João Bosco Pitombeira de (1993). Olhando mais de cim : Euclides, Fibonacci i Lamé . Revista do Professor de Matemàtica, São Paulo, n. 24, pág. 32-40, 2 sem.