Teoria de números/Eficiência do algoritmo de Euclides: diferenças entre revisões

[edição não verificada][edição não verificada]
Conteúdo apagado Conteúdo adicionado
m ajustes
continuando os cálculos
Linha 201:
 
Tem-se:
* <math>\varphi^2 = \varphi + 1\,\!</math>
{{demonstração|A verificação é direta, exigindo cálculos bastante simples.}}
 
* <math>F_n = \frac{\varphi^n}{\sqrt{5}}\,\!</math>, arredondado para o inteiro mais próximo.
{{Demonstração|
Utilizando a fórmula de Binet, basta observar que o módulo de <math>\hat{\varphi}\,\!</math> é menor que <math>1\,\!</math>, e consequentemente, quando <math>n \to \infty\,\!</math>, tem-se <math>\hat{\varphi}^n \to 0\,\!</math>
}}
 
* <math>F_n \ge \varphi^{n-1}\,\!</math>
{{Demonstração|
SegueA facilmentejustificativa será dada por indução.:
# <math>F_1 = 1 \ge 1 = \varphi^0\,\!</math>
# Se for verdade que <math>F_n \ge \varphi^{n-1}\,\!</math>, então:
:<math>F_{n+1} = F_{n}+F_{n-1} \ge \varphi^{n-1} + \varphi^{n-2} = \varphi^{n-2}(\varphi + 1) = \varphi^{n-2}\varphi^2 = \varphi^{n}\,\!</math>
}}
 
* <math>\log \varphi < \frac{1}{5}\,\!</math>
{{Demonstração|
De fato, valem as seguintes equivalências:
<math>\log \varphi < \frac{1}{5} \Leftrightarrow 5\log \varphi < 1 \Leftrightarrow \log \varphi^5 < 1 \,\!</math>
 
Mas <math>\varphi^5 =5\varphi + 3\,\!</math> (verifique a partir de <math>\varphi^2 = \varphi + 1\,\!</math>), e <math>\varphi > \frac{8}{5} \,\!</math> pois
:<math>\varphi > \frac{8}{5} \Leftrightarrow \frac{1 + \sqrt{5}}{2} > \frac{8}{5} \Leftrightarrow 5(1 + \sqrt{5}) > 16 \Leftrightarrow 5\sqrt{5} > 11 \Leftrightarrow 125 = 25 \cdot 5 > 121\,\!</math>
 
Sendo que esta última desigualdade é verdadeira.
}}
 
Como foi visto anteriormente, quando <math>(a,b)\,\!</math> é exige exatamente <math>n\,\!</math> passos, é tem-se <math>a\ge F_n+2\,\!</math> e <math>b\ge F_n+1\,\!</math>. Logo,
:<math>a\ge F_n+2 \ge \varphi^{n+1}\,\!</math>
Aplicando o logaritmo em ambos os menbros, segue:
:<math>(n+1)\log \varphi \le \log a\,\!</math>
ou seja
:<math>n\le \frac{\log a}{\log \varphi} = \log_{\varphi}a\,\!</math>
 
Mas <math>\frac{1}{\log \varphi} < 5\,\!</math>, então:
:<math>n\le \frac{1}{\log \varphi}\cdot \log a < 5\log_{\varphi}a < 5N\,\!</math>, onde <math>N\,\!</math> é o número de dígitos de <math>a\,\!</math>
 
== Exercícios ==