Teorema de Lamé

Enunciado

O número de passos de divisão no algoritmo de Euclides com entradas ${\displaystyle u\,\!}$ e ${\displaystyle v\,\!}$ é limitado superiormente por ${\displaystyle 5\,\!}$ vezes a quantidade de dígitos decimais em ${\displaystyle min(u,v)\,\!}$.

Demonstração

${\displaystyle u=vq_{1}+v_{1},0<v_{1}<v}$

${\displaystyle v=v_{1}q_{2}+v_{2},0<v_{2}<v_{1}}$

${\displaystyle v_{1}=v_{2}q_{3}+v_{3},0<v_{3}<v_{2}}$

${\displaystyle ...}$

${\displaystyle v_{n-2}=v_{n-1}q_{n}+v_{n},0<v_{n}<v_{n-1}}$

${\displaystyle v_{n-1}=v_{n}q_{n+1}}$

${\displaystyle F_{n}=\left\{{\begin{matrix}1,&{\mbox{se }}n=0\\1,&{\mbox{se }}n=1\\F_{n-1}+F_{n-2},&{\mbox{outros casos}}\end{matrix}}\right.}$,

${\displaystyle \phi ^{2}=\phi +1<2+1\leq f_{2}+f_{1}=f_{3}}$

${\displaystyle \phi ^{3}=\phi ^{2}+\phi <f_{3}+2\leq f_{3}+f_{2}=f_{4}}$

${\displaystyle \phi ^{4}=\phi ^{3}+\phi <f_{4}+f_{3}=f_{5}}$

${\displaystyle \vdots }$

${\displaystyle \phi ^{j}<f_{j+1},\;\;j=2,3,4,...}$

${\displaystyle \log _{10}{\phi ^{n}}<\log _{10}{v}}$

${\displaystyle n<{\frac {\log _{10}^{v}}{\log _{10}^{\phi }}}.}$

${\displaystyle {\frac {1}{\log _{10}{\phi }}}<5}$

${\displaystyle n<{\frac {\log _{10}v}{\log _{10}{\phi }}}<5\times \log _{10}{v}}$.

${\displaystyle v=d_{k-1}10^{k-1}+d_{k-2}10^{k-2}+...+d_{1}10+d_{0}}$

Bibliografia